Section7.3Wilson's Theorem and Fermat's Little Theorem
There are two famous theorems about congruences modulo \(p\) a prime that will come in very handy in the future.
Subsection7.3.1Wilson's Theorem
Theorem7.3.1Wilson's Theorem
If \(p\) is a prime, then \[(p-1)!\equiv -1\text{ mod }(p)\; .\]Proof
- If \(p=2\) this is very, very easy to check.
- So assume \(p\neq 2\), hence \(p-1\) is even.
- For each \(n\) such that \(1 < n < p-1\), we know that \(n\) has a unique inverse modulo \(p\).
- Pair up all the numbers between (not including) 1 and \(p-1\) in this manner.
- For instance, if \(p=11\), pair up \((2,6)\), \((3,4)\), \((5,9)\), and \((7,8)\).
- Then multiplying out \((p-1)\) factorial, we get \[(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)\] \[\equiv 1\cdot 1\cdot 1\cdots 1\cdot (p-1)\equiv (p-1)\equiv -1\text{ mod }(p)\]
- For instance, if \(p=11\), we pair up \[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\] which simplifies to \[10!\equiv 1\cdot 1\cdot 1\cdot 1\cdot -1\text{ mod }(p)\]
- 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)\).
- Since \(p\) is prime, it must divide one or the other of these factors, and in either case \(a\equiv 1\) or \(a\equiv p-1\).
- But we were not pairing off \(1\) or \(p-1\), so this can't happen.
One exercise below is to show that Wilson's theorem fails for \(p=10\). That is, that \((10-1)!\not\equiv -1\) mod (\(10\)). So does it work or not for other moduli?
Subsection7.3.2Fermat'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.
Theorem7.3.2Fermat's Little Theorem
If \(gcd(a,p)=1\) for \(p\) a prime, then \[a^{p-1}\equiv 1\text{ mod }(p)\, .\]Proof
Sketch of proof (to fill in):
- 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 whole set \(\{[0],[1],[2],\ldots,[p-1]\}\), though of course in a different order.
- If \(p\) is prime and \(p\) does not divide \(a\), then \[a\cdot 2a\cdot 3a\cdots (p-1)a\equiv 1\cdot 2\cdot 3\cdots (p-1)\text{ mod }(p)\, .\]
- Now use Wilson's Theorem.
There are other ways to combine the things above to prove it as well. We'll see a more abstract approach when we introduce the concept of groups. But despite the innocuous appearance as a corollary of another theorem, do not be fooled. It is incredibly powerful.
