Proving a generalization of Fermat's Little Theorem, involving the Euler phi function

Here is a simplified idea of what I am working to solve. I am unsure where to start (besides what I've listed below from looking at previous sections), or where to go from there. Thanks in advance for any help with this proof!

The Euler phi function ϕ gives the number of positive integers less than or equal to, and relatively prime to, a give positive integer. e.g. ϕ(3)=2, ϕ(5)=4. There is a generalization of Fermat's Little Theorem due to Euler:


Theorem. Let n be a positive integer and a∈ℤ with gcd(a,n)=1. Then a^(ϕ(n))≡1(mod n)


(a) Prove this theorem.


(b) Explain why Fermat's Little Theorem is a special case of this theorem.


What I've deduced so far.
The fact that a^|G|=e for every a∈G, if G is finite with identity e, seems as if it will help.
LaGrange's Theorem and/or cosets will likely be used as well.


Thanks in advance. Any help/solution to this would be a lifesaver!

consider, that for any natural number n > 0, the set of integers modulo n co-prime to n form a group, often called the group of units modulo n, or U(n).

this group has order φ(n): |U(n)| = φ(n). it may not be clear that if gcd(a,n) = 1 and gcd(b,n) = 1, that gcd(ab,n) = 1 as well.

but if gcd(a,n) = 1, then there are integers r,s with ar + sn = 1, and if gcd(b,n) = 1, then there are integers t,u with bt + un = 1.

hence (ar + sn)(bt + un) = 1*1 = 1, so:

ab(rt) + (aru + bst + sun)n = 1, so there are integers x,y (namely x = rt, and y = aru+bst+sun) with (ab)x + yn = 1, gcd(ab,n) = 1.

if we denote a modulo n by [a], this shows that if [a],[b] are in U(n), so is [a][b] = [ab]. since U(n) is finite, it is a group, since it is closed

under multiplication modulo n. thus Lagrange's theorem applies.

to obtain Fermat's Little Theorem, one considers the group U(p), where p is a prime.