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.