Maths Olympiad Prep

Library / /499 of 520

Number theory Difficulty 4.5 AIME Find the answer

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

A number or a short expression. Spacing and $ signs are ignored.

Solution

Since yxy|x, y+1x+1y+1|x+1, then gcd(y,x)=y\text{gcd}\,(y,x)=y (the bars indicate divisibility) and gcd(y+1,x+1)=y+1\text{gcd}\,(y+1,x+1)=y+1. By the Euclidean algorithm, these can be rewritten respectively as gcd(y,xy)=y\text{gcd}\,(y,x-y)=y and gcd(y+1,xy)=y+1\text{gcd}\, (y+1,x-y)=y+1, which implies that both y,y+1xyy,y+1 | x-y. Also, as gcd(y,y+1)=1\text{gcd}\,(y,y+1) = 1, it follows that y(y+1)xyy(y+1)|x-y. [1]
Thus, for a given value of yy, we need the number of multiples of y(y+1)y(y+1) from 00 to 100y100-y (as x100x \le 100). It follows that there are 100yy(y+1)\left\lfloor\frac{100-y}{y(y+1)} \right\rfloor satisfactory positive integers for all integers y100y \le 100. The answer is
y=199100yy(y+1)=49+16+8+4+3+2+1+1+1=085.\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 xy\frac{x}{y} and x+1y+1\frac{x+1}{y+1} are integers, then xy1=xyy\frac{x}{y} - 1 = \frac{x-y}{y} and x+1y+11=xyy+1\frac{x+1}{y+1} - 1 = \frac{x-y}{y+1} must be integers. Since yy and y+1y+1 cannot share common prime factors, it follows that xyy(y+1)\frac{x-y}{y(y+1)} must also be an integer.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.