Wilson's Theorem

The following characterization of prime numbers, from the 1770s, is called ``Wilson's Theorem'', though it was first proved by Lagrange.

Proposition 2.1 (Wilson's Theorem)   An integer $ p>1$ is prime if and only if $ (p-1)! \equiv -1 \pmod{p}.$

For example, if $ p=3$ , then $ (p-1)! = 2\equiv -1\pmod{3}$ . If $ p=17$ , then

$\displaystyle (p-1)! = 20922789888000 \equiv -1\pmod{17}.$

But if $ p=15$ , then

$\displaystyle (p-1)! = 87178291200 \equiv 0 \pmod{15},$

so $ 15$ is composite. Thus Wilson's theorem could be viewed as a primality test, though, from a computational point of view, it is probably one of the world's least efficient primality tests since computing $ (n-1)!$ takes so many steps.

Proof. The statement is clear when $ p=2$ , so henceforth we assume that $ p>2$ . We first assume that $ p$ is prime and prove that $ (p-1)! \equiv -1\pmod{p}$ . If $ a\in\{1,2,\ldots,p-1\}$ then the equation

$\displaystyle ax\equiv 1\pmod{p}
$

has a unique solution $ a'\in\{1,2,\ldots,p-1\}$ . If $ a=a'$ , then $ a^2\equiv 1\pmod{p}$ , so $ p\mid a^2-1 = (a-1)(a+1)$ , so $ p\mid (a-1)$ or $ p\mid (a+1)$ , so $ a\in\{1,p-1\}$ . We can thus pair off the elements of $ \{2,3,\ldots,p-2\}$ , each with their inverse. Thus

$\displaystyle 2\cdot 3 \cdot \cdots \cdot (p-2) \equiv 1\pmod{p}.
$

Multiplying both sides by $ p-1$ proves that $ (p-1)! \equiv -1\pmod{p}$ .

Next we assume that $ (p-1)! \equiv -1\pmod{p}$ and prove that $ p$ must be prime. Suppose not, so that $ p\geq 4$ is a composite number. Let $ \ell$ be a prime divisor of $ p$ . Then $ \ell<p$ , so $ \ell\mid (p-1)!$ . Also, by assumption,

$\displaystyle \ell \mid p \mid ((p-1)! + 1).
$

This is a contradiction, because a prime can not divide a number $ a$ and also divide $ a+1$ , since it would then have to divide $ (a+1) - a=1$ . $ \qedsymbol$

Example 2.1   We illustrate the key step in the above proof in the case $ p=17$ . We have

$\displaystyle 2\cdot 3 \cdots 15
= (2\cdot 9)\cdot(3\cdot 6)\cdot(4\cdot 13)\cdot
(5\cdot 7)\cdot(8\cdot 15)\cdot(10\cdot 12)\cdot(14\cdot 11)
\equiv 1\pmod{17},$

where we have paired up the numbers $ a, b$ for which $ ab\equiv 1\pmod{17}$ .

SAGE Example 2.1   We use SAGE to create a table of triples; the first column contains $ n$ , the second column contains $ (n-1)!$ modulo $ n$ , and the third contains $ -1$ modulo $ n$ . Notice that the first columns contains a prime precisely when the second and third columns are equal. (The ... notation indicates indentation in SAGE; you should not type the dots in explicitly.)
sage: for n in range(1,10):
...    print n, factorial(n-1) % n, -1 % n
1 0 0
2 1 1
3 2 2
4 2 3
5 4 4
6 0 5
7 6 6
8 0 7
9 0 8

William 2007-06-01