## Fermat's Little Theorem, revisited

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.

Theorem 1.8.2 (Fermat's Little Theorem)   If is a prime then .

Before proving Fermat's Little Theorem, we need a key property concerning residue classes (or equivalence classes) mod .

Lemma 1.8.3   Let be an integer. Let be any integer relatively prime to . Then each integer in the set is relatively prime to and they are mutually incongruent to each other.

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.

david joyner 2008-04-20