Here's a strange party trick for a number p: line up every whole number from 1 to p-1, multiply them all together, and look at the remainder when you divide by p. If p is prime, something remarkable happens every single time: the remainder is always exactly p - 1 — one short of a whole multiple of p. Never 2 short, never a random number in between. Always one short.

That coincidence isn't a coincidence at all — it's a theorem, discovered (or really, first proved) in the 1770s, and it gives a perfect characterisation of the primes: a single congruence that a number satisfies if and only if it is prime. It is too slow to be a practical primality test, but it is a genuine gem of number theory, and its proof is a lovely application of modular inverses.

The statement

Remember that -1 \pmod p is just another name for p - 1 — they're the same residue. So the theorem says: multiply everything below p together, and for a prime you land exactly one step short of the next multiple of p. For a composite number, you never do. That "if and only if" is doing a lot of work — it means the congruence is a flawless detector, with no false positives and no false negatives, however far out you look.

Worked example: checking p = 5

Let's actually do it. Take p = 5, so we need (5-1)! = 4!:

Now reduce 24 modulo 5. Since 24 = 25 - 1 = 5 \times 5 - 1, we have

Exactly as promised: the remainder is 4, which is p - 1. And 5 is indeed prime. One data point isn't a proof, but it's a satisfying place to start.

Worked example: checking p = 7

Let's push one step further with p = 7. We need 6! = 6 \times 5 \times 4 \times 3 \times 2 \times 1. Multiplying it out gradually,

Divide 720 by 7: 7 \times 102 = 714, and 720 - 714 = 6. So

because 6 and -1 are the same residue modulo 7 (they differ by exactly 7). Once more, the prime 7 lands the factorial exactly one short of a multiple of 7. You could keep this game going forever, and for every prime you would land on -1 without fail.

Now try a composite for contrast, say n = 6: 5! = 120, and 120 = 6 \times 20 exactly, so 5! \equiv 0 \pmod 6 — nowhere near -1. The pattern breaks the moment primality breaks.

Why it's true: pairing up inverses

The proof is one of the most elegant matching arguments in elementary number theory. Modulo a prime p, every residue in 2, 3, \dots, p-2 has a unique multiplicative inverse in that same range, and — crucially — that inverse is different from itself (nobody in the middle is their own inverse). So the residues 2 through p - 2 pair off into couples whose product is 1, and multiplying a bunch of pairs each worth 1 just gives 1 overall. The whole product (p-1)! therefore collapses to just the two residues that are not paired away — the two "loners" that are their own inverse:

Why are 1 and p - 1 the only self-paired residues? Because being your own inverse means x \cdot x \equiv 1, i.e. x^2 - 1 \equiv 0, which factors as (x-1)(x+1) \equiv 0 \pmod p. Since p is prime, it can only divide the product if it divides one of the factors, forcing x \equiv 1 or x \equiv -1. Every other residue genuinely cancels against a different partner, leaving only 1 \cdot (-1) = -1 standing.

Seeing it with real numbers helps. Take p = 7 again, and look at the middle residues 2, 3, 4, 5. Multiply 2 \times 4 = 8 \equiv 1 \pmod 7 — a matched pair. Multiply 3 \times 5 = 15 \equiv 1 \pmod 7 — another matched pair. Every middle residue has vanished into a pair worth 1, leaving only the two loners, 1 and 6 \equiv -1, to multiply together: exactly the -1 the theorem promises. The whole proof is really just this pairing trick, dressed up to work for any prime at all.

The converse half — and why the theorem is genuinely "if and only if"

A one-way theorem ("every prime satisfies this") would already be interesting, but Wilson's theorem is stronger: it's a true biconditional. If n is composite, the pairing argument above breaks down in a way that also breaks the congruence. A composite n > 4 has a proper factor that already appears somewhere inside the list 1, 2, \dots, n-1, so that factor (and its cofactor) shows up inside the product (n-1)! itself, forcing (n-1)! to share a common factor with n — which rules out (n-1)! \equiv -1 \pmod n (since -1 is always coprime to n). So the congruence (n-1)! \equiv -1 \pmod n can only ever happen when n is prime. Test the congruence, and you have your answer both ways — that's what makes it a genuine primality criterion, not just a curious fact about primes.

Just how slow is "explosively"?

It's worth putting real numbers on the claim that factorials get out of hand. Take p = 101, a perfectly ordinary three-digit prime. Wilson's theorem asks you to compute 100! — a number with about 158 digits — before you can even take its remainder modulo 101. That's 99 multiplications, each one working with numbers that keep getting bigger and bigger as you go.

Compare that with a Fermat-style test, which instead computes something like a^{100} \bmod 101 using repeated squaring. Because 100 in binary is only 1100100 — seven digits — the whole computation takes roughly 7 squarings, each one immediately reduced modulo 101 so the numbers never grow bigger than 101^2. Seven small steps versus ninety-nine ever-growing ones — and the gap only gets more lopsided as the prime grows. For a 300-digit prime (the kind of size used in real cryptography), Wilson's theorem would need you to build and reduce a number with thousands of digits, while a repeated-squaring test needs only around a thousand small, tightly controlled steps. Same underlying idea — "raise something to a power modulo p and see what happens" — but one route is a scenic stroll and the other is a dead-end cliff.