Determine all ordered pairs (m, n) of positive integers for which (n3 + 1)/(mn - 1) is an integer.
Answer
(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 n3 + 1 = 2, so m = 2 or 3, giving the solutions (2, 1) and (3, 1). Similarly, n = 2 gives n3 + 1 = 9, so 2m-1 = 1, 3 or 9, giving the solutions (1, 2), (2, 2), (5, 2). Similarly, n = 3 gives n3 + 1 = 28, so 3m - 1 = 2, 14, giving the solutions (1, 3), (5, 3). So we assume hereafter that n > 3.
Let n3 + 1 = (mn - 1)h. Then we must have h = -1 (mod n). Put h = kn - 1. Then n3 + 1 = mkn2 - (m + k)n + 1. Hence n2 = 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) ≥ (n2 + 2n - 1)(n - 1) = n3 + n2 - 3n + 1 = (n3 + 1) + n(n - 3) > n3 + 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 - 2 then n - m ≥ 3 and so m(n - m) - 1 ≥ 3m - 1 ≥ 3n/2 - 1 > 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.
© John Scholes
jscholes@kalva.demon.co.uk
15 Nov 1998
Last corrected/updated 25 Aug 03