Maths Olympiad Prep

Library / /7 of 18

Number theory Difficulty 5.5 AIME, harder Prove it Austria

Determine all pairs (x,y)(x, y) of positive integers such that for d=gcd(x,y)d = \gcd(x, y) the equation
xyd=x+y+d2 xyd = x + y + d^2
holds.

Solution

Answer. There are three such pairs, (x,y)=(2,2)(x, y) = (2, 2), (x,y)=(2,3)(x, y) = (2, 3) and (x,y)=(3,2)(x, y) = (3, 2).

For x=1x = 1, we get d=1d = 1 and the given equation becomes the contradiction y=y+2y = y + 2. This works analogously for y=1y = 1.
Therefore, we can assume x2x \ge 2 and y2y \ge 2.

We start with the case d=1d = 1 which gives the equation
xy=x+y+1    (x1)(y1)=2. xy = x + y + 1 \iff (x - 1)(y - 1) = 2.
The possible factorizations 2=122 = 1 \cdot 2 and 2=212 = 2 \cdot 1 give the pairs (x,y)=(2,3)(x, y) = (2, 3) and (x,y)=(3,2)(x, y) = (3, 2), respectively, because gcd(x,y)=1\gcd(x, y) = 1 is satisfied.

Now, we treat the case d2d \ge 2. The given equation is equivalent to
1xd+1yd+dxy=1. \frac{1}{xd} + \frac{1}{yd} + \frac{d}{xy} = 1.
Because of xd4xd \ge 4 and yd4yd \ge 4, we get
114+14+dxy    xy2d. 1 \le \frac{1}{4} + \frac{1}{4} + \frac{d}{xy} \iff xy \le 2d.
Together with xyd2xy \ge d^2, we obtain d=2d = 2, x=y=2x = y = 2 which gives indeed the third pair (x,y)=(2,2)(x, y) = (2, 2) with gcd(2,2)=2\gcd(2, 2) = 2.

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.