Wilson's Theorem

Wilson's Theorem gives a clean, exact (if-and-only-if) characterization of primality in terms of a factorial congruence. Whereas Fermat's Little Theorem gives a one-directional test that primes pass but some composites also pass (pseudoprimes), Wilson's Theorem fails for every composite, making it a true primality criterion. The surprising fact is that this perfect test exists at all and is so simple to state — yet it is computationally useless for large numbers because computing $(p-1)!$ is far slower than other primality tests. The theorem hinges on the elegant structure of $\mathbb{Z}/p\mathbb{Z}$ as a field, in which elements pair up with their multiplicative inverses, leaving only the self-inverse elements $1$ and $-1$ unpaired in the giant product.

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.

Formal Statement

Wilson's Theorem

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

Here:

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

Equivalently, the divisibility statement is

Converse / Composite Case

If $n>1$ is composite, then

In particular no composite $n$ satisfies $(n-1)!\equiv -1(\mathrm{mod}n)$, which is what makes Wilson's Theorem an exact primality test.

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

Why It Holds / Derivation

proof[Prime Case: $(p-1)!\equiv -1(\mathrm{mod}p)$] Assume $p$ is prime. We work in the field $\mathbb{Z}/p\mathbb{Z}$.

So only $a=1$ and $a=p-1$ ($\equiv -1$) satisfy $a=a^{-1}$.

This proves the forward direction. ∎

Converse: the congruence fails for composites

Suppose $n>1$ satisfies $(n-1)!\equiv -1(\mathrm{mod}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\ne 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(\mathrm{mod}4)$. ∎

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.

Building 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.

Worked Examples

Verifying Wilson for $p = 7$

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

1. Check pairing: inverses mod 7 are $2\cdot 4=8\equiv 1$, $3\cdot 5=15\equiv 1$. Self-inverses are $1$ and $6$.

Wilson fails for composite $n = 9$

1. The factor $3$ and the factor $6$ both appear in $8!=1\cdot 2\cdots 8$.
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(\mathrm{mod}9)$.
4. Since $0\not\equiv -1\equiv 8(\mathrm{mod}9)$, the Wilson congruence fails.

Common Misconceptions

Connections

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

• Fermat's Little Theorem — 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 $\left(\frac{-1}{p}\right)$ and Wolstenholme-type identities.

Real-World Applications

While primarily theoretical, Wilson's Theorem and its ideas surface in several concrete contexts:

1. Primality proofs in textbooks and competition mathematics — a standard tool for olympiad problems requiring an exact primality characterization.
2. Deriving the value of $(p-1)/2)!$ mod $p$ — used to compute square roots of $-1$ modulo primes $p\equiv 1(\mathrm{mod}4)$, relevant in Quadratic Residues and the Tonelli–Shanks algorithm.
3. Wilson primes search — distributed computing projects test the rare congruence $(p-1)!\equiv -1(\mathrm{mod}{p}^2)$, probing the boundary of analytic number theory predictions.
4. Generating primes in formulas — Wilson's Theorem underlies "prime-producing" formulas (e.g. via the floor function), of theoretical/recreational interest.
5. Cryptographic pedagogy — used to introduce modular inverse structure of $(\mathbb{Z}/p\mathbb{Z}{)}^{\times }$ before RSA and Diffie–Hellman.
6. Combinatorial identities — appears in evaluating products and binomial coefficients modulo primes (e.g. Lucas-type congruences).
7. Verification of finite field arithmetic — sanity-checking implementations of modular multiplication by confirming $(p-1)!\equiv -1$.

Historical Development

• ~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.

Subtleties & Limits

Only three are known: $5,13,563$. Heuristic arguments (modeling $\frac{(p-1)!+1}{p}\mathrm{mod}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.

See Also