Helpful context:

Here is a fact that looks like magic the first time you see it: take any number $a$ not divisible by a prime $p$, raise it to the power $p - 1$, and divide by $p$ - the remainder is always 1. So $2^{12} \equiv 1 \pmod{13}$, $5^{6} \equiv 1 \pmod{7}$, $7^{10} \equiv 1 \pmod{11}$. Every time, with every prime and every integer not divisible by it. Pierre de Fermat stated this in 1640. Euler generalized it in 1763 to any modulus, not just primes. Together these theorems are the theoretical core of RSA encryption.

The proof is not deep once you see the right picture. The nonzero elements of $\mathbb{Z}/p\mathbb{Z}$ form a group under multiplication. Multiplying by $a$ permutes that group. That permutation, together with careful counting, forces $a^{p-1} = 1$. The argument is direct and constructive - it even shows you why the theorem is true, not just that it is.

Fermat’s Little Theorem

Theorem (Fermat, 1640). Let $p$ be a prime and let $a$ be an integer with $p \nmid a$. Then

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

Equivalently, for any integer $a$: $a^p \equiv a \pmod{p}$.

(The second form is nicer to state: it holds even when $p \mid a$, since then both sides are $0$ mod $p$.)

Proof via Permutation

Consider the set $S = \{1, 2, 3, \ldots, p-1\}$ of nonzero residues mod $p$. Multiply every element by $a$:

$$T = \{a \cdot 1,; a \cdot 2,; \ldots,; a \cdot (p-1)\} \pmod{p}.$$

Claim: $T = S$ as sets (with elements reduced mod $p$).

Why the elements of $T$ are distinct: Suppose $ai \equiv aj \pmod{p}$ for $1 \leq i, j \leq p-1$. Since $p \nmid a$ and $p$ is prime, $\gcd(a, p) = 1$, so $a$ is invertible mod $p$. Multiply both sides by $a^{-1}$: $i \equiv j \pmod{p}$. But $1 \leq i, j \leq p-1$, so $i = j$.

Why the elements of $T$ lie in $S$: Each $ai \bmod p$ is in $\{1, \ldots, p-1\}$ (it’s nonzero because $p \nmid a$ and $p \nmid i$, and $p$ is prime).

So $T$ has $p-1$ distinct elements all in $S$. Since $|S| = p-1$, we have $T = S$.

The key step. The product of all elements of $S$ equals the product of all elements of $T$:

$$1 \cdot 2 \cdots (p-1) \equiv a \cdot (a \cdot 2) \cdots (a \cdot (p-1)) = a^{p-1} \cdot (p-1)! \pmod{p}.$$

So $(p-1)! \equiv a^{p-1} \cdot (p-1)! \pmod{p}$.

Since $\gcd((p-1)!, p) = 1$ (as $p$ is prime, none of $1, \ldots, p-1$ is divisible by $p$), we may cancel $(p-1)!$ to get $a^{p-1} \equiv 1 \pmod{p}$. $\square$

Group-Theoretic Proof (Lagrange’s Theorem)

The nonzero elements $\{1, 2, \ldots, p-1\}$ form an abelian group of order $p-1$ under multiplication mod $p$ (they are closed, associative, have identity 1, and each has an inverse since $\gcd(a, p) = 1$).

By Lagrange’s theorem, the order of any element $a$ divides the group order $p-1$. The order of $a$ is the smallest $k$ with $a^k \equiv 1$. Since $k \mid p-1$, we have $a^{p-1} = (a^k)^{(p-1)/k} \equiv 1^{(p-1)/k} = 1$. $\square$

This proof is shorter but requires Lagrange’s theorem, which itself requires a proof. The permutation argument is self-contained.

Wilson’s Theorem

Theorem (Wilson, 1770). An integer $p \geq 2$ is prime if and only if

$$(p-1)! \equiv -1 \pmod{p}.$$

