We prove a special case of Euler's theorem, Fermat's little theorem, first. The proof given here, unlike the one in §1.7.5, can be generalized to the proof of Euler's theorem.
Before proving Fermat's Little Theorem, we need a key property concerning residue classes (or equivalence classes) mod .
proof of lemma: The elements of are all relatively prime to since . They are mutually incongruent to each other since if then by the cancellation law (the third part of Lemma 1.7.3), , for any . But if then we must have .
proof of theorem: First, assume . The set forms a complete set of representatives of residue classes modulo . The set must as well, by the above lemma. Therefore, for each there is a unique such that . Multiply all these together:
Since , the cancellation law gives . Multiply both sides by to get .
If then , so , so by the transitivity of congruence, we have , as desired.