Wilson's Theorem

(p-1)! -1 p characterizes the primes.

The idea

Theorem (Wilson's theorem).

An integer $p > 1$ is prime if and only if $(p-1)! \equiv -1 \pmod{p}.$

The theorem separates the primes from the composites sharply: for a composite $n > 4$ the residue $(n-1)! \bmod n$ is not merely different from $-1$ but equal to $0$, while for every prime $p$ the product $(p-1)!$ of all the nonzero residues lands on $-1$. The substance of the theorem is the prime case.

As a primality test the theorem is impractical, since computing $(n-1)!$ costs far more than trial division. Its value is that it is exact, and that it determines factorial residues no direct computation could reach.

Ways to work on it

• Walkthrough. Pair residues with their inverses to collapse (p-1)! to -1.
• Proof. See why (p-1)! -1 for every prime — the general inverse-pairing argument.
• Practice. Evaluate (p-1)! p for a small prime.
• Hardest. Use the theorem as a primality test and to extract a factorial residue.

Not sure where to start? Take the ten-question placement test.