Skip to main content
\( \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

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

Proof

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.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.

Proof

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.1. So despite the innocuous appearance of this result as a corollary of another theorem, do not be fooled. It is incredibly powerful.