Proof about [itex] \phi (n) [/itex] being a power of 2.

[cragar]

Homework Statement

Prove: $\phi (n)$ is a power of 2 if and only if
$n=(2^x)p_1...p_k$
where the $p_i$ are distinct Fermat primes. And it doesn't say but I am pretty sure x
is a positive integer. and $\phi$ is Eulers phi function.

The Attempt at a Solution

we know that phi is a multiplicative function when the gcd(q,w)=1
so $\phi (n)= \phi (2^x) \phi (p_1)...\phi (p_k)$
and $\phi (2^x) = 2^x-2^{x-1}=2^{x-1}(2-1)$ so that is a power of 2.
And each Fermat prime will be $\phi (p_i)=2^{2^s}+1-1$ so each Fermat prime will be a power of 2 when phi is applied to it. So I guess I have showed that if n is written as it is then
phi (n) will be a power of 2, but I haven't shown the other direction that this is the only n where phi (n) is a power of 2. Maybe I could try a proof by contradiction.

 

[Office_Shredder]

You know that you can always write $\phi(n)$ as a product of $\phi(p_i)$ - what if p_i is NOT a Fermat prime? Do you still get a power of 2?

 

[cragar]

ok that's a good point. and we know that if $2^t+1$ is prime then t is a power of 2.
and we also couldn't have a power of a fermat prime as a factor of n because
$\phi (p^u)=p^u-p^{u-1}=p^{u-1}(p-1)$ and $p^{u-1}$ is not a power of 2 unless p is 2.