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

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

But if $p=15$ , then

$$(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

$$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

$$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,

$$\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

$$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