Wilson's Theorem: The Hidden Link Between Primes and Factorials

Here's a strange fact: multiply every number from 1 up to 562, add 1 to the result, and the gargantuan number you get is evenly divisible by 563. Try the same trick with 564 instead of 563, and it fails completely. There is nothing special about 563 on the surface — it's just a number you might pass on a page — except for one property: it's prime. That single fact is enough to force an exact, no-remainder division on a number with over a thousand digits. This is Wilson's theorem, and it is one of the cleanest "if and only if" statements in all of mathematics: a number p is prime precisely when (p−1)! + 1 is divisible by p. No exceptions, no approximations — primality and a factorial identity turn out to be exactly the same fact wearing different clothes.

The Concept

Wilson's theorem says: for a number p greater than 1, p is prime if and only if

(p − 1)! ≡ −1 (mod p)

Unpacking that notation: (p − 1)! is "p minus 1, factorial" — multiply together every whole number from 1 up to p − 1. The "≡ −1 (mod p)" part means that when you divide that product by p, the remainder is p − 1 (which is the same thing as saying the product is "one short of" a multiple of p).

Try it on a small prime, say p = 5. Then (p − 1)! = 4! = 1 × 2 × 3 × 4 = 24. Divide 24 by 5 and you get a remainder of 4, which is indeed −1 mod 5 (since 5 − 1 = 4). Add 1 to 24 and you get 25, which is 5 × 5 — divisible by 5 exactly.

Now try a composite number, say p = 6. Then (p − 1)! = 5! = 120. Divide 120 by 6 and you get remainder 0, not −1 (which would be 5). Add 1 to 120 and you get 121 = 11², which is not divisible by 6 at all. The pattern breaks the instant primality breaks.

What makes this theorem remarkable is that it's a genuine biconditional — a two-way street. Most of the famous primality facts in elementary number theory, like Fermat's Little Theorem, only go one direction: if p is prime, then some property holds, but numbers that aren't prime can still sneak through and satisfy the same property (these impostors are called Fermat liars or pseudoprimes). Wilson's theorem has no impostors. If the congruence holds, p is prime, full stop. That airtight equivalence is rare enough in number theory that it's worth pausing on.

Why It Matters

Wilson's theorem functions as a perfect, logically clean definition of primality rephrased in the language of factorials — and that reframing turns out to ripple into cryptography, coding theory, and theoretical computer science, even though the theorem itself is not how real-world systems check for primes.

Here's the paradox: Wilson's theorem is mathematically perfect but practically terrible as a primality test. To verify that a 300-digit number p is prime, you'd need to compute (p − 1)!, a number so unthinkably large that no computer on Earth could finish the multiplication before the heat death of the universe became a more pressing concern. Factorials grow faster than exponentials, which already grow faster than anything a brute-force computer wants to deal with. So while Wilson's theorem is theoretically a complete primality test, it is never actually used that way. Instead, the field relies on faster probabilistic and deterministic tests — Fermat's test, Miller–Rabin, and the AKS algorithm — that get the same yes/no answer without ever touching a number that large.

So why does Wilson's theorem matter at all if nobody uses it to find primes? Because it's one of the foundational tools used to prove other things are true. It appears in the machinery behind quadratic residue theory (which underlies whether a number has a "square root" in modular arithmetic — itself relevant to certain cryptographic protocols), it's a building block in competition mathematics and formal proofs about the structure of prime numbers, and it shows up in coding theory's constructions of error-correcting codes. RSA encryption — the algorithm quietly securing your bank's HTTPS connection — depends on fast, reliable primality testing to generate its keys; Wilson's theorem is part of the conceptual lineage of that testing machinery, even if the actual implementation reaches for Miller–Rabin instead. It's less a tool in the cryptographer's toolbox today and more a load-bearing beam in the foundation that toolbox stands on.

The Details

A tangled, trans-continental history

The theorem's name is something of a historical accident. It's credited to John Wilson, an 18th-century English mathematician and judge — but Wilson never published a proof, and may not have had one. The theorem appeared in print in 1770 in Edward Waring's Meditationes Algebraicae, where Waring credited his former student Wilson with the observation but openly admitted neither of them could prove it.

The first published proof came a year later, in 1771, from Joseph-Louis Lagrange — which is why some number theorists more precisely call it the Wilson–Lagrange theorem.

