📂Number Theory

Proof of Wilson's Theorem

Theorem ¹

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

Description

While not quite as famous as Fermat’s Little Theorem, Wilson’s Theorem is also quite useful in various contexts. Its formulation is conveniently suited for calculating the product of consecutive numbers.

Proof

This section introduces two proofs for $\pmod{p}$: Proof 1 utilizing the existence and uniqueness of the multiplicative inverse, and Proof 2 which is a bit more sophisticated, leveraging the properties of a primitive root Primitive root and Fermat’s Little Theorem. Choose the proof that suits your taste.

1

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

Multiplicative Inverse in Congruences: For the prime number $p$, 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 in $\pmod{p}$ must have a unique inverse, all integers except for $1$ and $(p-1)$ will pair up and multiply to give $1$. Since $p$ is an odd prime, there will be exactly an even number of such $i$s, leaving us with $$ (p-1)! \equiv 1 \cdot 1 \cdot 1 \cdots 1 \cdot (p-1) \pmod{p} $$ Hence, $(p-1)! \equiv -1 \pmod{p}$ holds.

■

For instance, for $(7-1)! \equiv 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \pmod{7}$, we have $$ 2 \cdot 4 \equiv 8 \equiv 1 \pmod{7} \\ 3 \cdot 5 \equiv 15 \equiv 1 \pmod{7} $$ and thus $$ (7-1)! \equiv 1 \cdot 1 \cdot 1 \cdot 6 \equiv 6 \equiv -1 \pmod{7} $$ Calculating a few larger primes manually should clarify this further.

2

If we consider $a$ to be a primitive root of the prime number $p$, then we can represent $(p-1)!$ 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$, Fermat’s Little Theorem implies that $a^{ { {p-1} \over 2 } p } \equiv (-1)^p \pmod{p}$ holds. Moreover, since $p$ is a prime greater than 2 and thus odd, we obtain: $$ (p-1)! \equiv (-1)^p \equiv -1 \pmod{p} $$

■