Difference between revisions of "1985 AIME Problems/Problem 13"
(→Solution) |
|||
| Line 3: | Line 3: | ||
== 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> [[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>. | + | 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>. |
| − | 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 | + | 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. |
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>\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 <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>. | + | 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>. |
| − | |||
| − | |||
== See also == | == See also == | ||
Revision as of 18:55, 28 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 multiply 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 
.
