Wilson's Theorem

$(p-1)!\equiv -1(\mathrm{mod}p)\text{iff }p\text{ is prime.}$

Why it holds

In ${\mathbb{Z}}_p^{\ast }$, pair every element with its inverse. The pairs cancel to 1, except for the self-inverse elements — those with $x^2\equiv 1$, i.e. $x\equiv \pm 1$. So the product of everything is $1\cdot (-1)=-1$.

For composite $n>4$, the factors $a$ and $n/a$ both appear in $(n-1)!$, so $n\mid (n-1)!$ and the product is $0$. ($n=4$ gives $3!=6\equiv 2$.) That makes Wilson’s theorem an exact primality characterisation — though a useless one computationally, since computing $(p-1)!$ takes $O(p)$.

The useful consequences

Factorial complements

$(p-1-k)!\equiv \frac{-1}{(-1{)}^{k+1}k!}(\mathrm{mod}p).$

Concretely, $(p-2)!\equiv 1$, and more generally you can convert a factorial near $p$ into a small one — useful when a formula involves $(p-k)!$ for small $k$.

Wilson’s quotient and prime powers

$(p-1)!\equiv -1(\mathrm{mod}{p}^2)$
holds only for Wilson primes: 5, 13, and 563. No others are known below $2\cdot 10^{13}$.

Factorial modulo $p$ with a factor removed

Define $(n!{)}_p$ as the product of integers $\le n$ not divisible by $p$. Then Wilson gives

$(n!{)}_p\equiv (-1{)}^{\lfloor n/p\rfloor }\cdot ((n\mathrm{mod}p)!)(\mathrm{mod}p),$

which is the engine of the generalised Lucas theorem — see Factorial Modulo p.

Related theorems worth having together

Theorem	Statement
Wilson	$(p-1)!\equiv -1(\mathrm{mod}p)$ iff $p$ prime
Fermat	$a^{p-1}\equiv 1(\mathrm{mod}p)$ for $p\nmid a$
Euler	$a^{\phi (n)}\equiv 1$ for $\gcd (a,n)=1$
Lucas	$\left(\genfrac{}{}{0ex}{}{n}{k}\right)\equiv \prod \left(\genfrac{}{}{0ex}{}{n_i}{k_i}\right)(\mathrm{mod}p)$ in base $p$
Legendre	the exponent of $p$ in $n!$ is ${\sum }_{i\ge 1}\lfloor n/p^i\rfloor$
Kummer	that exponent in $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ = number of carries adding $k$ and $n-k$ in base $p$

Legendre’s formula — the practical one

$v_p(n!)={\sum }_{i\ge 1}\lfloor \frac{n}{p^i}\rfloor .$

long long legendre(long long n, long long p) {
    long long e = 0;
    for (long long q = p; q <= n; q *= p) e += n / q;
    return e;
}

This is how you compute:

• trailing zeros of $n!$ — $v_5(n!)$ (there are always more 2s than 5s);
• the exact power of $p$ dividing $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ — $v_p(n!)-v_p(k!)-v_p((n-k)!)$;
• whether $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ is divisible by $p$ — equivalently, by Kummer’s theorem, whether adding $k$ and $n-k$ in base $p$ produces a carry.

See Trailing Zeroes.

Where Wilson actually gets used

• Computing $n!\mathrm{mod}p$ when $n\ge p$ — the answer is 0 unless you mean the $p$-free factorial, which Wilson evaluates.
• Generalised Lucas for $\left(\genfrac{}{}{0ex}{}{n}{k}\right)\mathrm{mod}{p}^e$ (Andrew Granville’s method).
• Proof exercises — Wilson gives quick proofs that $-1$ is a QR modulo $p$ iff $p\equiv 1(\mathrm{mod}4)$: take $x=\left(\frac{p-1}{2}\right)!$ and check $x^2\equiv (-1{)}^{(p+1)/2}$.
• Primality testing — theoretically exact, practically useless; use Miller-Rabin.

See also: Factorial Modulo p · Lucas Theorem · Combinatorics