Page 302 - Discrete Mathematics and Its Applications

4.4 Solving Congruences 281

Fermat’s Little Theorem

The great French mathematician Pierre de Fermat made many important discoveries in number
theory. One of the most useful of these states that p divides a p−1 − 1 whenever p is prime
and a is an integer not divisible by p. Fermat announced this result in a letter to one of his
correspondents. However, he did not include a proof in the letter, stating that he feared the proof
would be too long.Although Fermat never published a proof of this fact, there is little doubt that
he knew how to prove it, unlike the result known as Fermat’s last theorem. The first published
proof is credited to Leonhard Euler. We now state this theorem in terms of congruences.

THEOREM 3 FERMAT’S LITTLE THEOREM If p is prime and a is an integer not divisible by p,
then

a p−1 ≡ 1 (mod p).

Furthermore, for every integer a we have
p
a ≡ a(mod p).

Remark: Fermat’s little theorem tells us that if a ∈ Z p , then a p−1 = 1in Z p .

The proof of Theorem 3 is outlined in Exercise 19.
Fermat’s little theorem is extremely useful in computing the remainders modulo p of large
powers of integers, as Example 9 illustrates.

EXAMPLE 9 Find 7 222 mod 11.

Solution: We can use Fermat’s little theorem to evaluate 7 222 mod 11 rather than using the fast
modular exponentiation algorithm. By Fermat’s little theorem we know that 7 10 ≡ 1 (mod 11),
10 k
so (7 ) ≡ 1 (mod 11) for every positive integer k. To take advantage of this last congruence,
we divide the exponent 222 by 10, finding that 222 = 22 · 10 + 2. We now see that

10 22 2
7 222 = 7 22·10+2 = (7 ) 7 ≡ (1) 22 · 49 ≡ 5 (mod 11).
It follows that 7 222 mod 11=5. ▲

n
Example 9 illustrated how we can use Fermat’s little theorem to compute a mod p, where
p is prime and p | a. First, we use the division algorithm to find the quotient q and remainder
r when n is divided by p − 1, so that n = q(p − 1) + r where 0 ≤ r< p − 1. It follows that
n
) a ≡ 1 a ≡ a (mod p). Hence, to find a mod p, we only need
a = a q(p−1)+r = (a p−1 q r q r r n
r
to compute a mod p. We will take advantage of this simplification many times in our study of
number theory.

Pseudoprimes

In Section 4.2 we showed that an integer n is prime when it is not divisible by any prime p with
√
p ≤ n. Unfortunately, using this criterion to show that a given integer is prime is inefficient.
√
It requires that we find all primes not exceeding n and that we carry out trial division by each
such prime to see whether it divides n.