Wilson's Theorem/Necessary Condition/Proof 1
Theorem
Let $p$ be a prime number.
Then:
- $\paren {p - 1}! \equiv -1 \pmod p$
Proof
If $p = 2$ the result is obvious.
Therefore we assume that $p$ is an odd prime.
Let $p$ be prime.
Consider $n \in \Z, 1 \le n < p$.
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 $\paren {n'}' = 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 = \paren {n + 1} \paren {n - 1}$ from Difference of Two Squares.
So either $n + 1 \divides p$ or $n - 1 \divides p$.
Observe that these cases do not occur simultaneously, as their difference is $2$, and $p$ is an odd prime.
From Negative Number is Congruent to Modulus minus Number‎:
- $p - 1 \equiv -1 \pmod p$
Hence $n = 1$ or $n = p - 1$.
So, we have that $\paren {p - 1}!$ 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 Negative Number is Congruent to Modulus minus Number:
- $\paren {p - 1}! \equiv -1 \pmod p$
$\blacksquare$
Source of Name
This entry was named for John Wilson.
Historical Note
The proof of Wilson's Theorem 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 in $1682$ or $1683$ (accounts differ).
It was in fact finally proved by Lagrange in $1793$.
Sources
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.5$: Permutations and Factorials: Exercise $13$