Difference between revisions of "1985 AIME Problems/Problem 13"
Danielguo94 (talk | contribs) (→Solution) |
m (→Solution 4) |
||
(10 intermediate revisions by 8 users not shown) | |||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
− | The numbers in the [[sequence]] <math> | + | The numbers in the [[sequence]] <math>101</math>, <math>104</math>, <math>109</math>, <math>116</math>,<math>\ldots</math> are of the form <math>a_n=100+n^2</math>, where <math>n=1,2,3,\ldots</math> For each <math>n</math>, let <math>d_n</math> be the greatest common divisor of <math>a_n</math> and <math>a_{n+1}</math>. Find the maximum value of <math>d_n</math> as <math>n</math> ranges through the [[positive integer]]s. |
− | == Solution == | + | == Solution 1== |
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 == | ||
+ | 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]]: | ||
+ | |||
+ | <math>a_{n+1}-a_n = 2n+1</math> | ||
+ | |||
+ | |||
+ | Now, the question is to find the GCD of <math>2n+1</math> and <math>100+n^2</math>. We subtract <math>2n+1</math> 100 times from <math>100+n^2</math>. This leaves us with <math>n^2-200n</math>. We want this to equal 0, so solving for <math>n</math> gives us <math>n=200</math>. The last remainder is 0, thus <math>200*2+1 = \boxed{401}</math> is our GCD. | ||
+ | == Solution 3== | ||
+ | If Solution 2 is not entirely obvious, our answer is the max possible range of <math>\frac{x(x-200)}{2x+1}</math>. Using the Euclidean Algorithm on <math>x</math> and <math>2x+1</math> yields that they are relatively prime. Thus, the only way the GCD will not be 1 is if the<math> x-200</math> term share factors with the <math>2x+1</math>. Using the Euclidean Algorithm, <math>\gcd(x-200,2x+1)=\gcd(x-200,2x+1-2(x-200))=\gcd(x-200,401)</math>. Thus, the max GCD is 401. | ||
+ | |||
+ | ==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>. | ||
== See also == | == See also == |
Revision as of 18:19, 24 October 2020
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 |