232 CHAPTER 7 NUMBER THEORY
Fermat's Little Theorem
Let's derive a nice consequence of (1). Let p be a prime and let a ..1 p. Since the sets
{a,2a,3a, ... , (p - I)a} and {1 ,2,3, ... ,p - I}
are equal in Zp, the products of their elements are equal in Zp. In other words,
a. 2a. 3a ... (p -I)a == 1. 2. 3 ... (p - I) (mod p),
which is equivalent toaP-I(p - I)! == (p-I)! (modp).
Since p is a prime, (p - I)! ..1 p and consequently, we can "cancel out" the (p - I)!
from both sides,^3 obtaining Fermat's little theorem:aP-^1 == 1 (mod p).
(The word "little" is used to distinguish it from Fermat's Last Theorem.) We can alsoeliminate the hypothesis that a be non-zero^4 modulo p by mUltiplying by a, producing
the equivalent statement thataP==a (modp)
for all a, if p is prime.
The next example shows how one can use Fermat's little theorem to create com
posite numbers.Example 7.2.4 (Germany 1995) Let a and b be positive integers and let the sequence
(xn)n2: 0 be defined by Xo = 1 and Xn+ I = aXn + b for all non-negative integers n. Prove
that for any choice of a and b, the sequence (xn)n2: 0 contains infinitely many composite
numbers.Solution: First, let's experiment. Try a = 5, b = 7 and the sequence is
1,12,67,342, 1717,8592, ....
Clearly, every other term will be even, and that will always hold if a and b are both
odd. If a and b have opposite parity, for example, a = 2, b = 3, our sequence is
1 , 5 ,13, 29,61,125, 253,509, 1021, 2045, ....
Notice that, starting with a 2 = 5, every 4th term appears to be a multiple of 5. Can we
prove this? Let u = ak be a mUltiple of 5. Then the next terms are
ak+I=2u+3,
ak+ 2 = 2(2u + 3) + 3 = 4u+9,
ak+ 3 = 2(4u+9) + 3 = 8u+21 ,
ak+ 4 = 2 (8u + 21) + 3 = (^16) u+45.
(^3) See Problem 7. 2. 5 on page 2 (^33).
(^4) The phrases "non-zero modulo p," "relatively prime to p," "not a mUltiple of p," and "non-zero in Zp" are all
equivalent.