Take the number 2 and raise it to larger and larger powers. Divide each result by 7 and note the remainder:

Power $2^1$ $2^2$ $2^3$ $2^4$ $2^5$ $2^6$
Value 2 4 8 16 32 64
Remainder mod 7 2 4 1 2 4 1

At $2^6$ the remainder is 1. Now try 3 and the prime 5: $3^4=81$, which leaves remainder 1 when divided by 5. And 10 and the prime 13: $10^{12}=1{,}000{,}000{,}000{,}000$, which also leaves remainder 1 when divided by 13.

Coincidence? No. It is Fermat’s little theorem.

The statement

If $p$ is a prime number and $a$ is an integer that is not a multiple of $p$, then $a^{p-1}$ leaves remainder 1 when divided by $p$. In the notation of congruences, created by Gauss in 1801:

$$a^{p-1}\equiv1\pmod p.$$

The name “little” only serves to distinguish it from the last theorem. In practice, the little one is far more useful.

Choose the base and a prime. When the base is a multiple of the prime, the hypothesis of the version with exponent p − 1 does not apply.

A letter without a proof

Fermat announced the theorem in a letter of 18 October 1640 to the mathematician Bernard Frénicle de Bessy. As usual, he did not show the proof:

I would send you the proof, if I did not fear it being too long.

— Fermat, letter to Frénicle de Bessy (1640)

The first published proof was by Leonhard Euler in 1736, almost a hundred years later. It was learned later that Leibniz also had a proof, around 1683, which he never published.

A proof by shuffling

Let us prove the theorem for $p=7$ and $a=3$; the general argument is identical.

Write the numbers $1,2,3,4,5,6$. Multiply each by 3 and take the remainder mod 7:

$$3,\ 6,\ 9\to2,\ 12\to5,\ 15\to1,\ 18\to4.$$

The remainders are $3,6,2,5,1,4$: the same numbers as before, shuffled. This always happens. No remainder can be 0, because $p$ divides neither $a$ nor $k$. And no remainder repeats, because if $ai$ and $aj$ left the same remainder, $p$ would divide $a(i-j)$ and therefore $i-j$, which is impossible for two different numbers between 1 and $p-1$.

Since the two sets are equal, their products also leave the same remainder:

$$(3\cdot1)(3\cdot2)\cdots(3\cdot6)\equiv1\cdot2\cdots6\pmod7,$$

that is, $3^6\cdot6!\equiv6!\pmod7$. Since 7 is prime and does not divide $6!$, we may cancel $6!$ and conclude that $3^6\equiv1\pmod7$. Check: $3^6=729=7\cdot104+1$.

Huge calculations with little effort

What is the remainder of $3^{100}$ divided by 7? Without the theorem we would need a 48-digit number. With it: $3^6\equiv1$, and $100=6\cdot16+4$. So

$$3^{100}=\left(3^6\right)^{16}\cdot3^4\equiv1^{16}\cdot81\equiv4\pmod7.$$

This ability to reduce gigantic powers is the basis of the RSA system, which protects purchases and passwords on the internet. RSA uses a generalization of the theorem made by Euler, told in the Euler trail.

Careful with the converse

If $p$ is prime, then $a^{p-1}\equiv1$. But the converse is false: a number can pass the test without being prime. The smallest treacherous example is $561=3\cdot11\cdot17$, which satisfies $a^{560}\equiv1\pmod{561}$ for every $a$ with no factor in common with 561. Numbers like this are called Carmichael numbers. That is why the theorem can show a number is not prime, but cannot by itself show that it is.

Exercise: what is the remainder of 3¹⁰ divided by 11?

11 is prime and does not divide 3, so $3^{10}\equiv1\pmod{11}$. The remainder is 1. Check: $3^{10}=59{,}049=11\cdot5368+1$.

Exercise: what is the remainder of 2¹⁰⁰ divided by 13?

$2^{12}\equiv1\pmod{13}$ and $100=12\cdot8+4$. So $2^{100}\equiv2^4=16\equiv3\pmod{13}$. The remainder is 3.

Sources: Fermat biography, MacTutor.

All Fermat topics · ← Maxima and minima: the rectangle with the largest area · Fermat numbers: a conjecture and a counterexample →

Image credits.