Fermat’s Little Theorem

We begin this chapter with a fundamental result of number theory, discovered by Pierre de Fermat. Fermat lived from 1601 to 1665. Many of his contemporaries were “number-lovers” rather than number theorists, [108, p. 51], and one thing that interested them was perfect numbers (a number is perfect if it is the sum of all its proper divisors). Bernard Frénicle de Bessy, who was also a mathematician and physicist, first raised the question of whether there was a perfect number of 20 digits and, if not, what the next largest perfect number was. (See [29] and [30].) The answer to the question required determining whether certain large numbers were prime. As a consequence, the men began corresponding. In a letter to Frénicle, dated October 18, 1640, Fermat stated what is now known as Fermat’s theorem or Fermat’s little theorem (to distinguish it from Fermat’s last theorem), but he did not include a proof. In 1736, almost a century later, Leonhard Euler gave the first rigorous proof of the little theorem. Though this theorem is clearly theoretical in nature, it plays an important role in primality testing; that is, in deciding whether or not a certain number is prime. Fermat’s little theorem (in the form due to Euler) is also the mathematical heart of the widely used RSA code that we will describe later in this chapter. In fact, Fermat’s little theorem is not little at all.