The Art and Craft of Problem Solving

248 CHAPTER 7 NUMBER THEORY

we are ready to make a tentative guess that f(7 + 3) will also be a multiple of 3. This

seems almost too good to be true, yet

f(lO) = 103 + 10+ 1 = 1011 = 3·337.

Let's attempt to prove this conjecture, at least for this particular polynomial. Given

that 3 If(a), we'd like to show that 3 lf(a + 3). We have

f(a+3) = (a+3)^3 + ( a+3) + 1 = (a^3 +9a^2 +27a+ 27) + (a+3) + 1.

Don't even think of adding up the like terms-that would be mindless "simplification."

Instead, incorporate the hypothesis that f( a) is a multiple of 3. We then write

f(a + 3) = (a^3 + a + (^1) ) + (9a^2 + 27a+ 27 + 3),

and we are done, since the first expression in parenthesis is f(a), which is a mUltiple

of 3, and all of the coefficients of the second expression are multiples of 3.

Solution: Now we are ready to attempt a more general argument. Assume that

f(x) is the generic polynomial defined in (9). Let f(u) = p for some integer a, where

p is prime. We would like to show that f(u + p) will be a mUltiple of p. We have

f(u+ p) = an(u+ pt +an-I (u+ pt-I + ... +aI (u+ p) +ao·

Before we faint at the complexity of this equation, let's think about it. If we expand

each (u + p)k expression by the binomial theorem, the leading term will be uk. So we

can certainly extract f(u). We need to look at what 's left over; i.e.,

f(u+ p) - f(u) = an ((u+ pt - un) + an-I ((u+ pt-I - un-

I

) + ... +aIP.

Now it suffices to show that

(u+ p)k _uk

is divisible by p for all values of k. This is a simple exercise in congruence notation,

for

u + P == u (mod p)

implies

(U+p)k== Uk (modp).

We aren't completely done, because of the possibility that f(u + p) -f(u) = O.

In this case, f( u + p) = p, which is not composite. If this happens, we keep adding

multiples of p. By the same argument used,f(u + 2p),J(u + 2p), ... will all be multi­

ples of p. Because f(x) is a polynomial, it can only equal p (or -p) for finitely many

values of x [for otherwise, the new polynomial g(x) : = f(x) - p would have infinitely

many zeros, violating the Fundamental Theorem of Algebra]. _

Incidentally, we never used the fact that p was prime. So we obtained a "bonus"

result:

If f(x) is a polynomial with integer coefficients, then for all integers a,

f(a + f(a)) is a multiple of f(a).