1985 AIME Problems/Problem 13
Contents
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
times from
.
This leaves us with
Factoring, we get
Because
and
will be coprime, the only thing stopping the GCD from being
is
We want this to equal 0, because that will maximize our GCD.
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
.
Video Solution by OmegaLearn
https://youtu.be/yh70NBCxQzg?t=752
~ pi_is_3.14
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 |