A dark field of small dots marking, for each residue a modulo the prime 101, the exponents k at which a to the power k is congruent to 1; the column k = 100 is lit for every row, which is Fermat's little theorem
Unit 05 · All masterclasses · 60 min

The Theorems of Fermat, Euler, and Wilson

Three classical theorems about powers modulo a prime, and the cryptography built on them
Image: Own rendering

Fermat's little theorem with two proofs, Euler's totient function and Euler's theorem, the multiplicative order, and Wilson's theorem, which characterizes the primes by one congruence. The theorems are then put to work: the Fermat test and its refinement by Miller and Rabin tell composites from primes without factoring, and the RSA cryptosystem turns Euler's theorem into the lock behind the certificates of most secure connections on the internet.

Preview: the beginning of the unit

Every time a browser opens a secure connection, a computer somewhere raises a number with several hundred digits to a power with several hundred digits and reduces the result modulo a third such number, and the whole exchange rests on a fact that Pierre de Fermat (1607-1665) stated in a letter in 1640 without proof. This unit proves that fact twice, extends it from prime moduli to all moduli with Euler’s theorem, adds Wilson’s theorem, which characterizes the primes by a single congruence, and then puts the theorems to work: first as a test that tells a composite number from a prime without factoring it, and then as the RSA cryptosystem, the public-key method that still underlies the certificates of most secure connections on the internet.

1 Fermat’s little theorem

Unit 4 ended with the last digit of \(7^{222}\), found from the cycle \(7, 9, 3, 1\) of the powers of \(7\) modulo \(10\). Such cycles exist for every modulus, and modulo a prime they have a striking regularity. To see it, take \(p = 7\) and write down the powers of each non-zero residue: \begin{align*} 2^{k} &\equiv 2, 4, 1, 2, 4, 1 \pmod 7, \\ 3^{k} &\equiv 3, 2, 6, 4, 5, 1 \pmod 7, \\ 6^{k} &\equiv 6, 1, 6, 1, 6, 1 \pmod 7 \qquad (k = 1, 2, \ldots, 6). \end{align*} The three sequences cycle with different lengths, \(3\), \(6\), and \(2\), but all three show a \(1\) in the sixth place, and so do the sequences for \(1\), \(4\), and \(5\). The sixth power of every non-zero residue modulo \(7\) is \(1\), and \(6 = p - 1\). Fermat announced the general statement in 1640, and it is now called his little theorem, to distinguish it from his Last Theorem, which Unit 8 discusses.

The two forms say the same thing. Multiplying the first by \(a\) gives the second for \(a\) not divisible by \(p\), and when \(p \mid a\) both sides of the second form are \(0\) modulo \(p\). Conversely, if \(a^{p} \equiv a\) and \(p \nmid a\), multiplying by the inverse of \(a\) modulo \(p\) (Unit 4) gives \(a^{p-1} \equiv 1\). The first proof below uses an idea that reappears in Section 2, and the second counts coloured necklaces.