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

(Solution 2)
(Solution 3: Fixed frac)
Line 17: Line 17:
 
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.
 
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==
 
== 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-22,2x+1-2(x-200))=gcd(x-200,401)</math>. Thus, the max gcd is 401.
+
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-22,2x+1-2(x-200))=gcd(x-200,401)</math>. Thus, the max gcd is 401.
  
 
== See also ==
 
== See also ==

Revision as of 15:51, 19 September 2015

Problem

The numbers in the sequence $\displaystyle 101$, $\displaystyle 104$, $\displaystyle 109$, $\displaystyle 116$,$\displaystyle \ldots$ are of the form $\displaystyle a_n=100+n^2$, where $\displaystyle n=1,2,3,\ldots$ For each $\displaystyle n$, let $\displaystyle d_n$ be the greatest common divisor of $\displaystyle a_n$ and $\displaystyle a_{n+1}$. Find the maximum value of $\displaystyle d_n$ as $\displaystyle 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 multiple 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$. This leaves us with $n^2-200n$. We want this to equal 0, so 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-22,2x+1-2(x-200))=gcd(x-200,401)$. Thus, the max gcd is 401.

See also

1985 AIME (ProblemsAnswer KeyResources)
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