# Proof about $\phi (n)$ being a power of 2.

1. May 15, 2013

### cragar

1. The problem statement, all variables and given/known data
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 doesnt say but Im pretty sure x
is a positive integer. and $\phi$ is Eulers phi function.
3. 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.

2. May 15, 2013

### Office_Shredder

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

3. May 15, 2013

### cragar

ok thats a good point. and we know that if $2^t+1$ is prime then t is a power of 2.
and we also couldnt 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.