Wilson's Theorem
Here is a perfect characterisation of the primes — one that, in principle, tells you whether
n is prime by a single congruence. It is too slow to be a practical
test, but it is a
gem, and its proof is a lovely application of
modular inverses.
The statement
An integer p > 1 is prime if and only if
(p - 1)! \equiv -1 \pmod{p}.
Try p = 5: 4! = 24 \equiv -1 \pmod 5 (since
24 = 25 - 1). For a composite like 6,
5! = 120 \equiv 0 \pmod 6 — nowhere near -1.
The congruence holds for primes and only primes.
Why it's true: pairing up inverses
Modulo a prime p, every number in
2, 3, \dots, p-2 has a distinct inverse different from itself,
so they pair off into couples whose product is 1. The whole product
(p-1)! collapses to the only two self-paired elements:
(p-1)! \equiv \underbrace{1}_{} \cdot \underbrace{(p-1)}_{\equiv -1} \cdot \underbrace{(\text{pairs} \to 1)}_{} \equiv -1 \pmod p.
The only residues equal to their own inverse are 1 and
p - 1 \equiv -1 (because x^2 \equiv 1 forces
x \equiv \pm 1 modulo a prime). Everything else cancels in pairs,
leaving 1 \cdot (-1) = -1.
The converse half
If n is composite, the pairing breaks down: a proper factor of
n appears inside (n-1)!, forcing the factorial
to be \equiv 0 (or otherwise not -1). So the
congruence (n-1)! \equiv -1 can only happen for primes — making
it a genuine, if impractical, primality criterion.