Difference between revisions of "1985 AIME Problems/Problem 13"
Adam zheng (talk | contribs) m (→Solution 2) |
Adam zheng (talk | contribs) m (→Solution 4: - typo fix) |
||
Line 29: | Line 29: | ||
==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>, | + | 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>, and happens when <math>n \equiv 200 \pmod{401}</math>. |
− | |||
== Video Solution by OmegaLearn == | == Video Solution by OmegaLearn == |
Latest revision as of 19:04, 6 March 2024
Contents
[hide]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 , and 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 |