Select Page

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

But try the problem first…

Source

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.