Wilson's Theorem
Contents |
Theorem
A positive integer $p$ is a prime iff $\left({p-1}\right)! \equiv -1 \pmod {p}$.
Proof
If $p = 2$ the result is obvious.
Therefore we assume that $p$ is an odd prime.
Sufficient Condition
Consider $n \in \Z, 1 \le n < p$. Then as $p$ is prime, $n \perp p$.
From Law of Inverses (Modulo Arithmetic), we have:
- $\exists n' \in \Z, 1 \le n' < p: n n' \equiv 1 \pmod p$
By Solution of Linear Congruence, for each $n$ there is exactly one such $n'$, and $\left({n'}\right)' = n$.
So, provided $n \ne n'$, we can pair any given $n$ from $1$ to $p$ with another $n'$ from $1$ to $p$.
We are then left with the numbers such that $n = n'$.
Then we have $n^2 \equiv 1 \pmod p$.
Consider $n^2 - 1 = \left({n+1}\right) \left({n-1}\right)$ from Difference of Two Squares.
So either $n + 1 \backslash p$ or $n - 1 \backslash p$.
Observe that these cases do not occur simultaneously, as their difference is $2$, and $p$ is an odd prime.
From Congruence Modulo Negative Number‎, we have that $p - 1 \equiv -1 \pmod p$.
Hence $n = 1$ or $n = p - 1$.
So, we have that $\left({p - 1}\right)!$ consists of numbers multiplied together as follows:
- in pairs whose product is congruent to $1 \pmod p$
- the numbers $1$ and $p - 1$.
The product of all these numbers is therefore congruent to $1 \times 1 \times \cdots \times 1 \times p - 1 \pmod p$ by modulo multiplication.
From Congruence Modulo Negative Number we therefore have that $\left({p - 1}\right)! \equiv -1 \pmod p$.
Necessary Condition
Now assume $p$ is composite, and $q$ is a prime such that $q \backslash p$.
Then both $p$ and $\left({p-1}\right)!$ are divisible by $q$.
If the congruence $\left({p-1}\right)! \equiv -1 \pmod p$ were satisfied, we would have $\left({p-1}\right)! \equiv -1 \pmod q$.
However, this amounts to $0 \equiv -1 \pmod q$, a contradiction.
Hence for $p$ composite, the congruence $\left({p-1}\right)! \equiv -1 \pmod p$ cannot hold.
$\blacksquare$
Historical Note
This proof was attributed to John Wilson by Edward Waring in his 1770 edition of Meditationes Algebraicae.
It was first stated by Ibn al-Haytham ("Alhazen").
It appears also to have been known to Gottfried Leibniz before 1663.
It was in fact finally proved by Lagrange in 1793.
Sources
- Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (1968): $\S 1.2.5$: Exercise $13$
- George E. Andrews: Number Theory (1971): $\S 3.3$: Theorem $3.5$, $\S 4.1$: Example $4.3$
