IMO 1988/B3 solution

IMO 1988

Problem B3

Let a and b be positive integers such that ab + 1 divides a² + b². Show that (a² + b²)/(ab + 1) is a perfect square.

Solution

A little experimentation reveals the following solutions: a, a³ giving a²; a³, a⁵ - a giving a²; and the recursive a₁ = 2, b₁ = 8, a_n+1 = b_n, b_n+1 = 4b_n - a_n giving 4. The latter may lead us to: if a² + b² = k(ab + 1), then take A = b, B = kb - a, and then A² + B² = k(AB + 1). Finally, we may notice that this can be used to go down as well as up.

So starting again suppose that a, b, k is a solution in positive integers to a² + b² = k(ab + 1). If a = b, then 2a² = k(a² + 1). So a² must divide k. But that implies that a = b = k = 1. Let us assume we do not have this trivial solution, so we may take a < b. We also show that a³ > b. For (b/a - 1/a)(ab + 1) = b² + b/a - b - 1/a < b² < a² + b². So k > b/a - 1/a. But if a³ < b, then b/a (ab + 1) > b² + a², so k < b/a. But now b > ak and < ak + 1, which is impossible. It follows that k ≥ b/a.

Now define A = ka - b, B = a. Then we can easily verify that A, B, k also satisfies a² + b² = k(ab + 1), and B and k are positive integers. Also a < b implies a² + b² < ab + b² < ab + b² + 1 + b/a = (ab + 1)(1 + b/a), and hence k < 1 + b/a, so ka - b < a. Finally, since k > b/a, ka - b ≥ 0. If ka - b > 0, then we have another smaller solution, in which case we can repeat the process. But we cannot have an infinite sequence of decreasing numbers all greater than zero, so we must eventually get A = ka - b = 0. But now A² + B² = k(AB + 1), so k = B². k was unchanged during the descent, so k is a perfect square.

A slightly neater variation on this is due to Stan Dolan

As above take a² + b² = k(ab + 1), so a, b, and k are all positive integers. Now fixing k take positive integers A, B such that A² + B² = k(AB + 1) (*) and min(A,B) is as small as possible. Assume B ≤ A. Regarding (*) as a quadratic for A, we see that the other root C satisfies A + C = kB, AC = B² - k. The second equation implies that C = B²/A - k/A < B. So C cannot be a positive integer (or the solution C, B would have min(C,B) < min(A,B)). But we have (A+1)(C+1) = A+C + AC + 1 = B² + (B-1)k + 1 > 0, so C > -1. C = kB - A is an integer, so C = 0. Hence k = B².

Note that jumping straight to the minimal without the infinite descent avoids some of the verification needed in the infinite descent.

Solutions are also available in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.

29th IMO 1988