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
Check the Answer
Answer: is 85.
AIME I, 1995, Question 8
Elementary Number Theory by David Burton
Try with Hints
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)\)
here number of multiples of y(y+1) from 0 to 100-y \((x \leq 100)\) are
[\(\frac{100-y}{y(y+1)}\)]
\(\Rightarrow \displaystyle\sum_{y=1}^{99}[\frac{100-y}{y(y+1)}\)]=49+16+8+4+3+2+1+1+1=85.
Other useful links
- https://www.cheenta.com/rational-number-and-integer-prmo-2019-question-9/
- https://www.youtube.com/watch?v=lBPFR9xequA