$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 3.2: Wilson's Theorem

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

$$\newcommand{\NN}{\mathbb N}$$
$$\newcommand{\RR}{\mathbb R}$$
$$\newcommand{\QQ}{\mathbb Q}$$
$$\newcommand{\ZZ}{\mathbb Z}$$
$$\newcommand{\Cc}{\mathcal C}$$
$$\newcommand{\Dd}{\mathcal D}$$
$$\newcommand{\Ee}{\mathcal E}$$
$$\newcommand{\Ff}{\mathcal F}$$
$$\newcommand{\Kk}{\mathcal K}$$
$$\newcommand{\Mm}{\mathcal M}$$
$$\newcommand{\Pp}{\mathcal P}$$
$$\newcommand{\ind}{\operatorname{ind}}$$
$$\newcommand{\ord}{\operatorname{ord}}$$

In this section, we prove a nice theorem usually named after an $$18^{\text{th}}$$ century English mathematician ... although it was actually first stated by Ibn al-Haytham nearly $$800$$ years earlier.

First, we need a Lemma.

Lemma $$\PageIndex{1}$$

Let $$p$$ be a prime. Then $$n\in\NN$$ equals its own inverse mod $$p$$ if and only if $$p\mid n+1$$ or $$p\mid n-1$$, i.e., iff $$n\equiv\pm1\pmod{p}$$.

Proof

Say $$p$$ is a prime and $$n\in\NN$$ equals its own inverse mod $$p$$. That means that $$n^2=n\cdot n\equiv1\pmod{p}$$. By definition, $$p\mid n^2-1=(n+1)(n-1)$$. By Proposition 3.1.1, this means that either $$p\mid n+1$$ or $$p\mid n-1$$.

For the converse, suppose $$n\equiv1\pmod{p}$$ or $$n\equiv-1\pmod{p}$$. Then, by Theorem 2.1.1, $$n^2\equiv(\pm 1)^2=1\pmod{p}$$, so $$n$$ equals its own inverse mod $$p$$.

This Lemma is a key step in

Theorem $$\PageIndex{1}$$: Wilson's Theorem

Given $$p\in\NN$$ such that $$p\ge2$$, $$p$$ is prime iff $$(p-1)!\equiv-1\pmod{p}$$.

Proof

Suppose $$p$$ is prime. Consider the terms of $$(p-2)!$$: every one has an inverse mod $$p$$ by Corollary 2.2.1, and only $$1$$ equals its own inverse mod $$p$$ (so would $$p-1$$, but it is not in the product $$(p-2)!$$ by Lemma 3.2.1. Hence in $$(p-1)!$$ we can group the terms into pairs ($$(p-3)/2$$ of these pairs) which are inverses mod $$p$$, leaving out only $$1$$ and $$(p-1)$$. That is $(p-1)! \equiv 1^{(p-3)/2}(p-1) \equiv p-1\equiv -1\pmod{p}$

Conversely, suppose $$p\in\NN$$ satisfies $$p\ge2$$ and $$(p-1)!\equiv-1\pmod{p}$$. We can rewrite that congruence as $$(p-1)!+1\equiv0\pmod{p}$$, or $$p\mid((p-1)!+1)$$.

Now let $$d\in\NN$$ be a divisor of $$p$$ such that $$d\neq p$$. It follows that $$d$$ is one of the numbers in the product $$(p-1)!$$, so $$d\mid(p-1)!$$; also, since $$d\mid p$$ and $$p\mid((p-1)!+1)$$, it follows that $$d\mid((p-1)!+1)$$. Therefore, $$d\mid((p-1)!+1)-(p-1)! = 1$$ by Theorem 1.3.2, which means $$d=1$$.

In other words, if $$d\in\NN$$ is a divisor of $$p$$, it must be either $$p$$ or $$1$$, so $$p$$ is prime.

Example $$\PageIndex{1}$$

Let’s work through one direction of the proof for a simple case, say of $$p=7$$. We start by finding all the inverses of the numbers $$2,\dots,6$$ (by brute force, in this small case): $$2\cdot4\equiv1\pmod{7}$$ and $$3\cdot5\equiv1\pmod{7}$$, meaning that $$2^{-1}\equiv4$$ (or$$4^{-1}\equiv2$$) and $$3^{-1}\equiv5$$ (or $$5^{-1}\equiv3$$).

Then $(p-2)! = 5! = 5\cdot4\cdot3\cdot2\cdot1=(5\cdot3)\cdot(4\cdot2)\equiv1\cdot1\equiv1\pmod{7}$ which in turn means that $(p-1)! = 6! = 6\cdot5!\equiv6\cdot1\equiv6\equiv7-1\equiv-1\pmod{7}\ .$

Notice that Wilson’s Theorem can be used to build a test for primality: see if a number $$n$$ satisfies $$(n-1)!\equiv-1\pmod{n}$$ and, if so, $$n$$ is prime. This is an entirely impractical test, but it is our first example of a simple computational congruence involving an integer which can tell us that that integer is prime.