But the story goes back even further. Historical research has traced an awareness of the same underlying fact to the 11th-century Arab mathematician Ibn al-Haytham (also known as Alhazen, better remembered today for his foundational work in optics), who appears to have stated a version of the result around 1000 AD — roughly 770 years before Wilson. And Gottfried Leibniz, writing around 1683, also seems to have been aware of the relationship, though he never published it either. So the "Wilson" in Wilson's theorem is really a case of a result accumulating a name through the person who happened to make it stick in European mathematical circles, not the person who found it first — a pattern that shows up again and again in math history (Pascal's triangle predates Pascal by centuries in Chinese and Persian mathematics for exactly the same reason).

Why the theorem is true, in plain English

Here's the intuition behind Lagrange's proof. Work modulo a prime p, and look at the numbers 1 through p − 1. Every one of these numbers has a unique "multiplicative partner" — another number in that same range that, when multiplied together, gives a remainder of 1 when divided by p. For instance, modulo 7: 2 and 4 are partners, because 2 × 4 = 8, and 8 mod 7 = 1. Likewise 3 and 5 are partners (3 × 5 = 15, and 15 mod 7 = 1).

Almost every number pairs off neatly with a distinct partner — except for two stubborn numbers that are each their own partner: 1 (since 1 × 1 = 1) and p − 1 (since (p−1) × (p−1) leaves remainder 1 too, because (p−1)² = p² − 2p + 1, and modulo p that's just 1). Every other number from 2 to p − 2 pairs off with some different partner, and each pair multiplies to give remainder 1. So when you multiply everything from 1 to p − 1 together, all those paired-off numbers cancel down to a remainder of 1, leaving just the two unpaired numbers: 1 and p − 1. Multiply those together and you get p − 1, which is exactly −1 modulo p. That's the whole trick: a factorial that looks hopelessly complicated collapses, through pairing, into a single lonely leftover term.

This pairing argument only works cleanly because p is prime — primality guarantees that every number from 1 to p − 1 has a genuine multiplicative partner in that same range. For composite numbers, that guarantee breaks down (not every number coprime to a composite n has as clean a pairing structure), which is exactly why the "only if" direction of the theorem fails for composites.

The composite case, and Gauss's cleanup

Carl Friedrich Gauss later tidied up what happens for composite moduli. If instead of taking every number up to n − 1, you restrict yourself to just the numbers that share no common factor with n (the "coprime" ones) and multiply those together, Gauss showed the product is congruent to −1 (mod n) only when n is 1, 2, 4, a power of an odd prime, or twice a power of an odd prime — and congruent to +1 (mod n) for every other n. It's a beautiful generalization because it reveals that the −1 in Wilson's original theorem isn't really about primes specifically; it's about a structural property of how numbers multiply together in modular arithmetic (specifically, whether the group of "invertible" numbers mod n has a certain cyclic structure).

Wilson primes: a theorem within the theorem

Mathematicians being mathematicians, someone eventually asked: for prime p, how close is (p − 1)! + 1 to being divisible by p², not just p? A prime where (p − 1)! + 1 is divisible by p² is called a Wilson prime, and they are startlingly rare. Only three are currently known: 5, 13, and 563. An extensive computational search in 2012 checked every prime up to 2 × 10¹³ (20 trillion) and found no others. Mathematicians conjecture there are infinitely many Wilson primes, but proving it — or finding a fourth one — remains an open problem. It's a nice reminder that even a 250-year-old theorem can still be hiding unanswered questions in its margins.

Takeaways

• Wilson's theorem states that a number p > 1 is prime exactly when (p − 1)! + 1 is divisible by p — a rare true biconditional in number theory, with no "pseudoprime" exceptions.
• It's named after John Wilson, published by Edward Waring in 1770, first proved by Lagrange in 1771 — but versions of the idea trace back to Ibn al-Haytham around 1000 AD and Leibniz around 1683.
• The theorem is mathematically perfect but practically useless as a primality test for large numbers, since computing a giant factorial is far slower than modern tests like Miller–Rabin.
• Gauss generalized the result to composite moduli, showing the "−1" is really about the structure of modular multiplication, not primality alone.
• Only three Wilson primes are known (5, 13, 563), and whether there are infinitely many is still an open question in number theory.

Resources: - Wilson's theorem — Wikipedia - Wilson prime — Wikipedia - A Search for Wilson Primes (Costa, Gerbicz, Harvey, 2012)