Wilson's theorem

In algebra and number theory, Wilson's theorem states that a natural number n > 1 is a prime number if and only if the product of all the positive integers less than n is one less than a multiple of n. That is (using the notations of modular arithmetic), the factorial \((n - 1)! = 1 \times 2 \times 3 \times \cdots \times (n - 1)\) satisfies

\((n-1)!\ \equiv\; -1 \pmod n\)

exactly when n is a prime number. In other words, any integer n > 1 is a prime number if, and only if, (n − 1)! + 1 is divisible by n.

The theorem was first stated by Ibn al-Haytham c. 1000 AD. Edward Waring announced the theorem in 1770 without proving it, crediting his student John Wilson for the discovery. Lagrange gave the first proof in 1771. There is evidence that Leibniz was also aware of the result a century earlier, but never published it.

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, \((n-1)!\ \equiv n-1\bmod\ n\) when n is prime. The background color is blue for prime values of n, gold for composite values.

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

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

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

Using Wilson's Theorem, for any odd prime p = 2m + 1, we can rearrange the left hand side of \[1\cdot 2\cdots (p-1)\ \equiv\ -1\ \pmod{p}\] to obtain the equality \[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 \[\prod_{j=1}^m\ j^2\ \equiv(-1)^{m+1} \pmod{p}\] or \[(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).

Gauss proved that \[\prod_{k = 1 \atop \gcd(k,m)=1}^{m-1} \!\!k \ \equiv \begin{cases} -1 \pmod{m} & \text{if } m=4,\;p^\alpha,\;2p^\alpha \\ \;\;\,1 \pmod{m} & \text{otherwise} \end{cases}\] where p represents an odd prime and \(\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.