## Section7.5Wilson'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.

### Subsection7.5.1Wilson's Theorem

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?

### Subsection7.5.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.

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{.}$

There are other ways to prove it as well. There is a beautiful approach in terms of counting necklaces or strings of pearls which requires essentially no number theory, but rather basic ideas from combinatorics, the discipline of counting well. 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 4 For more on this story see [C.5.8, page 57]; for more on this type of number see Definition 12.1.6.; imagine discovering this factorization by hand!