Try this beautiful problem from the American Invitational Mathematics Examination I, AIME I, 1985 based on GCD and Sequence.

GCD and Sequence – AIME I, 1985


The numbers in the sequence 101, 104,109,116,…..are of the form \(a_n=100+n^{2}\) where n=1,2,3,——-, for each n, let \(d_n\) be the greatest common divisor of \(a_n\) and \(a_{n+1}\), find the maximum value of \(d_n\) as n ranges through the positive integers.

  • is 107
  • is 401
  • is 840
  • cannot be determined from the given information

Key Concepts


GCD

Sequence

Integers

Check the Answer


But try the problem first…

Answer: is 401.

Source
Suggested Reading

AIME I, 1985, Question 13

Elementary Number Theory by David Burton

Try with Hints


First hint

\(a_n=100+n^{2}\) \(a_{n+1}=100+(n+1)^{2}=100 + n^{2} +2n +1\) and \(a_{n+1}-a_{n}=2n +1\)

Second Hint

\(d_{n}|(2n+1)\) and \(d_{n}|(100 +n^{2})\) then \(d_{n}|[(100+n^{2})-100(2n+1)]\) then \(d_{n}|(n^{2}-200n)\)

Final Step

here \(n^{2} -200n=0\) then n=200 then \(d_{n}\)=2n+1=2(200)+1=401.

Subscribe to Cheenta at Youtube