Prove that there is no odd $n$ such that $\phi (n) = 2^{32}$

273 Views Asked by At

I've encountered this problem, which I believe is very simple, but I didn't manage to solve it myself.

Prove that there is no odd $n$ such that $\phi (n) = 2^{32}$, where $\phi$ is Euler's function.

I managed to show that if $\phi(n) = 2^r$ for some $r$, then $n$ is the product of distinct primes, but now I'm stuck.

Any ideas?

1

There are 1 best solutions below

1
On BEST ANSWER

Of course there are such $n$. The simplest is $n=2^{33}$. And there are several others. The next simplest is $3\cdot 2^{32}$.

Maybe you want to show that there is no odd natural number $n$ such that $\varphi(n)=2^{32}$. Edit: The question was changed, with "odd" inserted.

Any such odd $n$ would have to be the product of distinct Fermat primes, that is, primes of the form $2^{2^k}+1$.

Note that by a result of Euler, $2^{2^5}+1$ is not prime. The only smaller Fermat primes are $2^{2^k}+1$ for $k=0$ to $4$. But the product $(2^{2^0}+1)(2^{2^1}+1)(2^{2^2}+1)(2^{2^3}+1)(2^{2^4}+1)$ is less than $2^{32}$ (by one unit).