1995 AIME Problems/Problem 8

From AoPSWiki

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$ (the bars indicate divisibility) and $\text{gcd}\,(y+1,x+1)=y+1$ . By the Euclidean algorithm, these can be rewritten respectively as $\text{gcd}\,(y,x-y)=y$ and $\text{gcd}\, (y+1,x-y)=y+1$ , which implies that both $y,y+1 | x-y$ . Also, as $\text{gcd}\,(y,y+1) = 1$ , it follows that $y(y+1)|x-y$ . ^[1]

Thus, for a given value of $y$ , we need the number of multiples of $y(y+1)$ from $0$ to $100-y$ (as $x \le 100$ ). It follows that there are $\left\lfloor\frac{100-y}{y(y+1)} \right\rfloor$ satisfactory positive integers for all integers $y \le 100$ . The answer is

$\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}.$

^ Another way of stating this is to note that if $\frac{x}{y}$ and $\frac{x+1}{y+1}$ are integers, then $\frac{x}{y} - 1 = \frac{x-y}{y}$ and $\frac{x+1}{y+1} - 1 = \frac{x-y}{y+1}$ must be integers. Since $y$ and $y+1$ cannot share common prime factors, it follows that $\frac{x-y}{y(y+1)}$ must also be an integer.

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

Personal tools

Navigation

Search

Toolbox

1995 AIME Problems/Problem 8

From AoPSWiki

Problem

Solution

See also