1985 AIME Problems/Problem 13
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 multiple 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.
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 |