Eli Bendersky's website A very important and useful theorem in number theory is named after Leonhard Euler:
Where 
is Euler's totient function - the count of numbers smaller than n that are coprime to it.
Here I want to present a nice proof of this theorem, based on group theory. I begin with some preliminary definitions and gradually move towards the final goal.
(I) Congruence class: Let a and n > 0 be integers. The set of all integers that have the same remainder as a when divided by n is called the congruence class of a modulo n and is denoted by 
, where:
is the set of all congruence classes modulo n.
(II) Units of : If for we find some 
such that 
, we call a unit of . The set of units of is denoted by 
For example, 
is a unit of 
, because 
.
(III) The congruence class is a unit of if and only if 
(the GCD of a and n is 1, in other words they're co-prime).
Proof: By definition of units, there exists some such that . Therefore 
, which implies that for some q, 
. Thus 
. So 1 is a linear combination of a and n. Therefore 
.
On the other hand, if , there exist q and b such that 
, or , so .
(IV) By definition, since every unit of is coprime to n, the number of units of (or, the number of elements of ) is .
Let's keep this result in mind and prepare some more theorems in order to attack the proof.
(V) Lagrange's theorem: If H is a subgroup of the finite group G, then the order of H is a divisor of the order of G.
Proof: Let's first define 
and 
. Also, let 
be the equivalence relation defined in example (III) of the previous post. Since it's an equivalence relation, it partitions G into equivalence classes. Define 
as the equivalence class of a with , for any 
.
To prove Lagrange's theorem, we're going to show that has the same number of elements as H. For this purpose, let's define a function 
by 
for all 
and prove that it's an isomorphism. To do that, we'll have to separately prove that it's onto and one-to-one.
But first, let's verify that the stated codomain of 
is correct. If 
then 
because 
, so by definition of we have 
. So indeed the codomain of is .
- Let's pick some y in G such that
. By definition of our it means that 
for some . So 
has a solution 
(since 
). Therefore is onto. - Suppose that
with 
. Then 
and by cancellation in groups we have 
, which proves that is one-to-one.
So we've proved that is an isomorphism, which means that 
(we can map each element of to one and only one element of 
).
We've previously shown that the equivalence classes of partition G. But now we see that the size of each equivalence class is equal to . Therefore, all the equivalence classes are of the same size, and 
where t is the number of equivalence classes. This proves Lagrange's theorem.
We're almost there. To see how all of this relates to Euler's theorem, let's first define the order of an element of a group.
(VI) Order of group element: Let . If there exists a positive integer n such that 
, then a is said to have finite order and the smallest such positive integer is called the order of a, denoted by 
.
We'll also define the subgroup generated by an element:
(VII) Cyclic subgroup: 
is a cyclic subgroup of G generated by . For a finite G this subgroup is also finite, and its size is: 
.
Armed with these definitions, we're now ready for the following corollary of Lagrange's theorem:
(VIII) Lagrange theorem corollary: Let G be a finite group of order n. Then:
- For any , divides n
- For any ,
Proof: As we've seen, and by Lagrange's theorem 
divides n (since 
is a subgroup of G). Therefore (1) is proven.
For (2), note that if a has order m, then by (1) we have 
for some integer q. Thus 
. But a has order m, so 
and therefore 
. Q.E.D.
We now finally have all the tools required to prove Euler's theorem.
Proof of Euler's theorem: Let 
the group of units modulo n. The order of G is (by (IV)). Now, by (VIII) part (2), raising any congruence class to the power must give the identity element. The statement 
is equivalent to 
