Wilson's theorem

Example

For each of the values of n from 2 to 30, the following table shows the number (n − 1)! and the remainder when (n − 1)! is divided by n. (In the notation of modular arithmetic, the remainder when m is divided by n is written m mod n.) As expected, ${\displaystyle (n-1)!\equiv n-1modn}$ when n is prime. The background color is blue for prime values of n, gold for composite values.

Proofs

As a biconditional (if and only if) statement, the proof has two halves: to show that equality does not hold when ${\displaystyle n}$ is composite, and to show that it does hold when ${\displaystyle n}$ is prime.

Composite modulus

Suppose that ${\displaystyle n}$ is composite. Therefore, it is divisible by some prime number ${\displaystyle q}$ where ${\displaystyle 2\le q<n}$. Because ${\displaystyle q}$ divides ${\displaystyle n}$, there is an integer ${\displaystyle k}$ such that ${\displaystyle n=qk}$. Suppose for the sake of contradiction that ${\displaystyle (n-1)!}$ were congruent to ${\displaystyle -1}$ modulo ${\displaystyle n}$. Then ${\displaystyle (n-1)!}$ would also be congruent to ${\displaystyle -1}$ modulo ${\displaystyle q}$: indeed, if ${\displaystyle (n-1)!\equiv -1(\mathrm{mod}n)}$ then ${\displaystyle (n-1)!=nm-1=(qk)m-1=q(km)-1}$ for some integer ${\displaystyle m}$, and consequently ${\displaystyle (n-1)!}$ is one less than a multiple of ${\displaystyle q}$. On the other hand, since ${\displaystyle 2\le q\le n-1}$, one of the factors in the expanded product ${\displaystyle (n-1)!=(n-1)\times (n-2)\times \cdots \times 2\times 1}$ is ${\displaystyle q}$. Therefore ${\displaystyle (n-1)!\equiv 0(\mathrm{mod}q)}$. This is a contradiction; therefore it is not possible that ${\displaystyle (n-1)!\equiv -1(\mathrm{mod}n)}$ when ${\displaystyle n}$ is composite.

In fact, more is true. With the sole exception of the case ${\displaystyle n=4}$, where ${\displaystyle 3!=6\equiv 2(\mathrm{mod}4)}$, if ${\displaystyle n}$ is composite then ${\displaystyle (n-1)!}$ is congruent to 0 modulo ${\displaystyle n}$. The proof can be divided into two cases: First, if ${\displaystyle n}$ can be factored as the product of two unequal numbers, ${\displaystyle n=ab}$, where ${\displaystyle 2\le a<b<n}$, then both ${\displaystyle a}$ and ${\displaystyle b}$ will appear as factors in the product ${\displaystyle (n-1)!=(n-1)\times (n-2)\times \cdots \times 2\times 1}$ and so ${\displaystyle (n-1)!}$ is divisible by ${\displaystyle ab=n}$. If ${\displaystyle n}$ has no such factorization, then it must be the square of some prime ${\displaystyle q}$ larger than 2. But then ${\displaystyle 2q<q^2=n}$, so both ${\displaystyle q}$ and ${\displaystyle 2q}$ will be factors of ${\displaystyle (n-1)!}$, and so ${\displaystyle n}$ divides ${\displaystyle (n-1)!}$ in this case, as well.

Prime modulus

The first two proofs below use the fact that the residue classes modulo a prime number form a finite field (specifically, a prime field).

Elementary proof

The result is trivial when ${\displaystyle p=2}$, so assume ${\displaystyle p}$ is an odd prime, ${\displaystyle p\ge 3}$. Since the residue classes modulo ${\displaystyle p}$ form a field, every non-zero residue ${\displaystyle a}$ has a unique multiplicative inverse ${\displaystyle a^{-1}}$. Euclid's lemma implies that the only values of ${\displaystyle a}$ for which ${\displaystyle a\equiv a^{-1}(\mathrm{mod}p)}$ are ${\displaystyle a\equiv \pm 1(\mathrm{mod}p)}$. Therefore, with the exception of ${\displaystyle \pm 1}$, the factors in the expanded form of ${\displaystyle (p-1)!}$ can be arranged in disjoint pairs such that product of each pair is congruent to 1 modulo ${\displaystyle p}$. This proves Wilson's theorem.

For example, for ${\displaystyle p=11}$, one has $${\displaystyle 10!=[(1\cdot 10)]\cdot [(2\cdot 6)(3\cdot 4)(5\cdot 9)(7\cdot 8)]\equiv [-1]\cdot [1\cdot 1\cdot 1\cdot 1]\equiv -1(\mathrm{mod}11).}$$

Proof using Fermat's little theorem

Again, the result is trivial for p = 2, so suppose p is an odd prime, p ≥ 3. Consider the polynomial

${\displaystyle g(x)=(x-1)(x-2)\cdots (x-(p-1)).}$

g has degree p − 1, leading term x^{p − 1}, and constant term (p − 1)!. Its p − 1 roots are 1, 2, ..., p − 1.

Now consider

${\displaystyle h(x)=x^{p-1}-1.}$

