Difference between revisions of "1985 AIME Problems/Problem 13"

Latest revision as of 21:27, 19 December 2024

Problem

The numbers in the sequence $101$ , $104$ , $109$ , $116$ , $\ldots$ are of the form $a_n=100+n^2$ , where $n=1,2,3,\ldots$ For each $n$ , let $d_n$ be the greatest common divisor of $a_n$ and $a_{n+1}$ . Find the maximum value of $d_n$ as $n$ ranges through the positive integers.

Solution 1

If $(x,y)$ denotes the greatest common divisor of $x$ and $y$ , then we have $d_n=(a_n,a_{n+1})=(100+n^2,100+n^2+2n+1)$ . Now assuming that $d_n$ divides $100+n^2$ , it must divide $2n+1$ if it is going to divide the entire expression $100+n^2+2n+1$ .

Thus the equation turns into $d_n=(100+n^2,2n+1)$ . Now note that since $2n+1$ is odd for integral $n$ , we can multiply the left integer, $100+n^2$ , by a power of two without affecting the greatest common divisor. Since the $n^2$ term is quite restrictive, let's multiply by $4$ so that we can get a $(2n+1)^2$ in there.

So $d_n=(4n^2+400,2n+1)=((2n+1)^2-4n+399,2n+1)=(-4n+399,2n+1)$ . It simplified the way we wanted it to! Now using similar techniques we can write $d_n=(-2(2n+1)+401,2n+1)=(401,2n+1)$ . Thus $d_n$ must divide $\boxed{401}$ for every single $n$ . This means the largest possible value for $d_n$ is $401$ , and we see that it can be achieved when $n = 200$ .

Solution 2

We know that $a_n = 100+n^2$ and $a_{n+1} = 100+(n+1)^2 = 100+ n^2+2n+1$ . Since we want to find the GCD of $a_n$ and $a_{n+1}$ , we can use the Euclidean algorithm:

$a_{n+1}-a_n = 2n+1$

Now, the question is to find the GCD of $2n+1$ and $100+n^2$ . We subtract $2n+1$ $100$ times from $100+n^2$ . $(100+n^2)-100(2n+1)$ $=n^2+100-200n-100$ This leaves us with $n^2-200n.$ Factoring, we get $n(n-200)$ Because $n$ and $2n+1$ will be coprime, the only thing stopping the GCD from being $1$ is $n-200.$ We want this to equal 0, because that will maximize our GCD. Solving for $n$ gives us $n=200$ . The last remainder is 0, thus $200*2+1 = \boxed{401}$ is our GCD.

Solution 3

If Solution 2 is not entirely obvious, our answer is the max possible range of $\frac{x(x-200)}{2x+1}$ . Using the Euclidean Algorithm on $x$ and $2x+1$ yields that they are relatively prime. Thus, the only way the GCD will not be 1 is if the $x-200$ term share factors with the $2x+1$ . Using the Euclidean Algorithm, $\gcd(x-200,2x+1)=\gcd(x-200,2x+1-2(x-200))=\gcd(x-200,401)$ . Thus, the max GCD is 401.

Solution 4

We can just plug in Euclidean algorithm, to go from $\gcd(n^2 + 100, n^2 + 2n + 101)$ to $\gcd(n^2 + 100, 2n + 1)$ to $\gcd(n^2 + 100 - 100(2n + 1), 2n + 1)$ to get $\gcd(n^2 - 200n, 2n + 1)$ . Now we know that no matter what, $n$ is relatively prime to $2n + 1$ . Therefore the equation can be simplified to: $\gcd(n - 200, 2n + 1)$ . Subtracting $2n - 400$ from $2n + 1$ results in $\gcd(n - 200,401)$ . The greatest possible value of this is $\boxed{401}$ , and happens when $n \equiv 200 \pmod{401}$ .

Solution 5

As clearly shown in the above solutions, we want to maximize $(100+n^2, 2n+1).$ Then the maximum of the GCD will be achieved with integers $a,b,c$ such that $a(100+n^2) + b(2n+1)=c$ by Bezout's identity. Note for the LHS to be constant, $b$ must be a linear function of $n,$ so $b=px+q.$ However, there cannot be a linear $n$ term in $b(2n+1),$ hence $b=2n-1$ by difference of squares. Changing $b$ to $-2n+1,$ we get $100a+an^2-4n^2+1=c,$ so $a=4,$ and the answer is $c=\boxed{401}.$

~anduran

Video Solution by OmegaLearn

https://youtu.be/yh70NBCxQzg?t=752

~ pi_is_3.14

@@ Line 30: / Line 30: @@
 ==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>, and happens when <math>n \equiv 200 \pmod{401}</math>.
+==Solution 5==
+As clearly shown in the above solutions, we want to maximize <math>(100+n^2, 2n+1).</math> Then the maximum of the GCD will be achieved with integers <math>a,b,c</math> such that <math>a(100+n^2) + b(2n+1)=c</math> by Bezout's identity. Note for the LHS to be constant, <math>b</math> must be a linear function of <math>n,</math> so <math>b=px+q.</math> However, there cannot be a linear <math>n</math> term in <math>b(2n+1),</math> hence <math>b=2n-1</math> by difference of squares. Changing <math>b</math> to <math>-2n+1,</math> we get <math>100a+an^2-4n^2+1=c,</math> so <math>a=4,</math> and the answer is <math>c=\boxed{401}.</math>
+~anduran
 == Video Solution by OmegaLearn ==

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

Page

Toolbox

Search