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



Ordered pair

Check the Answer

But try the problem first…

Answer: is 85.

Suggested Reading

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


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