Difference between revisions of "1985 AIME Problems/Problem 13"

(Solution)
Line 3: Line 3:
  
 
== Solution ==
 
== Solution ==
If <math>(x,y)</math> denotes the [[greatest common divisor]] of <math>x</math> and <math>y</math>, then we have <math>d_n=(a_n,a_{n+1})=(100+n^2,100+n^2+2n+1)</math>. Now assuming that <math>d_n</math> [[divisor | divides]] <math>100+n^2</math>, it must divide <math>2n+1</math> if it is going to divide the entire [[expression]] <math>100+n^2+2n+1</math>.
+
If <math>\displaystyle (x,y)</math> denotes the [[greatest common divisor]] of <math>\displaystyle x</math> and <math>\displaystyle y</math>, then we have <math>\displaystyle d_n=(a_n,a_{n+1})=(100+n^2,100+n^2+2n+1)</math>. Now assuming that <math>\displaystyle d_n</math> [[divisor | divides]] <math>\displaystyle 100+n^2</math>, it must divide <math>\displaystyle 2n+1</math> if it is going to divide the entire [[expression]] <math>\displaystyle 100+n^2+2n+1</math>.
  
Thus the [[equation]] turns into <math>d_n=(100+n^2,2n+1)</math>. Now note that since <math>2n+1</math> is [[odd integer | odd]] for [[integer | integral]] <math>n</math>, we can multiply the left integer, <math>100+n^2</math>, by a multiple of two without affecting the greatest common divisor. Since the <math>n^2</math> term is quite restrictive, let's multipy by <math>4</math> so that we can get a <math>(2n+1)^2</math> in there.
+
Thus the [[equation]] turns into <math>\displaystyle d_n=(100+n^2,2n+1)</math>. Now note that since <math>\displaystyle 2n+1</math> is [[odd integer | odd]] for [[integer | integral]] <math>\displaystyle n</math>, we can multiply the left integer, <math>\displaystyle 100+n^2</math>, by a multiple of two without affecting the greatest common divisor. Since the <math>\displaystyle n^2</math> term is quite restrictive, let's multiply by <math>\displaystyle 4</math> so that we can get a <math>(\displaystyle 2n+1)^2</math> in there.
  
 
So <math>\displaystyle d_n=(4n^2+400,2n+1)=((2n+1)^2-4n+399,2n+1)=(-4n+399,2n+1)</math>. It simplified the way we wanted it to!
 
So <math>\displaystyle d_n=(4n^2+400,2n+1)=((2n+1)^2-4n+399,2n+1)=(-4n+399,2n+1)</math>. It simplified the way we wanted it to!
Now using similar techniques we can write <math>d_n=(-2(2n+1)+401,2n+1)=(401,2n+1)</math>.  Thus <math>d_n</math> must divide <math>401</math> for every single <math>n</math>.  This means the largest possible value for <math>d_n</math> is <math>401</math>, and we see that it can be achieved when <math>n = 200</math>.
+
Now using similar techniques we can write <math>\displaystyle d_n=(-2(2n+1)+401,2n+1)=(401,2n+1)</math>.  Thus <math>\displaystyle d_n</math> must divide <math>\displaystyle 401</math> for every single <math>\displaystyle n</math>.  This means the largest possible value for <math>\displaystyle d_n</math> is <math>\displaystyle 401</math>, and we see that it can be achieved when <math>\displaystyle n = 200</math>.
 
 
 
 
  
 
== See also ==
 
== See also ==

Revision as of 19:55, 28 October 2006

Problem

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.

Solution

If $\displaystyle (x,y)$ denotes the greatest common divisor of $\displaystyle x$ and $\displaystyle y$, then we have $\displaystyle d_n=(a_n,a_{n+1})=(100+n^2,100+n^2+2n+1)$. Now assuming that $\displaystyle d_n$ divides $\displaystyle 100+n^2$, it must divide $\displaystyle 2n+1$ if it is going to divide the entire expression $\displaystyle 100+n^2+2n+1$.

Thus the equation turns into $\displaystyle d_n=(100+n^2,2n+1)$. Now note that since $\displaystyle 2n+1$ is odd for integral $\displaystyle n$, we can multiply the left integer, $\displaystyle 100+n^2$, by a multiple of two without affecting the greatest common divisor. Since the $\displaystyle n^2$ term is quite restrictive, let's multiply by $\displaystyle 4$ so that we can get a $(\displaystyle 2n+1)^2$ in there.

So $\displaystyle 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 $\displaystyle d_n=(-2(2n+1)+401,2n+1)=(401,2n+1)$. Thus $\displaystyle d_n$ must divide $\displaystyle 401$ for every single $\displaystyle n$. This means the largest possible value for $\displaystyle d_n$ is $\displaystyle 401$, and we see that it can be achieved when $\displaystyle n = 200$.

See also