1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. May 15, 2013 #1
    1. The problem statement, all variables and given/known data
    Prove: [itex] \phi (n) [/itex] is a power of 2 if and only if
    [itex] n=(2^x)p_1...........p_k [/itex]
    where the [itex] p_i [/itex] are distinct Fermat primes. And it doesnt say but Im pretty sure x
    is a positive integer. and [itex] \phi [/itex] 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 [itex] \phi (n)= \phi (2^x) \phi (p_1)......\phi (p_k) [/itex]
    and [itex] \phi (2^x) = 2^x-2^{x-1}=2^{x-1}(2-1) [/itex] so that is a power of 2.
    And each Fermat prime will be [itex] \phi (p_i)=2^{2^s}+1-1 [/itex] 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. jcsd
  3. May 15, 2013 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    You know that you can always write [itex] \phi(n)[/itex] as a product of [itex]\phi(p_i)[/itex] - what if pi is NOT a Fermat prime? Do you still get a power of 2?
  4. May 15, 2013 #3
    ok thats a good point. and we know that if [itex] 2^t+1 [/itex] 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
    [itex] \phi (p^u)=p^u-p^{u-1}=p^{u-1}(p-1) [/itex] and [itex] p^{u-1} [/itex] is not a power of 2 unless p is 2.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted