Difference between revisions of "1995 AIME Problems/Problem 8"
m (outline) |
(expand) |
||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
− | For how many ordered pairs of positive | + | For how many ordered pairs of positive [[integer]]s <math>(x,y),</math> with <math>y<x\le 100,</math> are both <math>\frac xy</math> and <math>\frac{x+1}{y+1}</math> integers? |
== Solution == | == Solution == | ||
− | Since <math>y|x</math>, <math>y+1|x+1</math>, then <math>\text{gcd}\,(y,x)=y</math> and <math>\text{gcd}\,(y+1,x+1)=y+1</math>. By the [[Euclidean | + | Since <math>y|x</math>, <math>y+1|x+1</math>, then <math>\text{gcd}\,(y,x)=y</math> (the bars indicate [[divisibility]]) and <math>\text{gcd}\,(y+1,x+1)=y+1</math>. By the [[Euclidean algorithm]], these can be rewritten respectively as <math>\text{gcd}\,(y,x-y)=y</math> and <math>\text{gcd}\, (y+1,x-y)=y+1</math>, which implies that both <math>y,y+1 | x-y</math>. Also, as <math>\text{gcd}\,(y,y+1) = 1</math>, it follows that <math>y(y+1)|x-y</math>. {{ref|1}} |
− | <cmath>\sum_{y=1}^{99} \left\lfloor\frac{100-y}{y(y+1)} \right\rfloor = \boxed{085}</cmath> | + | |
+ | Thus, for a given value of <math>y</math>, we need the number of multiples of <math>y(y+1)</math> from <math>0</math> to <math>100-y</math> (as <math>x \le 100</math>). It follows that there are <math>\left\lfloor\frac{100-y}{y(y+1)} \right\rfloor</math> satisfactory positive integers for all integers <math>y \le 100</math>. The answer is | ||
+ | |||
+ | <cmath>\sum_{y=1}^{99} \left\lfloor\frac{100-y}{y(y+1)} \right\rfloor = 49 + 16 + 8 + 4 + 3 + 2 + 1 + 1 + 1 = \boxed{085}.</cmath> | ||
+ | |||
+ | <br /><br />{{note|1}} Another way of stating this is to note that if <math>\frac{x}{y}</math> and <math>\frac{x+1}{y+1}</math> are integers, then <math>\frac{x}{y} - 1 = \frac{x-y}{y}</math> and <math>\frac{x+1}{y+1} - 1 = \frac{x-y}{y+1}</math> must be integers. Since <math>y</math> and <math>y+1</math> cannot share common prime factors, it follows that <math>\frac{x-y}{y(y+1)}</math> must also be an integer. | ||
== See also == | == See also == | ||
{{AIME box|year=1995|num-b=7|num-a=9}} | {{AIME box|year=1995|num-b=7|num-a=9}} | ||
+ | |||
+ | [[Category:Intermediate Number Theory Problems]] |
Revision as of 18:11, 29 July 2008
Problem
For how many ordered pairs of positive integers with
are both
and
integers?
Solution
Since ,
, then
(the bars indicate divisibility) and
. By the Euclidean algorithm, these can be rewritten respectively as
and
, which implies that both
. Also, as
, it follows that
. [1]
Thus, for a given value of , we need the number of multiples of
from
to
(as
). It follows that there are
satisfactory positive integers for all integers
. The answer is
^ Another way of stating this is to note that if and
are integers, then
and
must be integers. Since
and
cannot share common prime factors, it follows that
must also be an integer.
See also
1995 AIME (Problems • Answer Key • Resources) | ||
Preceded by Problem 7 |
Followed by Problem 9 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |