Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(→‎Solution)
m (→‎Solution 4)
(13 intermediate revisions by 11 users not shown)
Line 2: Line 2:
 
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.
 
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>\displaystyle (x,y)</math> denotes the [[greatest common divisor]] of <math>\displaystyle x</math> and <math>\displaystyle y</math>, then we have <math>\displaystyle d_n=(a_n,a_{n+1})=(100+n^2,100+n^2+2n+1)</math>. Now assuming that <math>\displaystyle d_n</math> [[divisor | divides]] <math>\displaystyle 100+n^2</math>, it must divide <math>\displaystyle 2n+1</math> if it is going to divide the entire [[expression]] <math>\displaystyle 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>\displaystyle d_n=(100+n^2,2n+1)</math>. Now note that since <math>\displaystyle 2n+1</math> is [[odd integer | odd]] for [[integer | integral]] <math>\displaystyle n</math>, we can multiply the left integer, <math>\displaystyle 100+n^2</math>, by a multiple of two without affecting the greatest common divisor. Since the <math>\displaystyle n^2</math> term is quite restrictive, let's multiply by <math>\displaystyle 4</math> so that we can get a <math>(\displaystyle 2n+1)^2</math> in there.
+
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>\displaystyle 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>\displaystyle d_n=(-2(2n+1)+401,2n+1)=(401,2n+1)</math>.  Thus <math>\displaystyle d_n</math> must divide <math>\displaystyle 401</math> for every single <math>\displaystyle n</math>.  This means the largest possible value for <math>\displaystyle d_n</math> is <math>\displaystyle 401</math>, and we see that it can be achieved when <math>\displaystyle 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 ==
−
* [[1985 AIME Problems/Problem 14 | Next problem]]
+
{{AIME box|year=1985|num-b=12|num-a=14}}
−
* [[1985 AIME Problems/Problem 12 | Previous problem]]
+
* [[AIME Problems and Solutions]]
−
* [[1985 AIME Problems]]
+
* [[American Invitational Mathematics Examination]]
−
 
+
* [[Mathematics competition resources]]
  
 
[[Category:Intermediate Number Theory Problems]]
 
[[Category:Intermediate Number Theory Problems]]

Revision as of 18:19, 24 October 2020

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$. 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-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}$, an happens when $n \equiv 200 \pmod{401}$.

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1985_AIME_Problems/Problem_13&oldid=135766"