Wilson’s Theorem

Wilson’s Theorem is a test for primality.  It is inefficient for large numbers since factorials ($n!$) grow very fast.  Nevertheless, it has its uses because of its simplicity.

It was conjectured by Wilson and published in a book by Waring in 1770.  It was proved by Lagrange in 1773.  A manuscript of 1682 indicates that Leibniz was aware of the result.

 

If and only if $p$ is a prime number, then

$\displaystyle \frac {(p-1)! + 1}{p}$

is a natural number.

In modular arithmetic, we write Wilson’s Theorem as the congruence

$\bbox[10px,border:2px solid black]{(p-1)!\equiv -1\pmod p}$

 

The converse of Wilson’s Theorem is also true.

If $n \gt 1$ is a natural number and $(n-1)!\equiv -1\pmod n$, then $n$ is prime.

 

For a composite number, $n$, $(n-1)!\equiv 0\pmod n$ except when $n = 4$.

For small values we have

$\begin{array}{r|r|r|r} n & (n-1)! & (n-1)!\pmod n & Prime?\\ \hline 2 & 1 & 1 & T\\ 3 & 2 & 2 & T\\ 4 & 6 & 2 & F\\ 5 & 24 & 4 & T\\ 6 & 120 & 0 & F\\ 7 & 720 & 6 & T\\ 8 & 5040 & 0 & F\\ 9 & 40320 & 0 & F\\ 10 & 362880 & 0 & F\\ 11 & 3628800 & 10 & T \end{array}$

For example :

$7$ is prime.

$(7-1)! = 6! = 1 \times 2 \times 3 \times 4 \times 5 \times 6 = 720$

Using

$\displaystyle \frac {(p-1)! +1}{p} = n$

We have

$\displaystyle \frac {6! + 1}{7} = \frac {721}{7} = 103$

In modular arithmetic, we write this as the congruence

$6! \equiv -1 \pmod 7$

One way to explain how this works is by using modular multiplicative inverses.

Ordinary multiplication gives :

$\begin {array}{c|cccccc} \times & 1 & 2 & 3 & 4 & 5 & 6\\ \hline 1 & 1 & 2 & 3 & 4 & 5 & 6\\ 2 & 2 & 4 & 6 & 8 & 10 & 12\\ 3 & 3 & 6 & 9 & 12 & 15 & 18\\ 4 & 4 & 8 & 12 & 16 & 20 & 24\\ 5 & 5 & 10 & 15 & 20 & 25 & 30\\ 6 & 6 & 12 & 18 & 24 & 30 & 36 \end{array}$

Multiplication in modulo $7$ gives the residues (remainders) :

$\begin {array}{c|cccccc} \times & 1 & 2 & 3 & 4 & 5 & 6\\ \hline 1 & 1 & 2 & 3 & 4 & 5 & 6\\ 2 & 2 & 4 & 6 & 1 & 3 & 5\\ 3 & 3 & 6 & 2 & 5 & 1 & 4\\ 4 & 4 & 1 & 5 & 2 & 6 & 3\\ 5 & 5 & 3 & 1 & 6 & 4 & 2\\ 6 & 6 & 5 & 4 & 3 & 2 & 1 \end{array}$

By inspection of the above table, we see that $2$ and $4$ and $3$ and $5$ are modular multiplicative inverses of each other since $1$ is the multiplicative identity. $1$ and $6$ are both self-inverse.

Thus, we can write

$6! \equiv 1 \times 1 \times 1 \times 1 \times 1 \times 6 \pmod 7 \equiv 1 \times 6 \pmod 7 \equiv -1 \pmod 7$

 

© OldTrout $2019$