IMO 2002 SL N6

Origin: ROM | Category: Number Theory

Problem

Find all pairs of positive integers m, n \geq3 for which there exist infinitely many positive integers a such that am + a −1 an + a2 −1 is itself an integer.

Solution

Suppose that (m, n) is such a pair. Assume that division of the polynomial F(x) = xm + x −1 by G(x) = xn + x2 −1 gives the quotient Q(x) and remainder R(x). Since deg R(x) < deg G(x), for x large enough |R(x)| < |G(x)|; however, R(x) is divisible by G(x) for infinitely many integers x, so

it is equal to zero infinitely often. Hence R \equiv0, and thus F(x) is exactly divisible by G(x). The polynomial G(x) has a root \alpha in the interval (0, 1), because G(0) = −1 and G(1) = 1. Then also F(\alpha) = 0, so that \alpham + \alpha = \alphan + \alpha2 = 1. If m \geq2n, then 1 −\alpha = \alpham \leq(\alphan)2 = (1 −\alpha2)2, which is equivalent to \alpha(\alpha−1)(\alpha2 +\alpha−1) \geq0. But this last is not possible, because \alpha2+\alpha−1 > \alpham + \alpha −1 = 0; hence m < 2n. Now we have F(x)/G(x) = xm−n −(xm−n+2 −xm−n −x + 1)/G(x), so H(x) = xm−n+2 −xm−n −x + 1 is also divisible by G(x); but deg H(x) = m −n + 2 \leqn + 1 = deg G(x) + 1, from which we deduce that either H(x) = G(x) or H(x) = (x −a)G(x) for some a \inZ. The former case is impossible. In the latter case we must have m = 2n −1, and thus H(x) = xn+1 −xn−1 −x + 1; on the other hand, putting x = 1 gives a = 1, so H(x) = (x −1)(xn + x2 −1) = xn+1 −xn + x3 −x2 −x + 1. This is possible only if n = 3 and m = 5. Remark. It is an old (though difficult) result that the polynomial xn \pm xk \pm1 is either irreducible or equals x2 \pmx+1 times an irreducible factor.