Fermat’s Little Theorem and its Generalization to Euler’s Theorem

Primes have been, and still are, one of the most important areas of studies in mathematics. Although we know relatively very little about primes, we still do know quite a lot. This article explores a property of primes that we do know: Fermat’s little theorem. A powerful theorem in prime number theory, this theorem dates back to the 1600s —Pierre de Fermat’s time.

Now, Fermat is notorious for leaving out proofs. Although his results are quite central to modern research, he almost never gave proofs. Fermat’s little theorem is one such result. Firstly, what even is the theorem? Well, mathematically, it states the following:

In English, this means that for a prime, p, aᵖ — a is always perfectly divisible by p. If a and p are coprime, that is if a is not divisible by p, then this congruence can further be reduced to the following:

Fermat stated this result in a letter to Frénicle de Bessy, a fellow mathematician:

Tout nombre premier mesure infailliblement une des puissances −1 de quelque progression que ce soit, et l’exposant de la dite puissance est sous-multiple du nombre premier donné −1; et, après qu’on a trouvé la première puissance qui satisfait à la question, toutes celles dont les exposants sont multiples de l’exposant de la première satisfont tout de même à la question.

Roughly translated, this reads the following:

Every prime number [p] divides necessarily one of the powers minus one of any [geometric] progression [a, a², a³, …] [that is, there exists t such that p divides at — 1], and the exponent of this power [t] divides the given prime minus one [divides p — 1]. After one has found the first power [t] that satisfies the question, all those whose exponents are multiples of the exponent of the first one satisfy similarly the question [that is, all multiples of the first t have the same property].

And, consistent with his notoriety, Fermat wrote:

Et cette proposition est généralement vraie en toutes progressions et en tous nombres premiers; de quoi je vous envoierois la démonstration, si je n’appréhendois d’être trop long.

Translation: And this proposition is generally true for all series and for all prime numbers; I would send you a demonstration of it, if I did not fear going on for too long.

Since his time, there have been many published proofs of this theorem. In this article, we’ll explore a particularly nice proof given by Euler in 1736. However, before we dive into the proof, we’ll need the following lemma:

This is a special case of the Freshman’s Dream. To see why this is true, we turn to the binomial expansion of the LHS:

It’s fairly evident from this that all terms in this binomial expansion are divisible by p except for the terms xᵖ and yᵖ. And this concludes the proof of this lemma.

Now, to prove Fermat’s little theorem, we will proceed by induction. We assume the following is true:

And we seek to prove the case:

We now notice that we can use the lemma to simplify this significantly and the result seems to reveal itself beautifully:

Testing for the base case is trivial and it is very easy to see that the theorem holds true for all integers a.

Generalization to Euler’s Theorem

Fermat’s theorem was soon generalized to Euler’s theorem by Euler. No surprises there! Euler’s genius knew no bounds. But the generalized theorem reads the following:

Where φ(n) is Euler’s totient function, a is an integer, and n is any number coprime to a. Wait, what is the totient function, φ(n)? Well, it’s nothing scary. It’s simply a function that represents the number of integers from 1 to n that are coprime to n. A proof for this requires some heavy machinery, so I’m leaving it out for the time being. You’ll just have to take my word for it!

It is fairly easy to see how Fermat’s little theorem is a special case of this theorem. If we let n be a prime number, then φ(n) = n — 1. Since p is prime, all numbers less than p are coprime to p. As a result, Euler’s theorem reduces elegantly to Fermat’s little theorem:

With this, our exploration of Fermat’s little theorem ends. Thank you for reading. Happy new year, by the way! I hope you have a great year ahead, filled with joy, health, prosperity and more mathematics :)