# GCD and Ordered pair | AIME I, 1995 | Question 8

Try this beautiful problem from the American Invitational Mathematics Examination I, AIME I, 1995 based on GCD and Ordered pair.

## GCD and Ordered pair - AIME I, 1995

Find number of ordered pairs of positive integers (x,y) with $y \lt x \leq 100$ are both $\frac{x}{y}$ and $\frac{x+1}{y+1}$ integers.

• is 107
• is 85
• is 840
• cannot be determined from the given information

### Key Concepts

Integers

GCD

Ordered pair

AIME I, 1995, Question 8

Elementary Number Theory by David Burton

## Try with Hints

First hint

here y|x and (y+1)|(x+1) $\Rightarrow gcd(y,x)=y, gcd(y+1,x+1)=y+1$

$\Rightarrow gcd(y,x-y)=y, gcd(y+1,x-y)=y+1$

$\Rightarrow y,y+1|(x-y) and gcd (y,y+1)=1$

$\Rightarrow y(y+1)|(x-y)$

Second Hint

here number of multiples of y(y+1) from 0 to 100-y $(x \leq 100)$ are

[$\frac{100-y}{y(y+1)}$]

Final Step

$\Rightarrow \displaystyle\sum_{y=1}^{99}[\frac{100-y}{y(y+1)}$]=49+16+8+4+3+2+1+1+1=85.

## Subscribe to Cheenta at Youtube

This site uses Akismet to reduce spam. Learn how your comment data is processed.

### Cheenta. Passion for Mathematics

Advanced Mathematical Science. Taught by olympians, researchers and true masters of the subject.