Wilson's theorem

Wilson's Theorem in number theory was first discovered by John Wilson, a student of the English mathematician Edward Waring. Waring announced the theorem in 1770, although neither could prove it. Lagrange gave the first proof in 1771. There is evidence that Leibniz was aware of the result a century earlier, but he never published it.

Wilson's Theorem states that a number n > 1 is prime if and only if:

<math>(n-1)!\ \equiv\ -1\ (\mbox{mod}\ n)</math>

This is proved using the fact that if p is an odd prime, then the numbers {1, 2, ... p-1} form a group under multiplication modulo p. Therefore each number i in 2 ≤ i ≤ p-2 has a unique "partner" (inverse) j such that 2 ≤ j ≤ p-2 and ij is 1 mod p (1 is its own inverse, and so is p-1, but no other element has this property, because p is prime.) As 1(p-1) is -1 mod p, the result follows. If p = 2, the result is trivial to check. For the converse, suppose the congruence holds for a composite n, and note that then n has a proper divisor d with 1 < d < n. Clearly, d divides (n-1)! But by the congruence, d also divides (n-1)! + 1, so that d divides 1, a contradiction.

Here is another proof of the first direction: Suppose p is an odd prime. Consider the polynomial

<math>g(x)=(x-1)(x-2) \cdots (x-(p-1))</math>

Recall that if f(x) is a nonzero polynomial of degree d over a field F, then f(x) has at most d roots over F. Now, with g(x) as above, consider the polynomial

<math>f(x)=g(x)-(x^{p-1}-1)</math>

Since the leading coefficients cancel, we see that f(x) is a polynomial of degree p-2. Reducing mod p, we see that f(x) has at most p-2 roots mod p. But by Fermat's theorem, each of the elements 1,2,...,p-1 is a root of f(x). This is impossible, unless f(x) is identically zero mod p, i.e. unless each coefficient of f(x) is divisible by p.

But since p is odd, the constant term of f(x) is just (p-1)! + 1, and the result follows.

Wilson's theorem is useless as a primality test, since computing (n-1)! is difficult for large n.

Using Wilson's Theorem, we have for any prime p:

<math>1\cdot 2\cdots (p-1)\ \equiv\ -1\ (\mbox{mod}\ p)</math>

<math>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\ (\mbox{mod}\ p)</math>

where p = 2m + 1. This becomes:

<math>\prod_{j=1}^m\ j^2\ \equiv(-1)^{m+1}\ (\mbox{mod}\ p)</math>

And so primality is determined by the quadratic residues of p. We can use this fact to prove part of a famous result: -1 is a square (quadratic residue) mod p if p ≡1 (mod 4). For suppose p = 4k + 1 for some integer k. Then we can take m=2k above, and we conclude that

<math>\prod_{j=1}^{2k}\ j^2\ =(\prod_{j=1}^{2k}\ j)^{2}\equiv(-1)^{2k+1}\ =-1(\mbox{mod}\ p)</math>

There is also a generalization of Wilson's theorem, due to Gauss.

<math>\prod_{1\leq a<m, \ (a,m)=1}a \equiv \{\begin{matrix} -1 (\mbox{mod }m) & \mbox{if } m=4,p^\alpha,2p^\alpha \\ 1(\mbox{mod }m) & \mbox{otherwise}\end{matrix} </math>

where p is an odd prime.