- 1 PRIMES AND DIVISIBILITY 227
Since the right-hand side is a multiple of v, and v shares no factor with un, we must
conclude that v = ±1; i.e., u/v is an integer. _
Now that we understand GCD well, let us finish up an old problem that we startedin Example 2.2.2 on page 28.
Example 7.1. 8 (AIME 19 85) The numbers in the sequence
101 , 104, 10 9,1 16, ...are of the form an = 100 + n^2 , where n = 1,2,3, .... For each n, let dn be the greatest
common divisor of an and an+ I. Find the maximum value of dn as n ranges through
the positive integers.
Solution: Recall that we considered the sequence an := u + n^2 , where u was fixed,
and after some experimentation discovered that a 2 u, a 2 u+ 1 seemed fruitful, since a 2 u =
u( 4u + 1) and a 2 u+ 1 = (u + 1) (4u + 1). This of course means that 4u + 1 is a common
factor of a 2 u and a 2 u+l. In fact, since consecutive numbers are relatively prime (7. 1. 3 ),
we have
( a 2 u, a 2 u+.) = 4u + (^1).
It remains to show that this is the largest possible GCD. Make the abbreviations
a:=an=u+n^2 , b:=an+I=U+(n +l)^2 , g:=(a,b).
Now we shall explore profitable linear combinations of a and b, with the hope that we
will get 4u + 1. We have
b-a = 2n + 1.
This is nice and simple, but how do we get rid of the n? Since a = u + n^2 , let's build
the n^2 term. We have
and thus
2a -n(b-a) =2u-n.
Doubling this and adding it back to b - a yields
2 (2a - n (b- a)) + (b-a) = 2(2u - n) + (2n+ 1) = 4u + (^1).
In other words, we have produced a linear combination of a and b [specifically, the
combination (3 + 2n)a + (1 - 2n)b] that is equal to 4 u + 1. Thus gl (4u + 1), no matter
what n equals. Since this value has been achieved, we conclude that indeed 4 u + 1 is
the largest possible GCD of consecutive terms. _
Notice that we did not need clairvoyance to construct the linear combination in
one fell swoop. All it took was some patient "massage" moving toward the goal of