Difference between revisions of "1995 AIME Problems/Problem 8"

m
m (outline)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
For how many ordered pairs of positive integers <math>\displaystyle (x,y),</math> with <math>\displaystyle y<x\le 100,</math> are both <math>\displaystyle \frac xy</math> and <math>\displaystyle \frac{x+1}{y+1}</math> integers?
+
For how many ordered pairs of positive integers <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 Algorithm]], these can be rewritten as <math>\text{gcd}\,(y,x-y)=y</math> and <math>\text{gcd}\, (y+1,x-y)=y+1</math>, which implies that <math>y,y+1 | x-y</math>. Also, <math>\text{gcd}\,(y,y+1) = 1</math>, so <math>\frac{x-y}{y(y+1)}</math> must be an integer. Substituting the upper bound of <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. The answer is
 +
<cmath>\sum_{y=1}^{99} \left\lfloor\frac{100-y}{y(y+1)} \right\rfloor = \boxed{085}</cmath>
  
 
== See also ==
 
== See also ==
* [[1995_AIME_Problems/Problem_7|Previous Problem]]
+
{{AIME box|year=1995|num-b=7|num-a=9}}
* [[1995_AIME_Problems/Problem_9|Next Problem]]
 
* [[1995 AIME Problems]]
 

Revision as of 14:26, 15 March 2008

Problem

For how many ordered pairs of positive integers $(x,y),$ with $y<x\le 100,$ are both $\frac xy$ and $\frac{x+1}{y+1}$ integers?

Solution

Since $y|x$, $y+1|x+1$, then $\text{gcd}\,(y,x)=y$ and $\text{gcd}\,(y+1,x+1)=y+1$. By the Euclidean Algorithm, these can be rewritten as $\text{gcd}\,(y,x-y)=y$ and $\text{gcd}\, (y+1,x-y)=y+1$, which implies that $y,y+1 | x-y$. Also, $\text{gcd}\,(y,y+1) = 1$, so $\frac{x-y}{y(y+1)}$ must be an integer. Substituting the upper bound of $x \le 100$, it follows that there are $\left\lfloor\frac{100-y}{y(y+1)} \right\rfloor$ satisfactory positive integers. The answer is \[\sum_{y=1}^{99} \left\lfloor\frac{100-y}{y(y+1)} \right\rfloor = \boxed{085}\]

See also

1995 AIME (ProblemsAnswer KeyResources)
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