Wilson's Theorem

Lemma 1: Let $p \in \mathbb{Z}$ be any prime number. Then the congruence $x^2 \equiv 1 \pmod p$ has exactly two solutions which are $x = 1$ and $x = p - 1$.

• Proof: We begin by verifying that $x = 1$ and $x = p - 1$ are indeed solutions. Clearly we have that:

(1)

\begin{align} \quad 1^2 = 1 \equiv 1 \pmod p \end{align}

(2)

\begin{align} \quad (p - 1)^2 = p^2 - 2p + 1 \equiv 1 \pmod p \end{align}

• So let $x_0 \in \mathbb{Z}$ be any solution to $x^2 \equiv 1 \pmod p$. Then $x_0^2 \equiv 1 \pmod p$, so $p \mid (x_0^2 - 1 )$ and hence we have that:

(3)

\begin{align} \quad p \mid (x_0 + 1)(x_0 - 1) \end{align}

• Since $p$ is a prime number we must have that either $p \mid x_0 + 1$ in which case $x_0 = p - 1$, OR, $p \mid x_0 - 1$ in which case $x_0 = 1$. $\blacksquare$

Lemma 2: Let $a, b, a', b', p \in \mathbb{Z}$, $a, b, a', b' \in \{ 1, 2, ..., p -1 \}$ where $a'$ denotes the inverse of $a$ and $b'$ denotes the inverse of $b$ modulo $p$, and let $p$ be an odd prime. Suppose that $a'$ be a solution to the linear congruence $ax \equiv 1 \pmod p$. Then a \equiv b \pmod p $]] if and only if $a' \equiv b' \pmod p$.

• Proof: $\Rightarrow$ Suppose that $a \equiv b \pmod p$. Since $a', b' \in \{ 1, 2, ..., p - 1 \}$ we have that $(a', p) = 1$ and $(b', p) = 1$. Hence:

(4)

\begin{align} \quad a(a'b') & \equiv b(a'b') \pmod p \\ \quad (aa')b' & \equiv (bb')a' \pmod p \\ \quad b' & \equiv a' \pmod p \end{align}

• $\Leftarrow$ Conversely, suppose that $a' \equiv b' \pmod p$. Since $a, b \in \{ 1, 2, ..., p - 1 \}$ we have that $(a, p) = 1$ and $(b, p) = 1$. Hence:

(5)

\begin{align} \quad a'(ab) & \equiv b'(ab) \pmod p \\ \quad (a'a)b & \equiv (b'b)a \pmod p \\ \quad b & \equiv a \pmod p \quad \blacksquare \end{align}

• $\Leftarrow$

Lemma 3: Let $a, a', p \in \mathbb{Z}$ and let $a'$ denote the inverse of $a$ modulo $p$, and let $p$ be an odd prime. If $a$ is a solution to $ax \equiv 1 \pmod p$ then $a \equiv a' \pmod p$ if and only if $a = 1$ or $a = p - 1$.

• Proof: $\Rightarrow$ Suppose that $a \equiv a' \pmod p$. Then $a^2 \equiv 1 \pmod p$. So by Lemma 1 we must have that $a = 1$ or $a = p - 1$. $\blacksquare$

Theorem 4 (Wilson's Theorem): Let $p \in \mathbb{Z}$. Then $p$ is prime if and only if $(p - 1)! \equiv -1 \pmod p$.

• Proof: $\Rightarrow$ Suppose that $p$ is prime and assume that $p \geq 5$ (the result can be checked for $p = 2$ and $p = 3$ trivially). Then we can separate the numbers $2$, $3$, …, $p - 2$ into $\frac{p - 3}{2}$ pairs of numbers $a$ and their inverses $a'$ modulo $p$ to get:

(6)

\begin{align} 2 \cdot 3 \cdot ... \cdot (p - 2) \equiv 1^{\frac{p - 3}{2}} \pmod p \\ \quad [1 \cdot (p - 1)] \cdot 2 \cdot 3 \cdot ... \cdot (p - 2) \equiv (p - 1) \pmod p \\ (p - 1) ! \equiv -1 \pmod p \quad \blacksquare \end{align}