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
Line 3: Line 3:
  
 
== Solution ==
 
== Solution ==
−
If <math>(x,y)</math> 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$.\\
+
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> 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 $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 multipy 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!
+
Thus the equation turns into <math>d_n=(100+n^2,2n+1)</math>. Now note that since <math>2n+1</math> is odd for integral <math>n</math>, we can multiply the left integer, <math>100+n^2</math>, by a multiple of two without affecting the greatest common divisor. Since the <math>n^2</math> term is quite restrictive, let's multipy by <math>4</math> so that we can get a <math>(2n+1)^2</math> in there.
−
Now using similar techniques we can write $d_n=(-2(2n+1)+401,2n+1)=(401,2n+1)$. Thus the maximum value of $d_n$ is $401$.
+
 
 +
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 the maximum value of <math>d_n</math> is <math>401</math>.
  
  
−
Mark Doss  (drunner2007)
 
  
 
== See also ==
 
== See also ==
 
* [[1985 AIME Problems]]
 
* [[1985 AIME Problems]]

Revision as of 14:18, 12 October 2006

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

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 multipy 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 the maximum value of $d_n$ is $401$.


See also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1985_AIME_Problems/Problem_13&oldid=10269"