Finding all $n$ for which $\phi(n)$ is power of $2$

Question

How to find all $n$ for which $\phi(n)$ is power of $2$?

I would like to know how to find all $n$ for which Euler totient value $\phi(n)$ is a power of $2$.

I already managed to prove that $\phi(n)$ is even for $n\ge 3$ but I have no clue on how to approach this one (thought it might help me).

Answer 1

such a number is of the form $2^ap_1p_2\dots p_n$ where every $p_i$ is a distinct fermat prime.

It is easy to see these numbers work.

To see other numbers dont work first notice that no odd prime can appear with exponent larger than $1$ (simply apply the formula).

It is also clear that if $p$ is a dividor of the number then $p-1$ is a power of $2$. hence $p$ is of the form $2^n+1$. It has been shown that primes of the form $2^n+1$ are also of the form $2^{2^n}+1$

Answer 2

If $p$ is prime, $\phi(p^k) = p^{k-1} (p-1)$. In the case $p=2$, this is always a power of $2$. If $p$ is an odd prime, you need $k=1$, and $p-1$ must be a power of $2$, so $p$ is a Fermat prime. Now use the fact that $\phi$ is multiplicative.