Wilson's theorem

Theorem

Wilson's theorem

T-077Home MU-207Threads number

Statement

Let \( n \in \mathbb{N} \) with \( n \geq 2 \). Then \( n \) is prime if and only if \[ (n-1)! \equiv -1 \pmod{n}. \] Equivalently, writing \( p \) for a candidate prime: \( p \) is prime exactly when \( (p-1)! + 1 \) is divisible by \( p \). The statement is an "if and only if": both the forward direction (primality implies the congruence) and the converse (the congruence implies primality) hold, which is what makes Wilson's theorem usable as a primality criterion in principle.

Why it matters

Wilson's theorem is the first result a student meets in which a purely multiplicative statement about the group \( (\mathbb{Z}/n\mathbb{Z})^\times \) is converted into a clean numerical congruence, by pairing each unit with its inverse. The proof technique — pairing elements of a finite abelian group with their inverses and isolating the "self-paired" elements — recurs throughout algebra and number theory, from the classification of self-inverse elements in Sylow theory arguments to Gauss's own use of the theorem in his study of quadratic residues.

The theorem also matters because it is a genuine (if computationally useless) primality test: unlike Fermat's little theorem, which only gives a necessary condition for primality, Wilson's theorem gives a necessary and sufficient one. This logical strength — and the fact that \( (n-1)! \) grows too fast to compute for testing large \( n \) — makes it a favourite illustration of the gap between theoretical characterisations and practical algorithms.

Hypotheses

\( n \geq 2 \) is a fixed integer.Without this the statement is vacuous or ill-posed: for \( n = 1 \), \( (n-1)! = 0! = 1 \equiv 0 \pmod 1 \), and every integer is \( \equiv 0 \pmod 1 \), so the congruence \( (n-1)! \equiv -1 \) holds trivially while \( n=1 \) is neither prime nor composite by convention — the theorem is simply not asserted at \( n=1 \). Arithmetic is performed modulo \( n \), i.e. in \( \mathbb{Z}/n\mathbb{Z} \).The result is a genuinely modular statement, not an equality of integers: \( (p-1)! \) itself is far larger than \( p \) for \( p \geq 5 \) (e.g. \( 4! = 24 \neq -1 \) as integers), so working in the ring \( \mathbb{Z}/n\mathbb{Z} \) rather than in \( \mathbb{Z} \) is essential to the statement even making sense as claimed. The converse direction requires \( n \) composite (not prime) to produce a different residue, and relies on \( n \) having a proper nontrivial factorisation when \( n \gt 4 \).The composite case \( n = 4 \) must be checked separately from the argument used for other composites, because \( 4 = 2^2 \) has no factorisation into two distinct factors both less than \( 4 \) and greater than \( 1 \); indeed \( 3! = 6 \equiv 2 \pmod 4 \), not \( 0 \), so the generic composite argument (which produces \( (n-1)! \equiv 0 \)) needs amending exactly at \( n=4 \).

Proof

Direction 1: \( p \) prime \( \implies (p-1)! \equiv -1 \pmod p \).

Assume \( p \) is prime. The small cases \( p=2 \) and \( p=3 \) are checked directly: \( (2-1)! = 1! = 1 \equiv -1 \pmod 2 \); \( (3-1)! = 2! = 2 \equiv -1 \pmod 3 \).

Direct computation; these serve as base cases and also to sidestep degenerate group-theoretic arguments below where \( (\mathbb{Z}/p\mathbb{Z})^\times \) has fewer than \( 3 \) elements. A

Now fix a prime \( p \geq 5 \). Since \( p \) is prime, \( \mathbb{Z}/p\mathbb{Z} \) is a field, so every nonzero residue class has a multiplicative inverse: \( (\mathbb{Z}/p\mathbb{Z})^\times = \{1,2,\dots,p-1\} \) is a group of order \( p-1 \) under multiplication modulo \( p \).

Definition of field / unit group; every nonzero element of a field has a multiplicative inverse. A

For \( a \in (\mathbb{Z}/p\mathbb{Z})^\times \), the equation \( a \cdot x \equiv 1 \pmod p \) has a unique solution \( x = a^{-1} \) in \( (\mathbb{Z}/p\mathbb{Z})^\times \). Determine for which \( a \) we have \( a = a^{-1} \), i.e. \( a^2 \equiv 1 \pmod p \).

Uniqueness of inverses in a group; we now classify self-inverse elements. B

