IMO 1975 · Problem 2

Let \(a_1,a_2,a_3,\cdots\) be an infinite increasing sequence of positive integers. Prove that for every \(p\ge 1\) there are infinitely many \(a_m\) which can be written in the form \[ a_m=xa_p+ya_q \] with \(x,y\) positive integers and \(q>p\).

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

Solution

Fix any \(p\ge 1\). There are only \(a_p\) residue classes modulo \(a_p\), so at least one of them contains infinitely many terms of the sequence; otherwise the sequence would have only finitely many terms.

Choose an index \(q>p\) such that \(a_q\) belongs to this residue class. Infinitely many terms \(a_m\) in the same class have \(m>q\). For each such term, \[ a_m\equiv a_q\pmod{a_p}, \] so \[ x=\frac{a_m-a_q}{a_p} \] is an integer. Because the sequence is increasing and \(m>q\), we have \(a_m>a_q\), hence \(x>0\). Taking \(y=1\), we obtain \[ a_m=xa_p+ya_q, \] with \(x,y\) positive integers and \(q>p\).

This holds for infinitely many \(m\), and \(p\) was arbitrary. \(\square\)

The solution was checked against John Scholes' IMO solution archive (Kalva).