Difference between revisions of "1985 AIME Problems/Problem 13"
m (→Solution 4) |
Pi is 3.14 (talk | contribs) (→Solution 4) |
||
Line 22: | Line 22: | ||
==Solution 4== | ==Solution 4== | ||
We can just plug in Euclidean algorithm, to go from <math>\gcd(n^2 + 100, n^2 + 2n + 101)</math> to <math>\gcd(n^2 + 100, 2n + 1)</math> to <math>\gcd(n^2 + 100 - 100(2n + 1), 2n + 1)</math> to get <math>\gcd(n^2 - 200n, 2n + 1)</math>. Now we know that no matter what, <math>n</math> is relatively prime to <math>2n + 1</math>. Therefore the equation can be simplified to: <math>\gcd(n - 200, 2n + 1)</math>. Subtracting <math>2n - 400</math> from <math>2n + 1</math> results in <math>\gcd(n - 200,401)</math>. The greatest possible value of this is <math>\boxed{401}</math>, an happens when <math>n \equiv 200 \pmod{401}</math>. | We can just plug in Euclidean algorithm, to go from <math>\gcd(n^2 + 100, n^2 + 2n + 101)</math> to <math>\gcd(n^2 + 100, 2n + 1)</math> to <math>\gcd(n^2 + 100 - 100(2n + 1), 2n + 1)</math> to get <math>\gcd(n^2 - 200n, 2n + 1)</math>. Now we know that no matter what, <math>n</math> is relatively prime to <math>2n + 1</math>. Therefore the equation can be simplified to: <math>\gcd(n - 200, 2n + 1)</math>. Subtracting <math>2n - 400</math> from <math>2n + 1</math> results in <math>\gcd(n - 200,401)</math>. The greatest possible value of this is <math>\boxed{401}</math>, an happens when <math>n \equiv 200 \pmod{401}</math>. | ||
+ | |||
+ | |||
+ | == Video Solution by OmegaLearn == | ||
+ | https://youtu.be/yh70NBCxQzg?t=752 | ||
+ | |||
+ | ~ pi_is_3.14 | ||
== See also == | == See also == |
Revision as of 08:36, 4 November 2022
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
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
.
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 |