\( a^2 \equiv 1 \pmod p \iff p \mid (a-1)(a+1) \iff p \mid a-1 \text{ or } p \mid a+1 \) (since \( p \) is prime, it is irreducible, so Euclid's lemma applies), giving \( a \equiv 1 \) or \( a \equiv -1 \equiv p-1 \pmod p \).

Euclid's lemma: a prime dividing a product divides one of the factors. This uses primality of \( p \) essentially. B

Hence exactly two elements of \( (\mathbb{Z}/p\mathbb{Z})^\times \) are self-inverse, namely \( 1 \) and \( p-1 \); every other element \( a \in \{2,\dots,p-2\} \) is paired with a distinct partner \( a^{-1} \neq a \) also lying in \( \{2,\dots,p-2\} \).

Follows from Step 4 together with uniqueness of inverses (Step 3): the map \( a \mapsto a^{-1} \) is an involution on \( \{2,\dots,p-2\} \) with no fixed points. B

The set \( \{2,3,\dots,p-2\} \) has \( p-3 \) elements, an even number, and partitions into \( \frac{p-3}{2} \) disjoint pairs \( \{a, a^{-1}\} \) with \( a \cdot a^{-1} \equiv 1 \pmod p \) for each pair.

A fixed-point-free involution on a finite set partitions it into 2-element orbits (this is the orbit-counting fact underlying the pairing argument). C

\[ \prod_{a=2}^{p-2} a \equiv \prod_{\text{pairs}} (a \cdot a^{-1}) \equiv \prod_{\text{pairs}} 1 \equiv 1 \pmod p. \]

Multiplying the pairing of Step 6 collapses the product to \( 1 \), since each factor of the product is regrouped exactly once by the partition. B

\[ (p-1)! = 1 \cdot \Big(\prod_{a=2}^{p-2} a\Big) \cdot (p-1) \equiv 1 \cdot 1 \cdot (p-1) \equiv -1 \pmod p. \]

Substitute Step 7 and the fact \( p - 1 \equiv -1 \pmod p \); this completes the forward direction for \( p \geq 5 \), and combined with Step 1 for \( p=2,3 \) proves the direction for all primes. A

Direction 2 (converse): \( (n-1)! \equiv -1 \pmod n \implies n \) is prime.

Suppose, for contradiction, \( n \geq 2 \) is composite and \( (n-1)! \equiv -1 \pmod n \). Since \( n \) is composite, write \( n = ab \) with \( 1 \lt a \leq b \lt n \).

Definition of composite: a positive integer \( \gt 1 \) that is not prime has a nontrivial factorisation. A

Case \( a \lt b \): both \( a \) and \( b \) are distinct integers in \( \{1,\dots,n-1\} \), hence both appear as separate factors in the product \( (n-1)! = 1 \cdot 2 \cdots (n-1) \), so \( ab = n \mid (n-1)! \), i.e. \( (n-1)! \equiv 0 \pmod n \).

Direct inspection of which integers occur as factors of the factorial; uses \( a \neq b \) to guarantee they are two separate terms of the product. B

Case \( a = b \), i.e. \( n = a^2 \): if \( a \gt 2 \) then \( a\), \(2a \) are two distinct integers, both \( \leq a^2 - 1 = n-1\) (since \(2a \le a^2-1 \) once \(a\ge3\)), so again both \( a \) and \( 2a \) occur as separate factors in \( (n-1)! \), giving \( a \cdot 2a = 2a^2 = 2n \mid (n-1)! \), hence \( n \mid (n-1)! \), so \( (n-1)! \equiv 0 \pmod n \). If \( a = 2 \) (so \( n=4 \)) this bound fails and is treated separately in Step 12.

Same factor-inspection idea as Step 10, adapted to the repeated-factor case; the inequality \( 2a \leq a^2-1 \) for \( a \geq 3 \) is checked by elementary algebra (\(a^2-2a-1\ge 0 \) for \(a\ge3\)). C

For \( n = 4 \): direct computation gives \( 3! = 6 \equiv 2 \pmod 4 \), so \( (n-1)! \not\equiv -1 \pmod 4 \) (since \( -1 \equiv 3 \pmod 4 \), and \( 2 \neq 3 \)).

Exhaustive check of the one remaining composite case not covered by Steps 10–11. A

In every case, a composite \( n \geq 2 \) gives \( (n-1)! \equiv 0 \pmod n \), except \( n=4 \) where direct computation shows \( (n-1)! \equiv 2 \pmod n \); in neither case is \( (n-1)! \equiv -1 \pmod n \), since \( 0 \not\equiv -1 \) and \( 2 \not\equiv -1 \) for all \( n \geq 2\) (as \( -1 \equiv n-1 \), and \( n - 1 = 0 \) only if \( n=1\), \( n-1=2 \) only if \(n=3\), which is prime not composite). This contradicts the assumption of Step 9.

Combining Steps 10–12 exhausts all composite \( n \) and shows the congruence fails in each; contradiction, so no composite \( n \) satisfies \( (n-1)! \equiv -1 \pmod n \), proving the converse by contraposition. C

Result

n \text{ is prime} \iff (n-1)! \equiv -1 \pmod{n}

Reading. Multiply together every integer from \( 1 \) up to one less than \( n \); reduce modulo \( n \). You land exactly on \( -1 \) (i.e. \( n-1 \)) precisely when \( n \) has no factors of its own — when it's prime. For any composite \( n \), the same product instead lands on \( 0 \) (or, in the single exceptional case \( n=4 \), on \( 2 \)).

Scope. Holds for all integers \( n \geq 2 \) with no further restriction; it is a full biconditional (necessary and sufficient), unlike Fermat's little theorem which is only necessary for primality. It applies to \( n \) itself, not to intermediate moduli or to factorial-like products truncated elsewhere.

Corollaries & converses

The converse is not a separate fact to worry about — it is built into the theorem as stated (an "if and only if"), and was proved directly above in Direction 2.
Corollary (Wilson quotient). For prime \( p \), the integer \( W(p) = \dfrac{(p-1)!+1}{p} \) is a well-defined integer, called the Wilson quotient; its residue mod \( p \) is of independent interest (Wilson primes are those with \( W(p) \equiv 0 \pmod{p^2}\), i.e. \( p^2 \mid (p-1)!+1 \) — only \( 5, 13, 563 \) are known).
Corollary. For odd prime \( p \), \( \left(\dfrac{p-1}{2}!\right)^2 \equiv (-1)^{(p+1)/2} \pmod p \), obtained by pairing \( k \) with \( p-k \) in \( (p-1)! \); this is a standard route to determining when \( -1 \) is a quadratic residue mod \( p \).
As a primality test the theorem is correct but practically useless: computing \( (n-1)! \bmod n \) takes \( \Theta(n) \) modular multiplications, vastly slower than trial division or modern probabilistic/deterministic tests (Miller–Rabin, AKS).

Fails without

Drop \( n \geq 2 \): at \( n = 1 \), \( (0)! = 1 \equiv 0 \pmod 1 \), and the "congruence" \( \equiv -1 \) is vacuously true (everything is \( \equiv 0 \equiv -1 \pmod 1\)) even though \( 1 \) is not prime — the biconditional breaks down because primality is undefined/false at \( n=1\) while the congruence side is trivially satisfied.
Drop primality of \( p \) in the forward direction (i.e. try to apply the pairing argument to composite \( n \)): for \( n = 6 \), \( \mathbb{Z}/6\mathbb{Z} \) is not a field, \( (\mathbb{Z}/6\mathbb{Z})^\times = \{1,5\} \) has order \( 2 \), not \( 5 \), so the pairing argument over "all nonzero residues" collapses (most residues, e.g. \( 2,3,4\), are zero divisors, not units, and have no inverse); indeed \( 5! = 120 \equiv 0 \pmod 6 \), not \(-1\).
Forget the exceptional case \( n=4 \) in the converse proof: naively applying the Step 10 pairing (distinct factors \( a \neq b\)) to \( n=4=2\times2\) is impossible since \( a=b=2\), and the Step 11 bound \( 2a \le a^2-1\) fails at \( a=2\) (giving \(4 \le 3\), false); omitting the separate check at \( n=4\) would wrongly suggest \( 3! \equiv 0\), but in fact \( 3!=6\equiv2\pmod4\) — a genuinely different residue that must be checked by hand.

Common errors

Treating \( (p-1)! \equiv -1 \pmod p \) as an equation over \( \mathbb{Z} \) rather than a congruence, then being confused that \( (p-1)! \) is positive and large while \(-1\) is negative and small (e.g. plugging \( p=7 \): \( 6! = 720 \), and checking "\(720 = -1\)?" instead of "\(720 \equiv -1 \pmod 7\)", i.e. \(721 = 7\times103\)).
Believing the pairing argument works for composite \( n \) by pairing "all numbers less than \( n \) with their inverses" — forgetting that non-units (zero divisors) exist mod \( n \) when \( n \) is composite and have no multiplicative inverse at all.
Forgetting to isolate the self-inverse elements \( 1 \) and \( p-1 \) before pairing the rest, and instead trying to pair every element of \( \{1,\dots,p-1\}\) including \(1\) and \(p-1\) with themselves as if they had distinct partners, miscounting the number of pairs.
Misapplying Wilson's theorem as a practical primality test on large numbers, not registering that computing \( (n-1)! \bmod n \) is computationally far more expensive than simply trial-dividing or applying Miller–Rabin.
Confusing Wilson's theorem with Fermat's little theorem (\( a^{p-1}\equiv1\pmod p\) for \(\gcd(a,p)=1\)) — the two are related but logically different: Fermat's is only a necessary condition for primality (there are Fermat pseudoprimes), Wilson's is necessary and sufficient.

Discussion

Wilson's theorem is traditionally attributed to John Wilson, a student of Edward Waring who stated it (without proof) in 1770; Waring published it, Lagrange gave the first proof in 1771, and it was later noted that Leibniz had been aware of the essential fact roughly a century earlier without publishing it. The theorem's real content is not really about factorials at all — it is a statement about the structure of the unit group of a finite field, dressed up in factorial notation.

The pairing argument used in Direction 1 is a special case of a much more general fact: in any finite abelian group \( G \), the product of all elements of \( G \) equals the product of all elements of order dividing \( 2 \) (the self-inverse elements), because every other element cancels against its distinct inverse in the full product. Applied to \( G = (\mathbb{Z}/p\mathbb{Z})^\times \), a cyclic group of even order \( p-1 \) (for \( p \) odd), the unique element of order \( 2 \) is \( -1 \), which is exactly what step 5–8 isolates.

This generalisation immediately answers a natural follow-up question: what is the product of all elements of \( (\mathbb{Z}/n\mathbb{Z})^\times \) for composite \( n \)? Gauss showed the product is \( -1 \pmod n \) when \( n \) has a primitive root (i.e. \( n \in \{1,2,4,p^k,2p^k\} \) for odd prime \( p \)), and \( +1 \pmod n \) otherwise — because when no primitive root exists, the group \( (\mathbb{Z}/n\mathbb{Z})^\times \) is non-cyclic and has more than one element of order \( 2\), and these extra involutions pair off and cancel, leaving the identity. This is sometimes called the Gauss–Wilson theorem and is the natural generalisation of Wilson's theorem to composite moduli via unit-group products rather than full factorials.

Common misconception. Students sometimes think Wilson's theorem gives an efficient primality test because it is an "if and only if." Logical strength (necessary and sufficient) says nothing about computational cost: evaluating the criterion requires computing a factorial with \( \Theta(n) \) multiplications, which is exponential in the bit-length of \( n \), making it useless in practice compared to polynomial-time tests such as Miller–Rabin or AKS — a good early lesson that "characterises" and "efficiently decides" are different notions.

Worked examples

Verify Wilson's theorem directly for \( p = 7 \).

Set-up: compute \( 6! \bmod 7 \) and compare to \(-1 \equiv 6 \pmod 7\). A

Pair the non-self-inverse elements of \( \{2,3,4,5\} \subset (\mathbb{Z}/7\mathbb{Z})^\times \) with their inverses: \( 2 \cdot 4 = 8 \equiv 1 \), \( 3 \cdot 5 = 15 \equiv 1 \pmod 7 \). So \( \{2,4\} \) and \( \{3,5\} \) are the inverse pairs.

Using Steps 3–6 of the proof: every element of \( \{2,\dots,p-2\} = \{2,3,4,5\} \) pairs with a distinct inverse. B

\[ 6! = 1 \cdot (2\cdot4) \cdot (3\cdot5) \cdot 6 \equiv 1 \cdot 1 \cdot 1 \cdot 6 \equiv 6 \equiv -1 \pmod 7. \]

Direct substitution of the pairing into the product, as in Steps 7–8. A

6! = 720 \equiv -1 \pmod 7 \quad(\text{since } 720 = 7 \cdot 102 + 6)

Reading. The theorem checks out exactly as predicted for the prime \(p=7\), and the pairing mechanism makes visible why it works rather than just confirming the arithmetic.

Use the converse of Wilson's theorem to certify that \( n = 11 \) is prime, given only the value \( 10! \bmod 11 \).

Set-up: this is the direction-2 usage — a congruence check used as a primality certificate. A

Compute \( 10! = 3628800 \). Divide: \( 3628800 = 11 \cdot 329890 + 10 \), so \( 10! \equiv 10 \equiv -1 \pmod{11} \).

Direct computation of the remainder. A

By the converse direction of Wilson's theorem (Steps 9–13 of the proof), since \( 10! \equiv -1 \pmod{11} \), \( n=11 \) cannot be composite — any composite \( n \) would force \( (n-1)! \equiv 0 \) or, only at \( n=4 \), \( \equiv 2 \), never \( \equiv -1 \). Hence \( 11 \) is prime.

Contrapositive application of the proved converse. B

10! \equiv -1 \pmod{11} \implies 11 \text{ is prime}

Reading. This illustrates the converse being used as intended: a single congruence check, in principle, certifies primality without ever finding a factor — though as discussed, computing \( (n-1)! \) this way is impractical for large \( n \).

Problems

Verify Wilson's theorem directly (by computing the pairing of inverses) for \( p = 13 \).
Solution

Units are \( \{1,\dots,12\} \). Self-inverse elements are \(1\) and \(12\) (since \(12\equiv-1\)). Find inverse pairs among \( \{2,\dots,11\} \): \(2\cdot7=14\equiv1\); \(3\cdot9=27\equiv1\); \(4\cdot10=40\equiv1\); \(5\cdot8=40\equiv1\)... wait recompute: \(5\cdot8=40\equiv40-39=1\); \(6\cdot11=66\equiv66-65=1\). So pairs are \(\{2,7\},\{3,9\},\{4,10\},\{5,8\},\{6,11\}\) — five pairs covering all ten elements. Then \(12! \equiv 1\cdot(2\cdot7)\cdot(3\cdot9)\cdot(4\cdot10)\cdot(5\cdot8)\cdot(6\cdot11)\cdot12 \equiv 1\cdot1\cdot1\cdot1\cdot1\cdot1\cdot12 \equiv 12 \equiv -1 \pmod{13}\), confirming the theorem.
Show directly, without invoking the general converse proof, that \( 5! \not\equiv -1 \pmod 6 \), consistent with \( 6 \) being composite.
Solution

\(5! = 120\). \(120 = 6\cdot20 + 0\), so \(5! \equiv 0 \pmod 6\), while \(-1\equiv5\pmod6\). Since \(0\neq5\), the congruence fails, as predicted: \(6=2\cdot3\) with \(2\neq3\) both appearing as separate factors in \(5!=1\cdot2\cdot3\cdot4\cdot5\), giving \(6\mid5!\).
Using the corollary \( \left(\frac{p-1}{2}!\right)^2 \equiv (-1)^{(p+1)/2}\pmod p \), determine whether \(-1\) is a quadratic residue mod \(13\).
Solution

Here \(p=13\), \((p+1)/2=7\), so the corollary gives \(\left(6!\right)^2\equiv(-1)^7=-1\pmod{13}\). Since \(6! = 720 \equiv 720-55\cdot13=720-715=5\pmod{13}\), check \(5^2=25\equiv25-13=12\equiv-1\pmod{13}\) — consistent. Since \(6!\) squared is \(-1\), \(-1\) is a quadratic residue mod 13 (explicitly, \(5^2\equiv-1\)), matching the general fact that \(-1\) is a QR mod an odd prime \(p\) iff \(p\equiv1\pmod4\), and indeed \(13\equiv1\pmod4\).
Prove that for every prime \(p\geq5\), \((p-2)!\equiv1\pmod p\).
Solution

By Wilson's theorem, \((p-1)!\equiv-1\pmod p\). Also \((p-1)!=(p-1)\cdot(p-2)!\), and \(p-1\equiv-1\pmod p\), so \((p-1)!\equiv-1\cdot(p-2)!\pmod p\). Combining, \(-1\cdot(p-2)!\equiv-1\pmod p\). Since \(\gcd(-1,p)=1\), \(-1\) is invertible (it is its own inverse), so multiply both sides by \(-1\): \((p-2)!\equiv1\pmod p\).
A student claims: "since Wilson's theorem is an if-and-only-if, and \(4!=24\equiv0\pmod5\)... wait, \(5\) is prime, so this should be \(-1\)." Find the student's error and correct the computation, then use it to explain why the claim as computed is inconsistent with the theorem — or isn't.
Solution

Recompute: \(4! = 24\). \(24 = 5\cdot4 + 4\), so \(4!\equiv4\pmod5\), and indeed \(4\equiv-1\pmod5\). So there is in fact no inconsistency — the student's arithmetic error was writing "\(\equiv0\)" instead of correctly reducing \(24\bmod5=4\). This exercise is a caution: always finish the modular reduction rather than eyeballing it, since a wrong intermediate residue can make a true theorem look falsified.