7.5 MISCELLANEOUS INSTRUCTIVE EXAMPLES 247
(c) You discovered that if (u, v) is a solution to
.xl -2y^2 = I, then so is (3u+4v,2 u+3v). Prove
why this works. It is much easy to see why it
works than to discover it in the first place, so
don't feel bad if you "cheated" in (b).
(d) But now that you understand the lovely tool
of generating new solutions from clever lin
ear combinations of old solutions, you should
try your hand at x^2 - sy^2 = I. In general, this
method will furnish infinitely many solutions to
Pell's equation for any positive non-square d.
7.4.20 Notice that (3+2v2)^2 = 17+ 12V2. Is this a
coincidence? Ponder, conjecture, generalize.
7.4.21 Try to find solutions to x^2 - dy^2 = -I, for a
few positive non-square values of d.
7.4.22 An integer is called square-full if each of its
prime factors occurs to at least the second power.
Prove that there exist infinitely many pairs of consec
utive square-full integers.
7.5 Miscellaneous Instructive Examples
The previous sections barely sampled the richness of number theory. We conclude
the chapter with a few interesting examples. Each example either illustrates a new
problem-solving idea or illuminates an old one. In particular, we present several
"crossover" problems that show the deep interconnections between number theory and
combinatorics.
Can a Polynomial Always Output Primes?
Example 7.5. 1 Consider the polynomial f{x) := x^2 +x+41, which you may remem
ber from Problem 2.2.35 on page 39. Euler investigated this polynomial and discov
ered that f{n) is prime for all integers n from 0 to 39. The casual observer may
suspect after plugging in a few values of n that this polynomial always outputs primes,
but it takes no calculator to see that this cannot be : just let x = 41, and we have
f( 41) = 412 + 41 + 41, obviously a multiple of 41. (And it is easy to see that it will
also be a multiple of 41 if x = 40). So now we are confronted with the "interesting"
case:
Does there exist a polynomial f(x) with integral coefficients and con
stant term equal to ±1, such that f(n) is a prime fo r all n E N?
Investigation: Let us write
f{x) = an:x;'l +an_l:x;'l-l + ... +ao, (9)
where the ai are integers and ao = ± 1. Notice that we cannot use the trick of "plugging
in ao" that worked with x^2 +x+41. Since we are temporarily stumped, we do what
all problem solvers do: experiment! Consider the example f(x) := x^3 + x + 1. Let's
make a table:
I f(n) I ; Iii I^3 i I 6 � 1^13 � I^22 � I^35 i I
This polynomial doesn't output all primes; the first x-value at which it "fails" is
x = 4. But we are just looking for patterns. Notice that f( 4 ) = 3·23, and the next
composite value is f(7) = 33. 13. Notice that 4 = 1 + 3 and 7 = 4 + 3. At this point,
