Wilson’s Theorem

Wilson’s theorem gives a characterisation of the prime numbers, with a surprisingly short and elegant proof.

Statement

Wilson’s theorem. An integer \(n>1\) is prime if and only if

\[(n-1)! \equiv -1 \pmod{n},\]

that is, if and only if \(n\) divides \((n-1)!+1\).

We prove the two directions separately. Most of the work is in showing that every prime \(p\) satisfies \((p-1)! \equiv -1 \pmod p\).

Primes satisfy Wilson’s congruence

Let \(p\) be prime.

Inverses modulo \(p\)

The residue classes modulo \(p\) form a field, so every non-zero residue \(a\) has a unique multiplicative inverse \(a^*\), with \(a\, a^* \equiv 1 \pmod{p}\).

Which residues are their own inverse?

If \(a=a^*\), then \(a^2 \equiv 1 \pmod{p}\), that is,

\[p \mid a^2-1 = (a-1)(a+1).\]

Since \(p\) is prime, it divides one of the factors, so

\[a \equiv \pm 1 \pmod{p}.\]

So the only residues equal to their own inverse are \(1\) and \(p-1\).

Pairing off

Now consider

\[(p - 1)! = 1 \times 2 \times 3 \times \cdots \times (p - 2) \times (p - 1).\]

Each factor other than \(1\) and \(p-1\) can be paired with its inverse, which is a different factor in the product, and each pair multiplies to \(1\). What remains is \(1 \times (p-1) \equiv -1 \pmod p\).

For example, with \(p = 13\):

\[\begin{aligned} 12! & = 1 \times 2 \times 3 \times 4 \times 5 \times 6 \times 7 \times 8 \times 9 \times 10 \times 11 \times 12 \\ & = 1 \times (2 \times 7) \times (3 \times 9) \times (4 \times 10) \times (5 \times 8) \times (6 \times 11) \times 12 \\ & \equiv 1 \times 1 \times 1 \times 1 \times 1 \times 1 \times 12 \\ & \equiv 12 \equiv -1 \pmod{13}. \end{aligned}\]

Therefore \((p-1)! \equiv -1 \pmod p\) for every prime \(p\).

Composites do not

If \(n > 4\) is composite, write \(n = ab\) with \(1 < a \le b < n\). If \(a < b\), both \(a\) and \(b\) appear in \((n-1)!\), so \(n \mid (n-1)!\). If \(a = b\), then \(n = a^2\) with \(a > 2\), and both \(a\) and \(2a\) appear (since \(2a < a^2\)), so again \(n \mid (n-1)!\). Either way \((n-1)! \equiv 0 \not\equiv -1 \pmod n\). Finally, for \(n = 4\), \(3! = 6 \equiv 2 \pmod 4\). \(\blacksquare\)

Credits

I was inspired by the video below

and by these notes.

Exercises

• Show that if \(p\) is prime and \(p \mid ab\), then \(p \mid a\) or \(p \mid b\).
• Define an equivalence class. Show that the residue classes modulo a prime \(p\) form a field.
• Is Wilson’s theorem useful as a primality test? Why or why not?

Changes on 25 October 2026

What was wrong. In the example for \(p = 13\), the numbers were paired as (2, 6), (3, 4), (5, 9), (7, 8) and (10, 11), but none of these are inverse pairs modulo 13: for instance \(2 \times 6 = 12\). The correct pairs are (2, 7), (3, 9), (4, 10), (5, 8) and (6, 11).

What changed. The pairs are corrected and the proof is written out more carefully.