Difference between revisions of "1985 AIME Problems/Problem 13"
m |
|||
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 | + | 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 == | ||
− | 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>. | + | 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>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. | + | 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 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. |
− | 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! | + | 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! |
− | Now using similar techniques we can write <math>d_n=(-2(2n+1)+401,2n+1)=(401,2n+1)</math>. Thus the | + | 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>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>. |
== See also == | == See also == | ||
+ | * [[1985 AIME Problems/Problem 14 | Next problem]] | ||
+ | * [[1985 AIME Problems/Problem 12 | Previous problem]] | ||
* [[1985 AIME Problems]] | * [[1985 AIME Problems]] | ||
+ | |||
+ | |||
+ | [[Category:Intermediate Number Theory Problems]] |
Revision as of 15:22, 12 October 2006
Problem
The numbers in the sequence , , , , are of the form , where For each , let be the greatest common divisor of and . Find the maximum value of as ranges through the positive integers.
Solution
If denotes the greatest common divisor of and , then we have . Now assuming that divides , it must divide if it is going to divide the entire expression .
Thus the equation turns into . Now note that since is odd for integral , we can multiply the left integer, , by a multiple of two without affecting the greatest common divisor. Since the term is quite restrictive, let's multipy by so that we can get a in there.
So . It simplified the way we wanted it to! Now using similar techniques we can write . Thus must divide for every single . This means the largest possible value for is , and we see that it can be achieved when .