One of the first results in any introduction to number theory is Fermat’s Little Theorem, so called in contrast to the Last Theorem, or indeed to any of Fermat’s other results.
Theorem 1 (Fermat’s Little Theorem). Let be a prime number and let be any integer. Then
In this post — aimed at students taking an introductory course in number theory — I want to explain the two proofs that I find to be the simplest. Neither is deep, but the second requires a tiny bit of group theory, whereas the first does not.
1. First proof: by binomial coefficients
We shall take as given that the binomial coefficients , for are natural numbers. We also take as given the Binomial Theorem:
Fix a prime number .
Lemma 2. For , the binomial coefficient is divisible by .
Proof: Since is an integer, divides . Since is prime, and , it follows that and are coprime. By Euclid's Lemma, . Therefore is an integer.
Lemma 3. For integers we have .
Proof: Apply the Binomial Theorem and Lemma 1.
It’s now a simple matter to give the first proof of Fermat’s Little Theorem.
Proof: Let be a prime number, and let be the set of integers satisfying the conclusion of the theorem. If is odd, then . Otherwise, if then . Thus . Lemma 3 shows that is closed under addition. Therefore .
2. Second proof: by Lagrange’s Theorem
The second strategy is reasonably simple. I think of it as the proof ‘by Lagrange’s Theorem’, but that is perhaps unfair since its use of Bézout’s Lemma is just as key.
Let . Then there exist such that .
The proof goes by showing that the set
of -linear combinations of , is also the set of integer multiples of the greatest common divisor .
Let be a finite group, and let be a subgroup. Then .
The proof of Lagrange’s Theorem is a straightforward counting proof. One shows that each coset of has the same order, and that the cosets partition .
Okay! Using these two ingredients, we get the second proof of Fermat’s Little Theorem.
Proof: Let be a prime number. It is a consequence of Bézout’s Lemma that forms a group under multiplication modulo . Moreover it is a group of order . Thus, for each , we have .
Now let . If is divisible by , then certainly . Otherwise, there exists and such that . Then , as required.
To be perfectly honest, I find this second proof less satisfactory than the first. Relying on Bézout seems reasonable enough (we are interested in integer arithmetic after all), but relying on Lagrange is a bit silly. Lagrange’s Theorem is a statement about all finite groups, which is just far too strong for what we need.
However you get there, Fermat’s Little Theorem is an important result of elementary number theory.