Discrete Mathematics: Elementary and Beyond

6.5 Fermat’s “Little” Theorem 97

Pierre de Fermat

6.5 Fermat’s “Little” Theorem

Primes are important because we can compose every integer from them; but
it turns out that they also have many other, often surprising, properties.
One of these was discovered by the French mathematician Pierre de Fermat
(1601–1655), now called the “Little” Theorem of Fermat.

Theorem 6.5.1 (Fermat’s Theorem)Ifpis a prime andais an inte-
ger, thenp|ap−a.

Before proving this theorem, we remark that it is often stated in the
following form:Ifpis a prime andais an integer not divisible byp, then

p|ap−^1 − 1. (6.1)

The fact that these two assertions are equivalent (in the sense that if we
know the truth of one, it is easy to prove the other) is left to the reader as
Exercise 6.10.20.
To prove Fermat’s Theorem, we need a lemma, which states another
divisibility property of primes (but is easier to prove):

Lemma 6.5.2Ifpis a prime and 0 <k<p, thenp|

(p

k

)

.

Proof. We know by Theorem 1.8.1 that
(
p
k

)

=

p(p−1)···(p−k+1)

k(k−1)··· 1

.