Prove Euler's Totient Function: Divisibility of phi((2^n)-1) by n

[fk378]

Homework Statement

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)

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.

 

[AKG]

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|?