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)
(→‎Problem)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
−
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>\displaystyle 101</math>, <math>\displaystyle 104</math>, <math>\displaystyle 109</math>, <math>\displaystyle 116</math>,<math>\displaystyle \ldots</math> are of the form <math>\displaystyle a_n=100+n^2</math>, where <math>\displaystyle n=1,2,3,\ldots</math> For each <math>\displaystyle n</math>, let <math>\displaystyle d_n</math> be the greatest common divisor of <math>\displaystyle a_n</math> and <math>\displaystyle a_{n+1}</math>. Find the maximum value of <math>\displaystyle d_n</math> as <math>\displaystyle n</math> ranges through the [[positive integer]]s.
  
 
== Solution ==
 
== Solution ==

Revision as of 18:55, 28 October 2006

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

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

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

So $\displaystyle 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 $\displaystyle d_n=(-2(2n+1)+401,2n+1)=(401,2n+1)$. Thus $\displaystyle d_n$ must divide $\displaystyle 401$ for every single $\displaystyle n$. This means the largest possible value for $\displaystyle d_n$ is $\displaystyle 401$, and we see that it can be achieved when $\displaystyle n = 200$.

See also

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