Wilson's Theorem

Wilson's Theorem gives a necessary and sufficient condition for primality based on factorials.

Statement

Proof Idea

1. Composite $n=4$: $3!=6\equiv 2(\mathrm{mod}4)$. Fail.
2. Composite $n>4$: Both $a$ and $b$ (where $n=ab$) appear in $(n-1)!$. Or $p$ and $2p$. The product is $0(\mathrm{mod}n)$.
3. Prime $p$: Every number $a\in \{1,\dots ,p-1\}$ has a unique inverse $a^{-1}$.

• Group elements in pairs $(a,a^{-1})$ where $a\cdot a^{-1}\equiv 1$.

• Only elements that are their own inverses are $x^2\equiv 1⟹x\equiv 1,-1$.

• The product is $1\cdot (-1)\cdot (1\dots 1)\equiv -1$.

Applications

• Used to prove properties of Quadratic Residues ($x^2\equiv -1(\mathrm{mod}p)$).
• Calculating remainders of huge factorials modulo $p$.

Practice Problems