Wilson's Theorem

The statement

For any integer n > 1:

n is prime  ⟺  (n − 1)! ≡ −1 (mod n)

Or equivalently, n divides (n − 1)! + 1 iff n is prime.

This is a genuine if-and-only-if. Many primality results are one-way (primes satisfy property P, but some composites also satisfy P — Fermat's test is famously fooled by Carmichael numbers). Wilson's theorem is tight: the factorial test never misclassifies in either direction.

Worked example — primality of 7 (and contrast with 9)

Compute (7 − 1)! = 6! = 720. Reduce mod 7:

720 = 7 · 102 + 6
720 mod 7 = 6 = -1 (mod 7)  ✓ — 7 is prime.

And in full pairing form:

6! mod 7 = 1 · 2 · 3 · 4 · 5 · 6  (mod 7)
         = 1 · (2 · 4) · (3 · 5) · 6
         = 1 · 8 · 15 · 6  (mod 7)
         = 1 · 1 · 1 · 6  (mod 7)        ← inverse pairs collapse to 1
         = 6 ≡ -1 (mod 7)  ✓

Notice 2 · 4 = 8 ≡ 1 (mod 7), so 2 and 4 are inverses. Similarly 3 · 5 = 15 ≡ 1 (mod 7). Only 1 and 6 ≡ −1 pair with themselves. Product collapses to −1. This is the whole proof in miniature.

Now check n = 9 (composite):

8! = 40320
40320 mod 9: 40320 / 9 = 4480 exactly. So 40320 ≡ 0 (mod 9).
Not −1, not even close. 9 is composite — confirmed.

For composite n > 4, (n−1)! always contains enough of n's factors to make it divisible by n — so (n−1)! ≡ 0, not −1. (The lone exception is n = 4: 3! = 6 ≡ 2 (mod 4), neither 0 nor −1.)

Why pairing works (proof sketch)

Let p be prime. Consider the group (ℤ/pℤ)* — the nonzero elements 1, 2, …, p − 1 under multiplication mod p. We want to compute their product. Group it cleverly:

1. Each element x has a unique inverse x⁻¹ (mod p) — because gcd(x, p) = 1 for x ∈ {1, 2, …, p − 1}.
2. Inverses pair up. If x · x⁻¹ ≡ 1 and y = x⁻¹, then y · y⁻¹ = y · x = 1 too — same pair.
3. The only self-paired elements are ±1. If x = x⁻¹, then x² ≡ 1 (mod p), so (x − 1)(x + 1) ≡ 0 (mod p). Since p is prime, x ≡ ±1.

So the product 1 · 2 · 3 · … · (p − 1) splits into:

(p − 1)! ≡ 1 · (p − 1) · ∏(inverse pairs)  (mod p)
        ≡ 1 · (-1) · 1 · 1 · ... · 1
        ≡ -1  (mod p)

The converse — if (n − 1)! ≡ −1 (mod n) then n is prime — is short. Suppose n is composite. Then n has a factor 1 < d < n, so d divides (n − 1)! (because d appears as one of the factors 1, 2, …, n − 1). Therefore d divides (n − 1)! and also divides n, so d divides ((n − 1)! mod n). For (n − 1)! ≡ −1 (mod n), we'd need d to divide −1 — impossible for d > 1. So no composite satisfies the congruence.

JavaScript — verify Wilson's theorem

// Slow direct check — only works for small n
function wilsonTest(n) {
  if (n <= 1) return false;
  if (n === 2) return true;
  let fact = 1n;
  const N = BigInt(n);
  for (let i = 1n; i < N; i++) {
    fact = (fact * i) % N;
  }
  return fact === N - 1n;  // ≡ -1 (mod n)
}

// Check primes 2..20
for (let n = 2; n <= 20; n++) {
  console.log(n, wilsonTest(n));
}
// 2 true, 3 true, 4 false, 5 true, 6 false, 7 true, 8 false, 9 false,
// 10 false, 11 true, 12 false, 13 true, ... — matches primes exactly.

// Wilson prime check: p² | (p−1)! + 1
function isWilsonPrime(p) {
  if (!wilsonTest(p)) return false;
  let fact = 1n;
  const P = BigInt(p);
  for (let i = 1n; i < P; i++) fact = (fact * i) % (P * P);
  return (fact + 1n) % (P * P) === 0n;
}

isWilsonPrime(5);    // true
isWilsonPrime(13);   // true
isWilsonPrime(563);  // true (but slow — 562 multiplications mod 563²)
isWilsonPrime(7);    // false

Variants and comparison

Primality test	Type	Iff?	Cost	Practical?
Wilson's theorem	Algebraic identity	Yes — exact characterization	O(n log² n)	No — factorial growth
Fermat's little theorem	Algebraic identity	No — Carmichael numbers fool it	O(log³ n)	Yes — but only as a screen
Trial division	Direct factor search	Yes	O(√n)	Up to n ~ 10¹²
Miller-Rabin	Probabilistic + square-root check	Yes (probabilistically)	O(k · log³ n)	Yes — RSA standard
AKS (2002)	Deterministic, polynomial	Yes	O(log⁶ n)	Asymptotic, not practical
Lucas-Lehmer (Mersenne)	Specific to 2^p − 1	Yes, for Mersenne form	O(p² log p log log p)	Yes — GIMPS uses it
Wilson generalized (Gauss)	Product of group units	Yes — characterizes (ℤ/nℤ)*	Ω(φ(n))	No — same factorial-blowup problem

Common pitfalls

• Trying to use Wilson as a real primality test. (n−1)! has n log n digits. Even modular reduction during multiplication is O(log² n) per step, totalling Ω(n log² n) — exponentially slower than Miller-Rabin's O(log³ n). Wilson is a theorem, not a tool.
• Forgetting the converse. Some sources state only "prime ⇒ factorial ≡ −1". Wilson is an iff; the converse needs the divisibility argument for composites.
• n = 4 exception trap. 3! = 6 ≡ 2 (mod 4), neither 0 nor −1. The clean statement "composite ⇒ (n−1)! ≡ 0" fails here. It works for all composite n > 4 because n then has > 1 distinct factors below it, and they accumulate.
• Misnaming. Wilson never proved Wilson's theorem. Lagrange did. Ibn al-Haytham conjectured it 700 years earlier. The Eurocentric naming has stuck.
• Confusing with Wilson's primes. Wilson's theorem holds for all primes. Wilson primes are the very rare p satisfying p² | (p−1)! + 1 — only 5, 13, 563 known despite exhaustive search to p < 2 · 10¹³.
• Believing it generalizes simply to composites. Gauss's generalization works for (ℤ/nℤ)*, but the product equals −1 only when n is 1, 2, 4, p^k, or 2p^k; otherwise +1. The classical Wilson is the p^k with k = 1 case.

Applications

• Number-theoretic proofs. Wilson's theorem appears in proofs of Fermat's theorem on sums of two squares, the four-squares theorem, and in deriving properties of quadratic residues.
• Mathematical olympiads. Standard tool in IMO and Putnam problems on factorials mod primes — knowing the inverse-pairing trick unlocks many problems.
• Wilson-prime hunting. Distributed-computing projects have checked p < 2 · 10¹³; no fourth Wilson prime has been found. Open conjecture: infinite Wilson primes; heuristic density log log p / p.
• Formal verification. Proof assistants (Coq, Lean) include Wilson's theorem in their number-theory libraries as a foundational result for deeper algebraic number theory.
• Pedagogy. The inverse-pairing proof is the cleanest entry to thinking about multiplicative groups (ℤ/pℤ)* as cyclic objects — sets the stage for primitive roots, quadratic residues, Fermat's little theorem, and group theory more broadly.
• Combinatorial identities mod primes. Wilson plus Fermat give clean formulas for binomial coefficients and Stirling numbers reduced mod p — used in Lucas's theorem and generating functions.

History

The result is named for John Wilson, an English mathematician who studied with Edward Waring in the 1760s. Waring stated the theorem in Meditationes Algebraicae (1770), crediting his student Wilson with the conjecture. Neither could prove it.

Joseph-Louis Lagrange supplied the first proof in 1771, using exactly the inverse-pairing argument now standard. But the result had been known much earlier — Ibn al-Haytham (Alhazen) stated and used it around 1000 CE in his work on algebra and number theory. So "Wilson's theorem" predates Wilson by seven centuries and Waring by eight.

Gauss later generalized the theorem to ℤ/nℤ — the product of all units of ℤ/nℤ is −1 iff n is 1, 2, 4, p^k, or 2p^k for odd prime p, and +1 otherwise.