Proof ($\Leftarrow$, the easy direction). If $p$ is composite, write $p = ab$ with $1 < a, b < p$. Then $a$ appears as a factor in $(p-1)!$ and $a \mid p$, so $p \nmid (p-1)!$ - actually more directly: if $(p-1)! \equiv -1$ then $\gcd((p-1)!, p) = 1$. But $a \mid p$ and $a \mid (p-1)!$ (since $1 \leq a \leq p-1$), so $a \mid \gcd((p-1)!, p)$. For $a > 1$ this means $\gcd > 1$, contradiction.

Proof ($\Rightarrow$). Suppose $p$ is prime. In $\mathbb{Z}/p\mathbb{Z}$, every element $a \in \{1, \ldots, p-1\}$ has a unique inverse $a^{-1}$. The elements that are their own inverse satisfy $a^2 \equiv 1$, i.e., $a \equiv \pm 1 \pmod{p}$, i.e., $a = 1$ or $a = p-1$.

Every other element $a \in \{2, \ldots, p-2\}$ pairs with its distinct inverse $a^{-1} \neq a$. When we compute $(p-1)! = 1 \cdot 2 \cdots (p-1)$, these paired elements cancel ($a \cdot a^{-1} = 1$), leaving only $1 \cdot (p-1) = p - 1 \equiv -1 \pmod{p}$. $\square$

Wilson’s theorem gives a primality criterion, but it is computationally useless for large numbers: computing $(p-1)!$ requires astronomical work.

Euler’s Totient Function

Definition. The Euler totient function $\varphi(n)$ counts the number of integers in $\{1, 2, \ldots, n\}$ that are coprime to $n$:

$$\varphi(n) = |\{a : 1 \leq a \leq n,; \gcd(a, n) = 1\}|.$$

Key values.

  • $\varphi(1) = 1$.
  • For prime $p$: $\varphi(p) = p - 1$ (all of $1, \ldots, p-1$ are coprime to $p$).
  • For prime power $p^k$: $\varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p-1)$ (the non-coprime elements are multiples of $p$: there are $p^{k-1}$ of them).
  • For distinct primes $p, q$: $\varphi(pq) = (p-1)(q-1)$.

Multiplicativity. If $\gcd(m, n) = 1$, then $\varphi(mn) = \varphi(m)\varphi(n)$. This follows from the Chinese Remainder Theorem: $\mathbb{Z}/mn\mathbb{Z} \cong \mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}$, and the units on both sides correspond.

Formula. For $n = p_1^{a_1} \cdots p_k^{a_k}$:

$$\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right).$$

For RSA: $\varphi(pq) = (p-1)(q-1) = pq - p - q + 1 = n - p - q + 1$.

Euler’s Theorem

Theorem (Euler, 1763). If $\gcd(a, n) = 1$, then

$$a^{\varphi(n)} \equiv 1 \pmod{n}.$$

Fermat’s little theorem is the special case $n = p$ prime, where $\varphi(p) = p - 1$.

Proof. The integers in $\{1, \ldots, n\}$ coprime to $n$ form a group under multiplication mod $n$ - call it $(\mathbb{Z}/n\mathbb{Z})^\times$ - with order $\varphi(n)$. The element $a$ has some order $k$ dividing $\varphi(n)$ (by Lagrange). So $a^{\varphi(n)} = (a^k)^{\varphi(n)/k} \equiv 1^{\varphi(n)/k} = 1$. $\square$

RSA Correctness

RSA depends entirely on Euler’s theorem. Here is the complete correctness proof.

Setup. Choose distinct large primes $p$ and $q$. Set $n = pq$ and $\varphi(n) = (p-1)(q-1)$. Choose $e$ with $\gcd(e, \varphi(n)) = 1$. Compute $d = e^{-1} \bmod \varphi(n)$ via the extended Euclidean algorithm.

Encryption. Given message $m$ with $\gcd(m, n) = 1$: compute $c = m^e \bmod n$.

Decryption. Compute $c^d \bmod n$.

