Problem:
The numbers in the sequence 101,104,109,116,… are of the form an​=100+n2, where n=1,2,3,…. For each n, let dn​ be the greatest common divisor of an​ and an+1​. Find the maximum value of dn​ as n ranges through the positive integers.
Solution:
More generally, we will show that if a is a positive integer and if dn​ is the greatest common divisor of a+n2 and a+(n+1)2, then the maximum value of dn​ is 4a+1, attained when n=2a. It will follow that for the sequence under consideration the answer is 4(100)+1 or 401​.
To prove the above, note that if dn​ divides a+(n+1)2 and a+n2, then it also divides their difference; i.e.,
dn​∣(2n+1)(1)
Now, since 2(a+n2)=n(2n+1)+(2a−n), it follows from (1) that
dn​∣(2a−n)(2)
Hence from (1) and (2), dn​∣((2n+1)+2(2a−n)), or
dn​∣(4a+1)(3)
Consequently, 1≤dn​≤4a+1, so 4a+1 is the largest possible value of dn​. It is attained, since for n=2a we have
a+n2=a+(2a)2=a(4a+1)
and
a+(n+1)2=a+(2a+1)2=(a+1)(4a+1)
The problems on this page are the property of the MAA's American Mathematics Competitions