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