IMO 1994 Problem B1 Determine all ordered pairs (m, n) of positive integers for which (n 3 + 1)/(mn - 1) is an integer.
(1, 2), (1, 3), (2, 1), (2, 2), (2, 5), (3, 1), (3, 5), (5, 2), (5, 3). Solution We start by checking small values of n. n = 1 gives n 3 + 1 = 2, so m = 2 or 3, giving the solutions (2, 1) and (3, 1). Similarly, n = 2 gives n 3 + 1 = 9, so 2m-1 = 1, 3 or 9, giving the solutions (1, 2), (2, 2), (5, 2). Similarly, n = 3 gives n 3 + 1 = 28, so 3m - 1 = 2, 14, giving the solutions (1, 3), (5, 3). So we assume hereafter that n > 3. Let n 3 + 1 = (mn - 1)h. Then we must have h = -1 (mod n). Put h = kn - 1. Then n 3 + 1 = mkn 2 - (m + k)n + 1. Hence n 2 = mkn - (m + k). (*) Hence n divides m + k. If m + k ≥ 3n, then since n > 3 we have at least one of m, k ≥ n + 2. But then (mn - 1)(kn - 1) ≥ (n 2 + 2n - 1)(n - 1) = n 3 + n 2 - 3n + 1 = (n 3 + 1) + n(n - 3) > n 3 + 1. So we must have m + k = n or 2n. Consider first m + k = n. We may take m ≥ k (provided that we remember that if m is a solution, then so is n - m). So (*) gives n = m(n - m) - 1. Clearly m = n - 1 is not a solution. If m = n - 2, then n = 2(n - 2) - 1, so n = 5. This gives the two solutions (m, n) = (2, 5) and (3, 5). If m  n for n > 3. Finally, take m + k = 2n. So (*) gives n + 2 = m(2n - m). Again we may take m ≥ k. m = 2n - 1 is not a solution (we are assuming n > 3). So 2n - m ≥ 2, and hence m(2n - m) ≥ 2m ≥ 2n > n + 2. 35th IMO 1994 © John Scholes jscholes@kalva.demon.co.uk 15 Nov 1998 Last corrected/updated 25 Aug 03