Wilson's Theorem

⚡ Key Takeaways

Wilson's Theorem: An integer $p > 1$ is prime if and only if $(p-1)! \equiv -1 \pmod{p}$ . In words, the product of all positive integers less than a number is one short of a multiple of that number exactly when the number is prime. It applies throughout elementary number theory, modular arithmetic, and primality characterization. Conjectured by Ibn al-Haytham (~1000 CE), stated by John Wilson (1770), and first proved by Joseph-Louis Lagrange (1771).

💡 The Core Insight

In the multiplicative group of nonzero residues mod a prime $p$ , almost every element can be paired with its distinct multiplicative inverse, so those pairs multiply to $1$ . The only elements equal to their own inverse are $1$ and $p-1 \equiv -1$ . Hence the entire product $(p-1)!$ collapses to $1 \cdot (-1) \cdot (\text{bunch of 1's}) = -1$ . For composites this pairing structure breaks because inverses don't always exist.

DefinitionWilson's Theorem

Let $p$ be an integer with $p > 1$ . Then $p$ is prime if and only if

1

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

Derivation hint: Read $(p-1)! = 1 \cdot 2 \cdot 3 \cdots (p-1)$ as a product taken in the ring $\mathbb{Z}/p\mathbb{Z}$ ; the claim is that this product equals the residue class $-1 \equiv p-1$ . Here:

$p$ is the candidate integer;
$(p-1)! = 1 \cdot 2 \cdots (p-1)$ is the factorial of $p-1$ ;
$\equiv \pmod p$ denotes congruence modulo $p$ , i.e. $p \mid \big[(p-1)! + 1\big]$ .

Equivalently, the divisibility statement is

2

\quad p \mid (p-1)! + 1 \iff p \text{ is prime}.

Derivation hint: $a \equiv -1 \pmod p$ means $p \mid (a+1)$ ; apply with $a = (p-1)!$ .

TheoremConverse / Composite Case

If $n > 1$ is composite, then

3

\quad (n-1)! \equiv \begin{cases} 0 \pmod n, & n \neq 4, \\ 2 \pmod 4, & n = 4. \end{cases}

Derivation hint: For composite $n > 4$ , both factors of any factorization $n = ab$ (and enough multiples) appear among $1,\dots,n-1$ , so $n \mid (n-1)!$ . The number $4$ is the lone exception because its only proper factor $2$ appears just once below $4$ . In particular no composite $n$ satisfies $(n-1)! \equiv -1 \pmod n$ , which is what makes Wilson's Theorem an exact primality test.

Figure

Pairing of inverses mod 11: each element joins its distinct inverse, leaving 1 and 10 self-paired

Why It Holds / Derivation

ProofConverse: the congruence fails for composites

Suppose $n > 1$ satisfies $(n-1)! \equiv -1 \pmod n$ , and suppose for contradiction $n$ is composite. Let $d$ be a proper divisor with $1 < d < n$ . Then $d$ appears as one of the factors $1, 2, \dots, n-1$ , so $d \mid (n-1)!$ . But $d \mid n$ and $n \mid (n-1)! + 1$ force $d \mid (n-1)! + 1$ . Subtracting, $d \mid 1$ , a contradiction since $d > 1$ . Hence $n$ is prime. For the explicit composite values in $[3]$ : if $n > 4$ is composite, write $n = ab$ with $1 < a \le b < n$ . If $a \neq b$ both appear separately in $(n-1)!$ , so $n = ab \mid (n-1)!$ . If $a = b$ (so $n = a^2$ ), then since $n > 4$ we have $a > 2$ , and both $a$ and $2a$ are distinct factors below $n$ , giving $a \cdot 2a = 2a^2 = 2n$ , so again $n \mid (n-1)!$ . The case $n = 4$ gives $3! = 6 \equiv 2 \pmod 4$ . ∎

∎

mathematician · Joseph-Louis Lagrange | 1736–1813

Though the result bears John Wilson's name (Wilson stated it without proof, reportedly relayed by his teacher Edward Waring in 1770), the first rigorous proof was published by Joseph-Louis Lagrange in 1771. Lagrange proved it as a corollary of his deep work on the number of roots of polynomial congruences modulo a prime — establishing that a degree- $d$ polynomial has at most $d$ roots mod $p$ . He even derived both Wilson's Theorem and Fermat's Little Theorem together from this polynomial framework. Lagrange, a towering figure of 18th-century mathematics, made foundational contributions to number theory, the calculus of variations, and analytical mechanics.

🧠 Intuition

Think of $\{1, 2, \dots, p-1\}$ as a dance floor where everyone must pair with their unique "inverse partner" (the person they multiply with to give $1$ ). Because $p$ is prime, everyone has exactly one partner — no one is left without a match, and no two people share a partner. Two people are their own partner: the identity $1$ (trivially) and $p-1 \equiv -1$ (since $(-1)^2 = 1$ ). Everyone else dances in genuine couples, and each couple "cancels" to $1$ . So the grand product is just the two wallflowers: $1 \times (-1) = -1$ . For a composite $n$ , the floor is broken: some elements have no inverse at all (those sharing a factor with $n$ ), so the clean pairing collapses, and the product instead gets dragged down to $0$ because the composite's factors are all sitting in the product waiting to assemble $n$ itself.

ExampleVerifying Wilson for

p = 7

Given: $p = 7$ (prime). Compute $(7-1)! = 6! \pmod 7$ .

Steps: 1. $6! = 720$ . 2. Reduce step by step to avoid big numbers:

$1 \cdot 2 = 2$
$2 \cdot 3 = 6$
$6 \cdot 4 = 24 \equiv 3 \pmod 7$
$3 \cdot 5 = 15 \equiv 1 \pmod 7$
$1 \cdot 6 = 6 \equiv -1 \pmod 7$

3. Check pairing: inverses mod 7 are $2\cdot4=8\equiv1$ , $3\cdot5=15\equiv1$ . Self-inverses are $1$ and $6$ .

Answer: $\boxed{6! \equiv -1 \pmod 7}$ — confirming $7$ is prime.

ExampleWilson fails for composite

n = 9

Given: $n = 9$ (composite, $= 3^2$ ). Compute $(9-1)! = 8! \pmod 9$ .

Steps: 1. The factor $3$ and the factor $6$ both appear in $8! = 1\cdot2\cdots8$ . 2. Their product $3 \cdot 6 = 18 = 2 \cdot 9$ is already a multiple of $9$ . 3. Therefore $9 \mid 8!$ , so $8! \equiv 0 \pmod 9$ . 4. Since $0 \not\equiv -1 \equiv 8 \pmod 9$ , the Wilson congruence fails.

Answer: $\boxed{8! \equiv 0 \pmod 9 \neq -1}$ — correctly flagging $9$ as composite (consistent with equation $[3]$ ).

⚠️ Common mistake

Wilson's Theorem is NOT a practical primality test. Computing $(p-1)!$ requires $\sim p$ multiplications, which is exponential in the number of digits of $p$ . For real primality testing one uses Fermat's Little Theorem-based tests, the Miller–Rabin test, or AKS. Wilson's Theorem is theoretically perfect but computationally hopeless for large $p$ .

Do not confuse the directions. Some students remember only " $(p-1)! \equiv -1$ for primes" and forget that the converse also holds — composites never satisfy it (except the $n=4$ residue quirk, which still gives $2$ , not $-1$ ). The biconditional is the whole point.

Counterexample

A tempting false analogy: One might guess that $(n-1)! \equiv -1 \pmod n$ has "near misses" for composites, like Fermat pseudoprimes do for Fermat's Little Theorem. It does not. Take $n = 15$ : the factors $3$ and $5$ both lie in $14!$ , so $15 \mid 14!$ , giving $14! \equiv 0 \pmod{15}$ , nowhere near $-1 \equiv 14$ . There are no "Wilson pseudoprimes" — the test has zero false positives. (Separately, a Wilson prime is a much rarer beast: a prime $p$ with $(p-1)! \equiv -1 \pmod{p^2}$ ; only $5, 13, 563$ are known.)

connection

Wilson's Theorem sits in a tight web of elementary number theory:

<a class="wiki-link" href="/wiki/math-numthy-fermat-little-theorem">Fermat's Little Theorem</a> — both follow from the group structure of $(\mathbb{Z}/p\mathbb{Z})^\times$ and were proved together by Lagrange; Fermat says $a^{p-1}\equiv 1$ , Wilson is the product over all $a$ .
Lagrange's Theorem on Polynomial Congruences — a degree- $d$ polynomial mod $p$ has at most $d$ roots; applying this to $x^{p-1}-1$ yields Wilson by comparing constant terms.
Group Theory — Wilson generalizes: in any finite abelian group, the product of all elements equals the product of elements of order $\le 2$ (the identity unless there is a unique element of order 2).
Gauss's Generalization — the product of the units mod $n$ is $-1$ if $n \in \{4, p^k, 2p^k\}$ and $+1$ otherwise.
Quadratic Residues — Wilson's Theorem yields the value of $\big(\frac{-1}{p}\big)$ and Wolstenholme-type identities.

🔬 Where this appears

⏳ History

- ~1000 CE — Ibn al-Haytham (Alhazen) implicitly states the result in his study of congruences, the earliest known appearance.

- 1770 — John Wilson, a student of Edward Waring, conjectures the theorem; Waring publishes it in Meditationes Algebraicae without proof, remarking that proofs may be difficult because there is no good notation for primes.

- 1771 — Joseph-Louis Lagrange publishes the first proof, derived from his theory of polynomial congruences, and notes the converse.

- 1773 — Leonhard Euler gives an alternative proof using primitive roots and the structure of

(\mathbb{Z}/p\mathbb{Z})^\times

.

- 1801 — Carl Friedrich Gauss, in Disquisitiones Arithmeticae, presents Wilson's Theorem and its generalization to the product of units mod

n

for arbitrary

n

.

- 1828 — Gauss's generalization is fully worked into mainstream number theory, clarifying the cases

4, p^k, 2p^k

.

- 1862 — Joseph Wolstenholme proves related higher-order congruences; the notion of Wilson primes (satisfying the congruence mod

p^2

) emerges from this lineage.

- 1900s–present — Computational searches identify the only three known Wilson primes:

5, 13, 563

; none exist below

2 \times 10^{13}

, deepening the mystery of their distribution.

open-problem

The Wilson prime mystery. A prime $p$ is a Wilson prime if it satisfies the stronger congruence

8

\quad (p-1)! \equiv -1 \pmod{p^2}.

Derivation hint: This strengthens equation $[1]$ from modulus $p$ to modulus $p^2$ , requiring $p^2 \mid (p-1)! + 1$ rather than merely $p \mid (p-1)! + 1$ . Only three are known: $5, 13, 563$ . Heuristic arguments (modeling $\frac{(p-1)!+1}{p} \bmod p$ as uniformly random) predict there should be infinitely many, with roughly $\log\log X$ of them below $X$ — an excruciatingly slow growth that explains why so few are found. It is unknown whether there are infinitely many Wilson primes, and it is even unknown whether there are infinitely many non-Wilson primes (though the latter is widely believed). Extensive searches confirm no fourth Wilson prime exists up to about $2 \times 10^{13}$ . This remains a genuinely open problem at the intersection of elementary and analytic number theory.

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also