TheoremProved

Wilson's theorem

Statement

A natural number $p>1$ is prime if and only if $(p-1)! \equiv -1 \pmod{p}$ .

Why is it true?

Modulo a prime $p$ , every residue from $1$ to $p-1$ pairs off with its multiplicative inverse, and only $1$ and $p-1\equiv-1$ are their own inverses. Multiplying all residues, the self-paired ones survive and the rest cancel in inverse pairs, leaving $(p-1)!\equiv -1$ .

Proof sketch

( $\Rightarrow$ ) For prime $p$ , pair each $k\in\{2,\dots,p-2\}$ with its inverse mod $p$ (never itself, since $x^2\equiv1\pmod p$ only for $x\equiv\pm1$ ); these pairs multiply to $1$ , leaving $(p-1)!\equiv 1\cdot(p-1)\equiv -1\pmod p$ . ( $\Leftarrow$ ) If $n$ is composite with a proper divisor $1<d<n$ , then $d$ appears as a factor in $(n-1)!$ , so $d\mid(n-1)!$ and $(n-1)!\not\equiv-1\pmod n$ .

Proved by

proved 1771Joseph-Louis Lagrange

Topics that use this theorem

Congruences and modular arithmetic

Related theorems

Fermat's little theorem

Step-by-step proofs

No step-by-step proof yet for this theorem.

References

G. H. Hardy, E. M. Wright (2008). An Introduction to the Theory of Numbers
Carl B. Boyer, Uta C. Merzbach (2011). A History of Mathematics