AoPSWiki

Want to learn how to tackle those tough AMC/AIME/Olympiad algebra problems? Check out Art of Problem Solving's Intermediate Algebra by Richard Rusczyk and Mathew Crawford. Over 1600 problems!

Personal tools

Search

Toolbox

1985 AIME Problems/Problem 13

From AoPSWiki

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

1985 AIME (Problems • Resources)
Preceded by Problem 12	Followed by Problem 14
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15

Retrieved from "http://www.artofproblemsolving.com/Wiki/index.php/1985_AIME_Problems/Problem_13"

Category: Intermediate Number Theory Problems

Looking for a challenging algebra text? Preparing for MATHCOUNTS or the AMC exams?
Check out Art of Problem Solving's Introduction to Algebra by Richard Rusczyk.

© Copyright 2008 AoPS Incorporated. All Rights Reserved. • Foundation • Privacy • Contact Us