Theorem 7.5.1. Wilson’s Theorem.
If \(p\) is a prime, then
\begin{equation*}
(p-1)!\equiv -1\text{ (mod }p)\text{,}
\end{equation*}
where the exclamation point here indicates the factorial.
Section 7.5 Wilson’s Theorem and Fermat’s Theorem
Polynomials aren’t the only types of formulas we will see. Here, we introduce two famous theorems about other types of congruences modulo \(p\) (a prime) that will come in very handy in the future.
Subsection 7.5.1 Wilson’s Theorem
Proof.
If \(p=2\) this is very, very easy to check. So assume \(p\neq 2\text{,}\) hence \(p-1\) is even. Now we will think of all the numbers from \(1\) to \(p-1\text{,}\) which will be multiplied to make the factorial. (We will put the example \(p=11\) in bullets to help follow.)
For each \(n\) such that \(1 \lt n \lt p-1\text{,}\) we know that \(n\) has a unique inverse modulo \(p\text{.}\) Pair up all the numbers between (not including) 1 and \(p-1\) in this manner.
- If \(p=11\text{,}\) we pair up \((2,6)\text{,}\) \((3,4)\text{,}\) \((5,9)\text{,}\) and \((7,8)\text{.}\)
Then multiplying out \((p-1)\) factorial, we can reorder the terms using the pairs, and notice much cancellation:
\begin{equation*}
(p-1)!\equiv1\cdot 2\cdot 3\cdots (p-2)\cdot (p-1) \equiv 1 \cdot a\cdot a^{-1}\cdot b\cdot b^{-1}\cdots (p-1)
\end{equation*}
\begin{equation*}
\equiv 1\cdot 1\cdot 1\cdots 1\cdot (p-1)\equiv (p-1)\equiv -1\text{ (mod }p)
\end{equation*}
- For instance, if \(p=11\text{,}\) we pair up\begin{equation*} 10!\equiv 1\cdot 2\cdots 9\cdot 10\equiv 1\cdot (2\cdot 6)\cdot (3\cdot 4)\cdot (5 \cdot 9)\cdot (7 \cdot 8)\cdot 10 \end{equation*}which simplifies to\begin{equation*} 10!\equiv 1\cdot 1\cdot 1\cdot 1\cdot -1\text{ (mod }p) \end{equation*}
Beautiful!
The only loose end is that perhaps some number pairs up with itself, which would mess up that all the numbers pair off nicely. However, in that case, \(a^2\equiv 1\) (mod \(p\)), so by definition \(p\mid (a-1)(a+1)\text{;}\) since \(p\) is a prime greater than two, it must divide one (and only one) of these factors (recall Lemma 6.3.6). In these cases \(a\equiv 1\) or \(a\equiv p-1\text{.}\) But we were not pairing off \(1\) or \(p-1\text{,}\) so this can’t happen.
Exercise 7.7.7 is to show that the conclusion of Wilson’s theorem fails for \(p=10\text{.}\) That is, that \((10-1)!\not\equiv -1\) (mod \(10\)). So does it work or not for other moduli?
Remark 7.5.2.
See Exercise 7.7.11 once you have explored this for a while. For nice combinatorial proofs, see Subsection 7.8.2 or [E.7.27]. If you are really curious, see Wikipedia 3 or Alexander Walker’s blog 4 for a generalization due to Gauss; a somewhat different approach to generalization is taken in [E.7.28].
Subsection 7.5.2 Fermat’s Little Theorem
If one explores a little with powers of numbers modulo \(p\) a prime, one usually notices some pattern of those powers. This is the best-known, and soon we’ll reinterpret it in a powerful way.
Theorem 7.5.3. Fermat’s Little Theorem.
If \(\gcd(a,p)=1\) for \(p\) a prime, then
\begin{equation*}
a^{p-1}\equiv 1\text{ (mod }p)\text{.}
\end{equation*}
Proof.
Sketch of proof (to fill in, see Exercise 7.7.10):
- If \(\gcd(a,p)=1\) and \(p\) is prime, show that \(\{a,2a,3a,\ldots,(p-1)a,pa\}\) is a complete residue system (mod \(p\)).
- That is, show that the set \(\{[a],[2a],[3a],\ldots,[pa]\}\) is the same as the complete set of residues \(\{[0],[1],[2],\ldots,[p-1]\}\text{,}\) though possibly in a different order.
- If \(p\) is prime and \(p\) does not divide \(a\text{,}\) show that\begin{equation*} a\cdot 2a\cdot 3a\cdots (p-1)a\equiv 1\cdot 2\cdot 3\cdots (p-1)\text{ (mod }p)\text{.} \end{equation*}
- Now use Wilson’s Theorem and multiply by \(-1\text{.}\)
Like with most important theorems, there are many other ways to prove it as well; in Section 7.8 we’ll provide a counting-based proof. See [E.7.40] for an analysis of interrelationship with a focus on mechanizing proof. We’ll see a more abstract approach after we introduce the concept of groups in Chapter 8; see Exercise 9.6.2.
So despite the innocuous appearance of this result as a corollary of another theorem, do not be fooled; it is incredibly powerful. As an example, it provides the primary tool in Fermat’s proof that \(2^{37}-1\) is not prime 5 ; imagine discovering this factorization by hand!
en.wikipedia.org/wiki/Wilson%27s_theorem#Gauss%27s_generalizationawwalker.com/2017/02/05/a-generalization-of-wilsons-theorem-due-to-gauss/For more on this story see [E.5.8, page 57]; for more on this type of number see Definition 12.1.6.
