Wilson's Theorem — Mathematics Knowledge System

Overview

Wilson's theorem says that an integer p > 1 is prime exactly when (p−1)! ≡ −1 (mod p). The statement is named for John Wilson, a student of Edward Waring who conjectured it in 1770 (Waring published it without proof); Lagrange gave the first proof in 1771, and there is evidence Leibniz knew the result nearly a century earlier. What makes it striking is that it is an if-and-only-if characterization of primality purely in terms of a factorial residue — no composite number can satisfy it, so in principle it is a primality test. In practice it is useless computationally, because computing (p−1)! mod p is far slower than trial division or modern probabilistic tests, but the theorem is a genuine gem of elementary number theory and a useful lemma in proofs (for instance, in results about primes of the form 4k+1 being a sum of two squares).

Intuition

Pair up the residues 1, 2, …, p−1 modulo an odd prime p with their multiplicative inverses. Every residue except 1 and p−1 (≡ −1) pairs with a genuinely different partner, because x ≡ x⁻¹ (mod p) forces x² ≡ 1, which only has the solutions x ≡ ±1 when p is prime. So the product (p−1)! splits into (p−3)/2 pairs that each multiply to 1, plus the two leftover terms 1 and p−1 ≡ −1. Multiplying everything together, the pairs vanish (contribute factors of 1) and only 1·(−1) = −1 survives, giving (p−1)! ≡ −1 (mod p). If p were composite with p > 4, some smaller factor of p would already appear as one of the terms 1, …, p−1, making the whole product divisible by p — i.e. ≡ 0, not −1 — which is why the theorem pins down primality exactly.

Formal Definition

Definition

For an integer p > 1, p is prime if and only if:

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

Wilson's theorem

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

Equivalent form (since -1 \equiv p-1)

n \text{ composite}, \ n > 4 \ \Rightarrow\ (n-1)! \equiv 0 \pmod{n}

Converse-adjacent fact for composite n > 4

Worked Examples

Compute the factorial.
$6! = 720$
Reduce 720 modulo 7.
$720 = 102 \cdot 7 + 6$
6 ≡ −1 (mod 7), confirming Wilson's theorem for p = 7.
$720 \equiv -1 \pmod{7}$

Answer: 6! ≡ −1 (mod 7). ✓

Practice Problems

Difficulty 3/10

Compute 24 mod 5.

Difficulty 6/10

Explain why (n−1)! mod n cannot be −1 when n = 8 (a composite number), without fully computing 7!.

Difficulty 5/10

Using Wilson's theorem, state the value of 10! mod 11 without direct computation, then verify by computing 10! mod 11 directly.

Quiz

Summary

(p−1)! ≡ −1 (mod p) holds exactly when p is prime — an if-and-only-if characterization of primality.
The proof pairs each residue with its modular inverse; only 1 and −1 are unpaired, so their product −1 survives.
For composite n > 4, (n−1)! ≡ 0 (mod n) instead, since n's smaller factors already appear in the product.

References

WebsiteWikipedia — Wilson's theorem