Wilson’s Theorem

Wilson’s Theorem provides another way to find prime numbers. Its proof is surprisingly short and elegant.

Statement

Wilson’s Theorem states that:

\[(n-1)! \equiv -1 \space (\text{mod} \space n)\]

This means:

Any integer \(n>1\) is a prime number iff \((n-1)!+1\) is divisible by \(n\).

Proof

Inverses in residue classes

Since the residue classes (mod \(p\)) are a field, every non-zero \(a\) has a unique multiplicative inverse, \(a^*\). This means \(a(a^*) \equiv 1 \space \text{mod} \space p\).

Two numbers with inverses equal to itself

If \(a=a^*\), we have \(a^2 \equiv 1 \space \text{mod} \space p\). When will this happen?

Notice that this is equivalent to

\[p \vert a^2-1\]

This is equivalent to :

\[p \vert a \pm 1\]

which implies:

\(a \equiv \pm 1 \space (\text{mod} \space p)\).

Therefore if \(a = 1\) or \(a=p-1\), its inverse is equal to itself.

Conclusion

Remember that :

\((p - 1)! \equiv 1 \times 2 \times 3 \times \ldots \times (p - 2) \times (p - 1)\) . As the residue classes form a field, and the elements in \((p-1)!\) “span” all the residue classes, we can pair off each term, other than \(1\) and \(p-1\).

As an illustration:

\[\begin{aligned} 12! & = 1 \times 2 \times 3 \times 4 \times 5 \times 6 \times 7 \times 8 \times 9 \times 10 \times 11 \times 12 \\ & = 1 \times (2 \times 6) \times (3 \times 4) \times (5 \times 9) \times (7 \times 8) \times (10 \times 11) \times 12 \\ & \equiv 1 \times 1 \times 1 \times 1 \times 1 \times 1 \times 12 \\ & \equiv 12 \equiv -1 \quad (\bmod \space 13) \end{aligned}\]

Therefore, \((n-1)! \equiv -1 \space (\text{mod} \space n)\)

Credits

I am inspired by the video below:

as well as this PDF.

Exercises for the reader

• Show that \(p \vert ab\) implies \(p \vert a\) or \(p \vert b\)
• Define an equivalent class. Show that equivalent classes form a field.
• Is Wilson’s Theorem useful as a primality test?