IMO 1992 SL 1

Origin: AUS

Problem

Prove that for any positive integer m there exist an infinite number of pairs of integers (x, y) such that (i) x and y are relatively prime; (ii) y divides x2 + m; (iii) x divides y2 + m.

Solution

Assume that a pair (x, y) with x < y satisfies the required conditions. We claim that the pair (y, x1) also satisfies the conditions, where x1 = y2+m x (note that x1 > y is a positive integer). This will imply the desired result, since starting from the pair (1, 1) we can obtain arbitrarily many solutions. First, we show that gcd(x1, y) = 1. Suppose to the contrary that gcd(x1, y) = d > 1. Then d | x1 | y2+m ⇒d | m, which implies d | y | x2+m ⇒d | x. But this last is impossible, since gcd(x, y) = 1. Thus it remains to show that x1 | y2 + m and y | x2 1 + m. The former relation is obvious. Since gcd(x, y) = 1, the latter is equivalent to y | (xx1)2 + mx2 = y4 + 2my2 + m2 +mx2, which is true because y | m(m+x2) by the assumption. Hence (y, x1) indeed satisfies all the required conditions. Remark. The original problem asked to prove the existence of a pair (x, y) of positive integers satisfying the given conditions such that x+y \leqm+1. The problem in this formulation is trivial, since the pair x = y = 1 satisfies the conditions. Moreover, this is sometimes the only solution with x + y \leqm + 1. For example, for m = 3 the least nontrivial solution is (x0, y0) = (1, 4).