3.2: Wilson's Theorem
- Page ID
- 28640
\(\newcommand{\RR}{\mathbb R}\)
\(\newcommand{\QQ}{\mathbb Q}\)
\(\newcommand{\ZZ}{\mathbb Z}\)
\(\newcommand{\Cc}{\mathcal C}\)
\(\newcommand{\Dd}{\mathcal D}\)
\(\newcommand{\Ee}{\mathcal E}\)
\(\newcommand{\Ff}{\mathcal F}\)
\(\newcommand{\Kk}{\mathcal K}\)
\(\newcommand{\Mm}{\mathcal M}\)
\(\newcommand{\Pp}{\mathcal P}\)
\(\newcommand{\ind}{\operatorname{ind}}\)
\(\newcommand{\ord}{\operatorname{ord}}\)
In this section, we prove a nice theorem usually named after an \(18^{\text{th}}\) century English mathematician ... although it was actually first stated by Ibn al-Haytham nearly \(800\) years earlier.
First, we need a Lemma.
Lemma \(\PageIndex{1}\)
Let \(p\) be a prime. Then \(n\in\NN\) equals its own inverse mod \(p\) if and only if \(p\mid n+1\) or \(p\mid n-1\), i.e., iff \(n\equiv\pm1\pmod{p}\).
- Proof
-
Say \(p\) is a prime and \(n\in\NN\) equals its own inverse mod \(p\). That means that \(n^2=n\cdot n\equiv1\pmod{p}\). By definition, \(p\mid n^2-1=(n+1)(n-1)\). By Proposition 3.1.1, this means that either \(p\mid n+1\) or \(p\mid n-1\).
For the converse, suppose \(n\equiv1\pmod{p}\) or \(n\equiv-1\pmod{p}\). Then, by Theorem 2.1.1, \(n^2\equiv(\pm 1)^2=1\pmod{p}\), so \(n\) equals its own inverse mod \(p\).
This Lemma is a key step in
Theorem \(\PageIndex{1}\): Wilson's Theorem
Given \(p\in\NN\) such that \(p\ge2\), \(p\) is prime iff \((p-1)!\equiv-1\pmod{p}\).
- Proof
-
Suppose \(p\) is prime. Consider the terms of \((p-2)!\): every one has an inverse mod \(p\) by Corollary 2.2.1, and only \(1\) equals its own inverse mod \(p\) (so would \(p-1\), but it is not in the product \((p-2)!\) by Lemma 3.2.1. Hence in \((p-1)!\) we can group the terms into pairs (\((p-3)/2\) of these pairs) which are inverses mod \(p\), leaving out only \(1\) and \((p-1)\). That is \[(p-1)! \equiv 1^{(p-3)/2}(p-1) \equiv p-1\equiv -1\pmod{p}\]
Conversely, suppose \(p\in\NN\) satisfies \(p\ge2\) and \((p-1)!\equiv-1\pmod{p}\). We can rewrite that congruence as \((p-1)!+1\equiv0\pmod{p}\), or \(p\mid((p-1)!+1)\).
Now let \(d\in\NN\) be a divisor of \(p\) such that \(d\neq p\). It follows that \(d\) is one of the numbers in the product \((p-1)!\), so \(d\mid(p-1)!\); also, since \(d\mid p\) and \(p\mid((p-1)!+1)\), it follows that \(d\mid((p-1)!+1)\). Therefore, \(d\mid((p-1)!+1)-(p-1)! = 1\) by Theorem 1.3.2, which means \(d=1\).
In other words, if \(d\in\NN\) is a divisor of \(p\), it must be either \(p\) or \(1\), so \(p\) is prime.
Example \(\PageIndex{1}\)
Let’s work through one direction of the proof for a simple case, say of \(p=7\). We start by finding all the inverses of the numbers \(2,\dots,6\) (by brute force, in this small case): \(2\cdot4\equiv1\pmod{7}\) and \(3\cdot5\equiv1\pmod{7}\), meaning that \(2^{-1}\equiv4\) (or\(4^{-1}\equiv2\)) and \(3^{-1}\equiv5\) (or \(5^{-1}\equiv3\)).
Then \[(p-2)! = 5! = 5\cdot4\cdot3\cdot2\cdot1=(5\cdot3)\cdot(4\cdot2)\equiv1\cdot1\equiv1\pmod{7}\] which in turn means that \[(p-1)! = 6! = 6\cdot5!\equiv6\cdot1\equiv6\equiv7-1\equiv-1\pmod{7}\ .\]
Notice that Wilson’s Theorem can be used to build a test for primality: see if a number \(n\) satisfies \((n-1)!\equiv-1\pmod{n}\) and, if so, \(n\) is prime. This is an entirely impractical test, but it is our first example of a simple computational congruence involving an integer which can tell us that that integer is prime.