The Art and Craft of Problem Solving

7.2 CONGRUENCE 233

So indeed, ak+ 4 will be a multiple of 5. It seems that we can generate composite num­

bers in this sequence if we are careful. Let's try a formal argument by contradiction,

using any given values of a and b.

Assume that the conclusion is false, i.e., that the sequence only contains finitely

many composite numbers. This means that "eventually" the sequence is only primes;

i.e., there exists some M such that an is prime for all n > M. This statement has

"footholds," since prime numbers are often easier to deal with than composite num­

bers, and in particular, we have nice tools we can use with them, like Fermat's little

theorem. Now we need to use our experimentation to produce a contradiction that

works for any values of a and b!

Let n > M and let Xn = p, a prime. What happens later in the sequence? We have

xn+l = ap +b,xn+ 2 = a^2 p+ab+b,xn+ 3 = a^3 p+a^2 b+ab+b, etc. In general, for

any k we have

xn+k = akp+b(ak-^1 +ak-^2 + ... + 1 ) = akp+b (

ak - (^1) )
.

a-I

It would be nice if we could show that Xn+k is not a prime for some k. Since p is

already in the picture, let's use it: if we could show that b (

ak - (^1) )
was a mUltiple of

a-I

p, we'd be done! Now Fermat's little theorem comes to the rescue: As long as a is not

a multiple of p, we have aP-^1 == 1 (mod p), so if we choose k = P -1, then ak - 1 is

a mUltiple of p. However, we are dividing this by a -I. What if p divides a-I? Then

we'd be in trouble. So we won't worry about that for now! Just assume that p doesn't

divide a-1.

Recapping, if we assume that p divides neither a nor a-I, then Xn+p-l will be a

multiple of p, which is a contradiction. How do we ensure that p satisfies these two

conditions? We are given a; it is fixed. Hence there are only finitely many primes p

that either divide a or divide a - I. But by assumption, for n > M, the values of an are

all primes, and there will be infinitely many primes, since the sequence is increasing.

Since we have infinitely many primes to pick from, just pick one that works! _

Problems and Exercises

7.2.5 Let ar :: br (mod m), with r J.. m. Show that we

can "cancel out" the r from both sides of this congru­

ence and conclude that a :: b (mod m). What happens

if (m,r) > I?

7.2.6 Show that if a^2 + b^2 = c^2 • then 3lab.

7.2.7 If.x3 + y^3 = z^3 , show that one of the three must

be a multiple of 7.

7.2.8 Find all prime x such that x^2 + 2 is a prime.

7.2.9 Prove that there are infinitely many positive in­

tegers which cannot be represented as a sum of three

perfect cubes.

7.2. 10 Let N be a number with nine distinct non-zero

digits, such that, for each k from I to 9 inclusive, the

first k digits of N form a number that is divisible by k.

Find N (there is only one answer).

7.2. 11 Let f(n) denote the sum of the digits of n.

(a) For any integer n, prove that eventually the se­

quence

f(n),f(f(n) ),f(f(f(n))), ...

will become constant. This constant value is