Find all pairs of integers m > 2, n > 2 such that there are infinitely many positive integers k for which (kn + k2 - 1) divides (km + k - 1).
Solution
Answer: m = 5, n = 3.
Obviously m > n. Take polynomials q(x), r(x) with integer coefficients and with degree r(x) < n such that xm + x - 1 = q(x) (xn + x2 - 1) + r(x). Then xn + x2 - 1 divides r(x) for infinitely many positive integers x. But for sufficiently large x, xn + x2 - 1 > r(x) since r(x) has smaller degree. So r(x) must be zero. So xm + x - 1 factorises as q(x) (xn + x2 - 1), where q(x) = xm-n + am-n-1xm-n-1 + ... + a0.
At this point I use an elegant approach provided by Jean-Pierre Ehrmann
We have (xm + x - 1) = xm-n(xn + x2 - 1) + (1 - x)(xm-n+1 + xm-n - 1), so (xn + x2 - 1) must divide (xm-n+1 + xm-n - 1). So, in particular, m ≥ 2n-1. Also (xn + x2 - 1) must divide (xm-n+1 + xm-n - 1) - xm-2n+1(xn + x2 - 1) = xm-n - xm-2n+3 + xm-2n+1 - 1 (*).
At this point there are several ways to go. The neatest is Bill Dubuque's:
(*) can be written as xm-2n+3(xn-3 - 1) + (xm-(2n-1) - 1) which is < 0 for all x in (0, 1) unless n - 3 = 0 and m - (2n - 1) = 0. So unless n = 3, m = 5, it is has no roots in (0, 1). But xn + x2 - 1 (which divides it) has at least one becaause it is -1 at x = 0 and +1 at x = 1. So we must have n = 3, m = 5. It is easy to check that in this case we have an identity.
Two alternatives follow. Jean-Pierre Ehrmann continued:
If m = 2n-1, (*) is xn-1 - x2. If n = 3, this is 0 and indeed we find m = 5, n = 3 gives an identity. If n > 3, then it is x2(xn-3 - 1). But this has no roots in the interval (0, 1), whereas xn + x2 - 1 has at least one (because it is -1 at x = 0 and +1 at x = 1), so xn + x2 - 1 cannot be a factor.
If m > 2n-1, then (*) has four terms and factorises as (x - 1)(xm-n-1 + xm-n-2 + ... + xm-2n+3 + xm-2n + xm-2n-1 + ... + 1). Again, this has no roots in the interval (0, 1), whereas xn + x2 - 1 has at least one, so xn + x2 - 1 cannot be a factor.
François Lo Jacomo, having got to xn + x2 - 1 divides xm-n+1 + xm-n - 1 and looking at the case m -n + 1 > n, continues:
xn + x2 - 1 has a root r such that 0 < r < 1 (because it is -1 at x = 0 and +1 at x = 1). So rn = 1 - r2. It must also be a root of xm + x - 1, so 1 - r = rm ≤ r2n = (1 - r2)2. Hence (1 - r2)2 - (1 - r) = (1 - r) r (1 - r - r2) ≥ 0, so 1 - r - r2 ≥ 0. Hence rn = 1 - r2 ≥ r, which is impossible.
Many thanks to Carlos Gustavo Moreira for patiently explaining why the brute force approach of calculating the coefficients of q(x), starting at the low end, is full of pitfalls. After several failed attempts, I have given up on it!
© John Scholes
jscholes@kalva.demon.co.uk
29 Aug 2002
Last corrected/updated 29 Aug 2002