1985 AIME Problems/Problem 13
Problem
The numbers in the sequence 
, 
, 
, 
,
are of the form 
, where 
For each 
, let 
be the greatest common divisor of 
and 
. Find the maximum value of as ranges through the positive integers.
Solution
If 
denotes the greatest common divisor of $x$ and $y$, then we have $d_n=(a_n,a_{n+1})=(100+n^2,100+n^2+2n+1)$. Now assuming that $d_n$ divides $100+n^2$, it must divide $2n+1$ if it is going to divide the entire expression $100+n^2+2n+1$.\\
Thus the equation turns into $d_n=(100+n^2,2n+1)$. Now note that since $2n+1$ is odd for integral $n$, we can multiply the left integer, $100+n^2$, by a multiple of two without affecting the greatest common divisor. Since the $n^2$ term is quite restrictive, let's multipy by $4$ so that we can get a $(2n+1)^2$ in there.\\
So $d_n=(4n^2+400,2n+1)=((2n+1)^2-4n+399,2n+1)=(-4n+399,2n+1). It simplified the way we wanted it to!
Now using similar techniques we can write $d_n=(-2(2n+1)+401,2n+1)=(401,2n+1)$. Thus the maximum value of $d_n$ is $401$.
Mark Doss (drunner2007)
