IMO 2002 · Problem 3

Find all pairs of integers \(m>2,n>2\) such that there are infinitely many positive integers \(k\) for which \(k^n+k^2-1\) divides \(k^m+k-1\).

Official text of the problem. Official problem paper (PDF)

Answer

\[ \boxed{(m,n)=(5,3)}. \]

Solution

Suppose \((m,n)\) satisfies the condition. Set \[ P(x)=x^n+x^2-1,\qquad Q(x)=x^m+x-1. \]

First, we show that \(P\) divides \(Q\) as polynomials. Since \(P\) is monic, polynomial division gives \[ Q(x)=A(x)P(x)+R(x), \] where \(A,R\in\mathbb Z[x]\) and either \(R=0\) or \(\deg R<n\). For every positive integer \(k\) satisfying the stated divisibility, \(P(k)\mid R(k)\). For all sufficiently large \(k\), \[ |R(k)|<P(k), \] so such a \(k\) must satisfy \(R(k)=0\). There are infinitely many such \(k\), hence \(R\) is identically zero. Thus \(P\mid Q\).

Because \(P(0)=-1\) and \(P(1)=1\), there is a real number \(\alpha\in(0,1)\) with \(P(\alpha)=0\). Polynomial divisibility also gives \(Q(\alpha)=0\), so \[ \alpha^n=1-\alpha^2,\qquad \alpha^m=1-\alpha. \] As \(1-\alpha<1-\alpha^2\), we have \(m>n\). Put \(d=m-n>0\). The identity \[ Q(x)-x^dP(x) =-(x-1)\bigl(x^{d+1}+x^d-1\bigr) \] shows that \(P\) divides the expression on the right. Since \(P(1)=1\), the polynomials \(P(x)\) and \(x-1\) are relatively prime. Therefore \[ P(x)\mid x^{d+1}+x^d-1. \] Comparing degrees yields \[ n\le d+1=m-n+1, \qquad\text{hence}\qquad m\ge 2n-1. \]

Now \(0<\alpha<1\), so \[ 1-\alpha=\alpha^m \le\alpha^{2n-1} =\frac{(1-\alpha^2)^2}{\alpha}. \] Multiplying by \(\alpha\) and dividing by \(1-\alpha>0\), we obtain \[ \alpha\le(1-\alpha)(1+\alpha)^2 =1+\alpha-\alpha^2-\alpha^3. \] Consequently, \[ \alpha^3\le1-\alpha^2=\alpha^n. \] For \(0<\alpha<1\), this implies \(n\le3\). Since \(n>2\), necessarily \(n=3\).

Then \(\alpha^3=\alpha^n\), so equality holds in the preceding inequalities. In particular, \[ \alpha^m=\alpha^{2n-1}, \] which forces \(m=2n-1=5\).

Finally, \[ x^5+x-1=(x^3+x^2-1)(x^2-x+1). \] Thus for \((m,n)=(5,3)\), the required divisibility holds for every positive integer \(k\), proving sufficiency.

The solution was checked against Evan Chen's published IMO solution notes.