Difference between revisions of "1985 AIME Problems/Problem 13"
m |
(→Solution 1) |
||
Line 5: | Line 5: | ||
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>(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>. | ||
− | 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 | + | 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 power of two without affecting the greatest common divisor. Since the <math>n^2</math> term is quite restrictive, let's multiply by <math>4</math> so that we can get a <math>(2n+1)^2</math> in there. |
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! | 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 <math>d_n</math> must divide <math>\boxed{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>d_n=(-2(2n+1)+401,2n+1)=(401,2n+1)</math>. Thus <math>d_n</math> must divide <math>\boxed{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>. | ||
+ | |||
== Solution 2 == | == Solution 2 == | ||
We know that <math>a_n = 100+n^2</math> and <math>a_{n+1} = 100+(n+1)^2 = 100+ n^2+2n+1</math>. Since we want to find the GCD of <math>a_n</math> and <math>a_{n+1}</math>, we can use the [[Euclidean algorithm]]: | We know that <math>a_n = 100+n^2</math> and <math>a_{n+1} = 100+(n+1)^2 = 100+ n^2+2n+1</math>. Since we want to find the GCD of <math>a_n</math> and <math>a_{n+1}</math>, we can use the [[Euclidean algorithm]]: |
Revision as of 22:18, 2 July 2018
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 1
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 power of two without affecting the greatest common divisor. Since the
term is quite restrictive, let's multiply 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
must divide
for every single
. This means the largest possible value for
is
, and we see that it can be achieved when
.
Solution 2
We know that and
. Since we want to find the GCD of
and
, we can use the Euclidean algorithm:
Now, the question is to find the GCD of and
. We subtract
100 times from
. This leaves us with
. We want this to equal 0, so solving for
gives us
. The last remainder is 0, thus
is our GCD.
Solution 3
If Solution 2 is not entirely obvious, our answer is the max possible range of . Using the Euclidean Algorithm on
and
yields that they are relatively prime. Thus, the only way the GCD will not be 1 is if the
term share factors with the
. Using the Euclidean Algorithm,
. Thus, the max GCD is 401.
Solution 4
We can just plug in Euclidean algorithm, to go from to
to
to get
. Now we know that no matter what,
is relatively prime to
. Therefore the equation can be simplified to:
. Subtracting
from
results in
. The greatest possible value of this is
, an happens when
.
See also
1985 AIME (Problems • Answer Key • Resources) | ||
Preceded by Problem 12 |
Followed by Problem 14 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |