📂Number Theory

Proof of Wilson's Theorem

Theorem¹

For a prime $p$ greater than 2, $(p-1)! \equiv -1 \pmod{p}$

Explanation

Even if not quite as much as Fermat’s little theorem, Wilson’s theorem is also useful here and there. Its very form makes it convenient for computing products of consecutive numbers.

Proof

We introduce two proofs: Proof 1, which uses the existence and uniqueness of multiplicative inverses in $\pmod{p}$, and Proof 2, which uses the properties of primitive roots and Fermat’s little theorem. Proof 2 is a bit harder but a bit more refined. Familiarize yourself with whichever proof suits your taste.

Proof 1 Using the Properties of Primitive Roots

If $i$ is an integer greater than 1 and less than $(p-1)$, then $(p-1)!$ can be expressed as follows. $$ (p-1)! = 1 \cdot 2 \cdot 3 \cdots i \cdots (p-2) \cdot (p-1) $$

Multiplicative inverses in congruences: The ring of integers $\mathbb{Z}_{p}$ is a field of integers if $p$ is a prime. In other words, if $\gcd(p,a) = 1$, then the equation $a x \equiv 1 \pmod{p}$ has exactly one solution in $0<x<p$.

Since every integer must have exactly one inverse in $\pmod{p}$, all integers except $1$ and $(p-1)$ will be multiplied by some other integer to become $1$. Because $p$ is a prime that is not even, there are exactly an even number of such $i$, and what ultimately remains is $$ (p-1)! \equiv 1 \cdot 1 \cdot 1 \cdots 1 \cdot (p-1) \pmod{p} $$ Since $(p-1) \equiv -1 \pmod{p}$, it holds that $(p-1)! \equiv -1 \pmod{p}$.

■

For example, looking at $(7-1)! \equiv 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \pmod{7}$, since $$ 2 \cdot 4 \equiv 8 \equiv 1 \pmod{7} \\ 3 \cdot 5 \equiv 15 \equiv 1 \pmod{7} $$ we get $$ (7-1)! \equiv 1 \cdot 1 \cdot 1 \cdot 6 \equiv 6 \equiv -1 \pmod{7} $$ If you compute a few somewhat larger primes by hand, you will definitely get a feel for it.

Proof 2 Using Fermat’s Little Theorem

If $a$ is a primitive root of a prime $p$, then $(p-1)!$ can be expressed as follows.

$$ \begin{align*} (p-1)! & \equiv 1 \cdot 2 \cdot 3 \cdots (p-2) \cdot (p-1) \pmod{p} \\ & \equiv a^{1} \cdot a^{2} \cdot a^{3} \cdots a^{p-2} \cdot a^{p-1} \pmod{p} \\ & \equiv a^{{p(p-1)} \over {2}} \pmod{p} \\ & \equiv a^{ { {p-1} \over 2 } p } \pmod{p} \end{align*} $$

Fermat’s little theorem: $a^{p-1} \equiv 1 \pmod{p}$

Since $a$ is a primitive root of $p$, by Fermat’s little theorem, $a^{ { {p-1} \over 2 } p } \equiv (-1)^p \pmod{p}$ holds. Meanwhile, $p$ is a prime greater than 2 and thus odd, so we obtain the following. $$ (p-1)! \equiv (-1)^p \equiv -1 \pmod{p} $$

■