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: Euler's function

  1. Sep 24, 2008 #1
    1. The problem statement, all variables and given/known data
    Let phi denote Euler's totient function, ie for k in N, phi(k) is the number of natural numbers less than k which are relatively prime to k.
    Prove that for every n in N we have n| phi((2^n) -1).
    (Hint: Compute o[2] in U_(2^n)-1, the group of units in Z mod (2^n)-1)

    3. The attempt at a solution
    I understand that in the hint, o[2]=n...but I don't know how to relate it to the problem.

    I also found that the value of phi(k) for any k is an even integer.
  2. jcsd
  3. Sep 26, 2008 #2


    User Avatar
    Science Advisor
    Homework Helper

    How does phi((2^n)-1) relate to U_((2^n)-1)? I.e. what sort of numbers in {0, ..., 2^n - 1} appear in U_((2^n)-1)? Next, if g is an element of a finite group G, what can you say about the relationship between o[g] and |G|?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook