Difference between revisions of "1985 AIME Problems/Problem 13"
(→Solution) |
m |
||
Line 3: | Line 3: | ||
== Solution == | == Solution == | ||
− | If <math>(x,y)</math> denotes the greatest common divisor of | + | 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> 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>. |
− | Thus the equation turns into | + | |
− | So | + | Thus the equation turns into <math>d_n=(100+n^2,2n+1)</math>. Now note that since <math>2n+1</math> is odd for 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. |
− | Now using similar techniques we can write | + | |
+ | So <math>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 the maximum value of <math>d_n</math> is <math>401</math>. | ||
− | |||
== See also == | == See also == | ||
* [[1985 AIME Problems]] | * [[1985 AIME Problems]] |
Revision as of 14:18, 12 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 denotes the greatest common divisor of
and
, then we have
. Now assuming that
divides
, it must divide
if it is going to divide the entire expression
.
Thus the equation turns into . Now note that since
is odd for integral
, we can multiply the left integer,
, by a multiple of two without affecting the greatest common divisor. Since the
term is quite restrictive, let's multipy by
so that we can get a
in there.
So . It simplified the way we wanted it to!
Now using similar techniques we can write
. Thus the maximum value of
is
.