Mathematical Theorem

Fermat’s Little Theorem

Pierre de Fermat first stated the theorem in a letter dated October 18, 1640, to his friend and confidant Frénicle de Bessy. Over the years, it has become one of the most fundamental results in Number Theory. Every Math Olympiad participant is expected to know it, but this theorem is often taught without proof, and students do not always grasp its whole idea as a result. Therefore, in this article, we will derive this famous theorem, so that you will hopefully be able to gain some intuition after reading it.

Derivation

We will use modular arithmetic. First, let us consider a residue system modulo a prime p, that is all possible remainders when a number is being divided by p:

Now, we multiply every number of the obtained set by some natural number a relatively prime to p:

The important question that might pop up in your head is, what are the numbers of the new set congruent to modulo p? We try some smaller examples for p = 3, 5, 7, and realize that the set aS looks to be equivalent to the original set S. Indeed, we have p − 1 integers, and they all seem different, and if they are, then they form a complete residue system modulo p. So now our goal is to prove every two integers of the set are distinct modulo p. We will prove this by contradiction:

Awesome. Now we know that S and aS form a complete residue system modulo p. But this means that the products of all their elements are also congruent!

Clearly, p and (p-1)! have no common divisors except for 1, so we can divide both sides by (p-1)!

And thus we got the famous result, Fermat’s Little Theorem. As you can see, the derivation wasn’t too complicated, which might be surprising because of how beautiful and unintuitive this theorem might be.

Other proofs and a generalization

We used modular arithmetic to prove Fermat’s Little Theorem, but some other ways exist, namely a proof by induction and even a combinatorial proof. We might show them in future articles, so stay tuned.

And yes, there is a generalization. Define a and n to be positive coprime integers, and φ(n) to be equal to the number of integers from 1 to n relatively prime to n (Euler’s totient function). Then the following congruency holds:

This is Euler’s Theorem. We leave its proof as an exercise to the reader.

Conclusion

This article has hopefully shown how important and elegant Fermat’s Little Theorem is. Even though it seems simple, the theorem is frequently being applied in Math contests, and this derivation might be a good lesson in Number Theory.