Composite modulus

If n is composite it is divisible by some prime number q, where 2 ≤ q ≤ n − 2. Because ${\displaystyle q}$ divides ${\displaystyle n}$, let ${\displaystyle n=qk}$ for some integer ${\displaystyle k}$. Suppose for the sake of contradiction that ${\displaystyle (n-1)!}$ were congruent to −1 (mod n) where n is composite. Then (n-1)! would also be congruent to −1 (mod q) as ${\displaystyle (n-1)!\equiv -1\ ({\text{mod}}\ n)}$ implies that ${\displaystyle (n-1)!=nm-1=(qk)m-1=q(km)-1}$ for some integer ${\displaystyle m}$ which shows (n-1)! being congruent to -1 (mod q). But (n − 1)! ≡ 0 (mod q) by the fact that q is a term in (n-1)! making (n-1)! a multiple of q. A contradiction is now reached.

In fact, more is true. With the sole exception of 4, where 3! = 6 ≡ 2 (mod 4), if n is composite then (n − 1)! is congruent to 0 (mod n). The proof is divided into two cases: First, if n can be factored as the product of two unequal numbers, n = ab, where 2 ≤ a < b ≤ n − 2, then both a and b will appear in the product 1 × 2 × ... × (n − 1) = (n − 1)! and (n − 1)! will be divisible by n. If n has no such factorization, then it must be the square of some prime q, q > 2. But then 2q < q² = n, both q and 2q will be factors of (n − 1)!, and again n divides (n − 1)!.

Prime modulus

Elementary proof

The result is trivial when p = 2, so assume p is an odd prime, p ≥ 3. Since the residue classes (mod p) are a field, every non-zero a has a unique multiplicative inverse, a⁻¹. Lagrange's theorem implies that the only values of a for which a ≡ a⁻¹ (mod p) are a ≡ ±1 (mod p) (because the congruence a² ≡ 1 can have at most two roots (mod p)). Therefore, with the exception of ±1, the factors of (p − 1)! can be arranged in disjoint pairs such that product of each pair is congruent to 1 modulo p. This proves Wilson's theorem.

For example, for 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{\pmod {11}}.}$$

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, and much faster primality tests are known (indeed, even trial division is considerably more efficient).^{[citation needed]}

Used in the other direction, to determine the primality of the successors of large factorials, it is indeed a very fast and effective method. This is of limited utility, however.^{[citation needed]}

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\ {\pmod {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{\pmod {p}}.}$$

This becomes

$${\displaystyle \prod _{j=1}^{m}\ j^{2}\ \equiv (-1)^{m+1}{\pmod {p}}}$$

or

$${\displaystyle (m!)^{2}\equiv (-1)^{m+1}{\pmod {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.