Correctness claim. $c^d \equiv m \pmod{n}$.

Proof. We have $c^d = (m^e)^d = m^{ed}$. Since $d \equiv e^{-1} \pmod{\varphi(n)}$, there exists an integer $k$ with

$$ed = 1 + k\varphi(n).$$

Therefore

$$m^{ed} = m^{1 + k\varphi(n)} = m \cdot (m^{\varphi(n)})^k.$$

By Euler’s theorem (using $\gcd(m, n) = 1$), $m^{\varphi(n)} \equiv 1 \pmod{n}$. So

$$m^{ed} \equiv m \cdot 1^k = m \pmod{n}. \quad \square$$

When $\gcd(m, n) \neq 1$. If $p \mid m$ but $q \nmid m$ (the case $p \mid m$ and $q \mid m$ means $n \mid m$, so $m \equiv 0$ and the result is trivial), then $m \equiv 0 \pmod p$ and $m \not\equiv 0 \pmod q$. By Fermat, $m^{q-1} \equiv 1 \pmod q$, so $m^{k(p-1)(q-1)} \equiv 1 \pmod q$, giving $m^{ed} \equiv m \pmod q$. And $m^{ed} \equiv 0 \equiv m \pmod p$ trivially. By CRT, $m^{ed} \equiv m \pmod{pq}$.

Fermat Primality Test and Its Failure

Fermat test. To test if $n$ is prime: pick random $a$ with $\gcd(a, n) = 1$. Check if $a^{n-1} \equiv 1 \pmod{n}$. If not, $n$ is definitely composite. If yes, $n$ is probably prime.

Carmichael numbers. A composite $n$ is a Carmichael number if $a^{n-1} \equiv 1 \pmod{n}$ for every $a$ with $\gcd(a, n) = 1$. The Fermat test gives the wrong answer for all witnesses simultaneously. The smallest example is $561 = 3 \times 11 \times 17$.

Why 561 is a Carmichael number. By Korselt’s criterion, a squarefree composite $n$ is Carmichael iff $(p-1) \mid (n-1)$ for every prime $p \mid n$. For $n = 561$: $n - 1 = 560$. Check: $2 \mid 560$, $10 \mid 560$, $16 \mid 560$. All hold. So for any $a$ coprime to $561$: $a^2 \equiv 1 \pmod 3$, $a^{10} \equiv 1 \pmod{11}$, $a^{16} \equiv 1 \pmod{17}$, and since $560 = 280 \cdot 2 = 56 \cdot 10 = 35 \cdot 16$, we get $a^{560} \equiv 1$ mod each prime factor, hence mod $561$.

There are infinitely many Carmichael numbers (proved by Alford, Granville, and Pomerance in 1994). The Fermat test is not sufficient for rigorous primality proofs. The Miller-Rabin test (covered in the primality testing post) fixes this.

Summary

Theorem Statement Proof idea
Fermat’s little theorem $a^{p-1} \equiv 1 \pmod p$ for prime $p$, $p \nmid a$ Multiplying by $a$ permutes $\{1, \ldots, p-1\}$; products equal
Wilson’s theorem $(p-1)! \equiv -1 \pmod p$ iff $p$ prime Elements pair with inverses; only $\pm 1$ are self-inverse
Totient $\varphi(n)$ Count of integers in $[1, n]$ coprime to $n$ $\varphi(p) = p-1$, $\varphi(pq) = (p-1)(q-1)$, multiplicative
Euler’s theorem $a^{\varphi(n)} \equiv 1 \pmod n$ when $\gcd(a,n)=1$ Lagrange on $(\mathbb{Z}/n\mathbb{Z})^\times$
RSA correctness $m^{ed} \equiv m \pmod n$ $ed = 1 + k\varphi(n)$, apply Euler’s theorem
Carmichael numbers Composites that fool the Fermat test $(p-1) \mid (n-1)$ for all prime factors $p$

Read next: