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 $p$ is a prime then $a^p\equiv a ({\rm mod} p)$ .

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

Lemma 1.8.3   Let $n>1$ be an integer. Let $a$ be any integer relatively prime to $n$ . Then each integer in the set $a\Phi_n=\{a\cdot r \vert \ gcd(r,n)=1\}$ is relatively prime to $n$ and they are mutually incongruent to each other.

proof of lemma: The elements of $\{a\cdot r \vert \ gcd(r,n)=1\}$ are all relatively prime to $n$ since $gcd(a,n)=1$ . They are mutually incongruent to each other since if $ia\equiv aj ({\rm mod} n)$ then by the cancellation law (the third part of Lemma 1.7.3), $i\equiv j ({\rm mod} n)$ , for any $i,j\in \Phi_n$ . But if $1\leq i,j\leq n-1$ then we must have $i=j$ . $\Box$

proof of theorem: First, assume $p\not\vert a$ . The set $\{1,2,...,p-1\}$ forms a complete set of representatives of residue classes modulo $p$ . The set $\{a,2a,...,(p-1)a\}$ must as well, by the above lemma. Therefore, for each $1\leq i\leq p-1$ there is a unique $1\leq k_i\leq p-1$ such that $i\equiv ak_i ({\rm mod} p)$ . Multiply all these together:

$$(p-1)!\equiv 1\cdot 2\cdot ... \cdot (p-1) \equiv ak_1\cdot ak_2\... ...\equiv a\cdot 2a\cdot ... \cdot (p-1)a\ \equiv (p-1)!a^{p-1} ({\rm mod} p).$$

Since $p\not\vert (p-1)!$ , the cancellation law gives $a^{p-1}\equiv 1 ({\rm mod} p)$ . Multiply both sides by $a$ to get $a^p\equiv a ({\rm mod} p)$ .

If $p\vert a$ then $a\equiv 0 ({\rm mod} p)$ , so $a^p\equiv 0 ({\rm mod} p)$ , so by the transitivity of congruence, we have $a^p\equiv a ({\rm mod} p)$ , as desired. $\Box$