Wilson's Theorem

# 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}