h also has degree p − 1 and leading term x^{p − 1}. Modulo p, Fermat's little theorem says it also has the same p − 1 roots, 1, 2, ..., p − 1.

Finally, consider

${\displaystyle f(x)=g(x)-h(x).}$

f has degree at most p − 2 (since the leading terms cancel), and modulo p also has the p − 1 roots 1, 2, ..., p − 1. But Lagrange's theorem says it cannot have more than p − 2 roots. Therefore, f must be identically zero (mod p), so its constant term is (p − 1)! + 1 ≡ 0 (mod p). This is Wilson's theorem.

Proof using elementary Group Theory

Let p be an odd prime. Let ${\displaystyle {\mathbb{F}}_p^{\times }}$ denote the multiplicative group of integers modulo p, such that ${\displaystyle (p-1)!\equiv \prod _{x\in {\mathbb{F}}_p^{\times }}x\mathrm{mod}p}$. Since ${\displaystyle {\mathbb{F}}_p^{\times }}$ is cyclic, there exists a group isomorphism ${\displaystyle \phi :{\mathbb{F}}_p^{\times }\to {\mathbb{Z}}_{p-1}}$, where ${\displaystyle {\mathbb{Z}}_{p-1}}$ is the additive group of integers modulo p - 1. Therefore:

${\displaystyle \phi \left(\prod _{x\in {\mathbb{F}}_p^{\times }}x\right)=\sum _{x\in {\mathbb{F}}_p^{\times }}\phi (x)=\sum _{n\in {\mathbb{Z}}_{p-1}}n\equiv \frac{p(p-1)}{2}\mathrm{mod}(p-1)}$

Since p was an odd prime, ${\displaystyle \frac{p(p-1)}{2}}$ has order 2 inside ${\displaystyle {\mathbb{Z}}_{p-1}}$. Since isomorphisms preserve the orders of elements, it follows that ${\displaystyle {\phi }^{-1}\left(\frac{p(p-1)}{2}\right)=\prod _{x\in {\mathbb{F}}_p^{\times }}x}$ also has order exactly 2. The only such element in ${\displaystyle {\mathbb{F}}_p^{\times }}$ is ${\displaystyle p-1}$.

Proof using the Sylow theorems

It is possible to deduce Wilson's theorem from a particular application of the Sylow theorems. Let p be a prime. It is immediate to deduce that the symmetric group ${\displaystyle S_p}$ has exactly ${\displaystyle (p-1)!}$ elements of order p, namely the p-cycles ${\displaystyle C_p}$. On the other hand, each Sylow p-subgroup in ${\displaystyle S_p}$ is a copy of ${\displaystyle C_p}$. Hence it follows that the number of Sylow p-subgroups is ${\displaystyle n_p=(p-2)!}$. The third Sylow theorem implies

${\displaystyle (p-2)!\equiv 1(\mathrm{mod}p).}$

Multiplying both sides by (p − 1) gives

${\displaystyle (p-1)!\equiv p-1\equiv -1(\mathrm{mod}p),}$

that is, the result.

Applications

Primality tests

In practice, Wilson's theorem is useless as a primality test because computing (n − 1)! modulo n for large n is computationally complex.

Quadratic residues

Using Wilson's Theorem, for any odd prime p = 2m + 1, we can rearrange the left hand side of $${\displaystyle 1\cdot 2\cdots (p-1)\equiv -1(\mathrm{mod}p)}$$ to obtain the equality $${\displaystyle 1\cdot (p-1)\cdot 2\cdot (p-2)\cdots m\cdot (p-m)\equiv 1\cdot (-1)\cdot 2\cdot (-2)\cdots m\cdot (-m)\equiv -1(\mathrm{mod}p).}$$ This becomes $${\displaystyle \prod _{j=1}^m{j}^2\equiv (-1{)}^{m+1}(\mathrm{mod}p)}$$ or $${\displaystyle (m!{)}^2\equiv (-1{)}^{m+1}(\mathrm{mod}p).}$$ We can use this fact to prove part of a famous result: for any prime p such that p ≡ 1 (mod 4), the number (−1) is a square (quadratic residue) mod p. For this, suppose p = 4k + 1 for some integer k. Then we can take m = 2k above, and we conclude that (m!)² is congruent to (−1) (mod p).

Formulas for primes

Wilson's theorem has been used to construct formulas for primes, but they are too slow to have practical value.

p-adic gamma function

Wilson's theorem allows one to define the p-adic gamma function.

Gauss's generalization

Gauss proved that $${\displaystyle \prod _{\genfrac{}{}{0ex}{}{k=1}{gcd(k,m)=1}}^{m-1}k\equiv \{\begin{array}{ll}-1(\mathrm{mod}m)& \text{if }m=4,p^{\alpha },2p^{\alpha }\\ 1(\mathrm{mod}m)& \text{otherwise}\end{array}}$$ where p represents an odd prime and ${\displaystyle \alpha }$ a positive integer. That is, the product of the positive integers less than m and relatively prime to m is one less than a multiple of m when m is equal to 4, or a power of an odd prime, or twice a power of an odd prime; otherwise, the product is one more than a multiple of m. The values of m for which the product is −1 are precisely the ones where there is a primitive root modulo m.