Question

The numbers in the sequence $101,$ $104,$ $109,$ $116,$ $\ldots$ are of the form $a_n=100+n^2,$ where $n=1,$ $2,$ $3,$ $\ldots.$ 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.

Answer

Answer: 401

Concepts:greatest common divisor algebraic manipulation prime

Difficulty rating: 2410

Small Hint:

A common divisor of consecutive terms also divides their difference $2n+1$

Big Hint:

Combine $n^2+100$ and $2n+1$ to show that the gcd divides a fixed prime

Solution:

A common divisor $d_n$ divides $a_{n+1}-a_n=2n+1.$ It therefore also divides $\begin{aligned} &4(n^2+100)-(2n+1)^2\\ &\qquad{}+2(2n+1)=401. \end{aligned}$ Since $401$ is prime, $d_n\leq401.$ Equality occurs at $n=200,$ because $2n+1=401$ and $n^2+100=40100=100\cdot401.$ Hence the maximum is $401.$

1985 AIME Problem 13

Answer: 401

Difficulty rating: 2410

Small Hint:

Big Hint:

Solution:

Problem 13 in Other Years