4. Let n – m = sn + r where r, n, s are integers and 0 ≤ s < n.
5. gsn + r = e
By definition of n = o(g)
7. gr = e
As n is the least that makes gn = e and 0 ≤ r < n.
8. r = 0
Lemma: Let . if and only if .
Proof: Let . if and only if .
By Euclidean division: , some integers with .
We have , hence if and only if .
But if and only if (i.e. if and only if ),
since, by definition, is the least positive integer satisfying .
Hence the result.
By definition: .
Therefore, (where ) all lie in – furthermore, by lemma above, these are pairwise distinct.
Finally, any element of the form , equals one of (again by lemma).
We conclude that are precisely the elements of ,
so , as required.
- Q.E.D. -