Difference between revisions of "1985 AIME Problems/Problem 13"
Drunner2007 (talk | contribs) (→Problem) |
Drunner2007 (talk | contribs) (→Solution) |
||
| Line 3: | Line 3: | ||
== Solution == | == Solution == | ||
| + | If $(x,y)$ 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) | ||
== See also == | == See also == | ||
* [[1985 AIME Problems]] | * [[1985 AIME Problems]] | ||
Revision as of 19:00, 10 October 2006
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 $(x,y)$ 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)
