[proofplan] We treat $p = 2$ directly, then assume $p > 2$. For each non-zero residue modulo $p$, Bezout's identity gives a unique inverse residue in $\{1,\dots,p-1\}$. The only residues equal to their own inverses are $1$ and $p-1$, so every remaining residue pairs with a distinct inverse, and the product of each such pair is congruent to $1$ modulo $p$. [/proofplan] [step:Verify the congruence for $p = 2$ and reduce to odd primes] If $p = 2$, then \begin{align*} (p-1)! = 1! = 1 \equiv -1 \pmod{2}, \end{align*} because $1 - (-1) = 2$ is divisible by $2$. Hence the theorem holds for $p = 2$. For the remainder of the proof, assume $p > 2$. Since $p$ is prime and $p > 2$, $p$ is odd. [/step] [step:Identify the only self-inverse non-zero residues modulo $p$] Let $S := \{1,2,\dots,p-1\}$ be the set of standard representatives of the non-zero residue classes modulo $p$. Suppose $x \in S$ satisfies $x^2 \equiv 1 \pmod{p}$. Then $p \mid x^2 - 1$, so \begin{align*} p \mid (x-1)(x+1). \end{align*} Since $p$ is prime, [Euclid's Lemma](/theorems/729) gives $p \mid x-1$ or $p \mid x+1$. Therefore $x \equiv 1 \pmod{p}$ or $x \equiv -1 \pmod{p}$. With $x \in S$, these alternatives mean $x = 1$ or $x = p-1$. Conversely, both $1$ and $p-1$ satisfy \begin{align*} 1^2 \equiv 1 \pmod{p}, \qquad (p-1)^2 \equiv (-1)^2 \equiv 1 \pmod{p}. \end{align*} Thus the only self-inverse elements of $S$ are $1$ and $p-1$. [guided] We want to find exactly which non-zero residues modulo $p$ are equal to their own inverses. Define \begin{align*} S := \{1,2,\dots,p-1\}. \end{align*} An element $x \in S$ is self-inverse modulo $p$ precisely when $x^2 \equiv 1 \pmod{p}$. This congruence is equivalent to divisibility by $p$: \begin{align*} x^2 \equiv 1 \pmod{p} \iff p \mid x^2 - 1 \iff p \mid (x-1)(x+1). \end{align*} Now we use the primality hypothesis. Since $p$ is prime, Euclid's Lemma applies to the divisibility $p \mid (x-1)(x+1)$ and gives \begin{align*} p \mid x-1 \quad\text{or}\quad p \mid x+1. \end{align*} Equivalently, \begin{align*} x \equiv 1 \pmod{p} \quad\text{or}\quad x \equiv -1 \pmod{p}. \end{align*} Because $x$ is chosen from the representative set $S = \{1,\dots,p-1\}$, the first congruence gives $x = 1$, while the second gives $x = p-1$. Conversely, \begin{align*} 1^2 \equiv 1 \pmod{p}, \qquad (p-1)^2 \equiv (-1)^2 \equiv 1 \pmod{p}. \end{align*} So the self-inverse residues in $S$ are exactly $1$ and $p-1$. [/guided] [/step] [step:Pair every remaining residue with its distinct inverse] For each $a \in S$, since $1 \le a \le p-1$, we have $\gcd(a,p)=1$. By Bezout's Identity, there exist integers $u_a,v_a \in \mathbb{Z}$ such that \begin{align*} a u_a + p v_a = 1. \end{align*} Let $a^{-1} \in S$ denote the unique representative of the congruence class of $u_a$ modulo $p$. Then \begin{align*} a a^{-1} \equiv 1 \pmod{p}. \end{align*} The inverse representative is unique because if $b,c \in S$ and $ab \equiv ac \pmod{p}$, then $p \mid a(b-c)$, and Euclid's Lemma, together with $p \nmid a$, gives $p \mid b-c$; since $b,c \in S$, this implies $b=c$. Let $T := S \setminus \{1,p-1\} = \{2,3,\dots,p-2\}$. The map \begin{align*} \iota: T &\to T \\ a &\mapsto a^{-1} \end{align*} is well-defined, satisfies $\iota(\iota(a)) = a$, and has no fixed point by the previous step. Hence $T$ is partitioned into disjoint two-element sets $\{a,a^{-1}\}$, and each such pair has product congruent to $1$ modulo $p$. [guided] The goal is to justify the inverse-pairing, not merely assert it. Let \begin{align*} S := \{1,2,\dots,p-1\}. \end{align*} Take any $a \in S$. Since $p$ is prime and $1 \le a \le p-1$, the integer $p$ does not divide $a$, so $\gcd(a,p)=1$. By Bezout's Identity, there exist integers $u_a,v_a \in \mathbb{Z}$ such that \begin{align*} a u_a + p v_a = 1. \end{align*} Reducing this equality modulo $p$ gives \begin{align*} a u_a \equiv 1 \pmod{p}. \end{align*} Let $a^{-1} \in S$ be the unique representative of the congruence class of $u_a$ modulo $p$. Then \begin{align*} a a^{-1} \equiv 1 \pmod{p}. \end{align*} We also need uniqueness of the inverse representative. Suppose $b,c \in S$ both satisfy \begin{align*} ab \equiv 1 \pmod{p}, \qquad ac \equiv 1 \pmod{p}. \end{align*} Subtracting the congruences gives \begin{align*} a(b-c) \equiv 0 \pmod{p}, \end{align*} so $p \mid a(b-c)$. Since $p \nmid a$, Euclid's Lemma gives $p \mid b-c$. But $b,c \in \{1,\dots,p-1\}$, so $b-c$ lies strictly between $-(p-1)$ and $p-1$. The only multiple of $p$ in that range is $0$, hence $b=c$. Now remove the two self-inverse residues: \begin{align*} T := S \setminus \{1,p-1\} = \{2,3,\dots,p-2\}. \end{align*} Define the inverse map \begin{align*} \iota: T &\to T \\ a &\mapsto a^{-1}. \end{align*} The map lands in $T$ because if $a^{-1}$ were $1$ or $p-1$, then taking inverses would force $a$ to be $1$ or $p-1$. Also $\iota(\iota(a)) = a$ by uniqueness of inverse representatives. Finally, $\iota(a) \ne a$ for every $a \in T$, because the previous step proved that the only self-inverse residues in $S$ are $1$ and $p-1$. Therefore $T$ is partitioned into disjoint two-element inverse pairs $\{a,a^{-1}\}$, and each pair satisfies \begin{align*} a a^{-1} \equiv 1 \pmod{p}. \end{align*} [/guided] [/step] [step:Multiply the inverse pairs to compute $(p-1)!$ modulo $p$] The product defining $(p-1)!$ is the product of all elements of $S$. The two unpaired elements are $1$ and $p-1$, and every element of $T$ belongs to exactly one inverse pair. Therefore \begin{align*} (p-1)! &= \prod_{a \in S} a \\ &\equiv 1 \cdot (p-1) \cdot \prod_{\{a,a^{-1}\} \subset T} a a^{-1} \pmod{p} \\ &\equiv 1 \cdot (p-1) \cdot 1 \pmod{p} \\ &\equiv p-1 \pmod{p} \\ &\equiv -1 \pmod{p}. \end{align*} Thus \begin{align*} (p-1)! \equiv -1 \pmod{p}, \end{align*} which proves Wilson's theorem. [/step]