IMO 2026 · Problem 6

Let \(a_1,a_2,a_3,\ldots\) be an infinite sequence of positive integers greater than 1. Suppose that for all positive integers \(n\), the number \(a_{n+1}\) is the smallest positive integer greater than \(a_n\) such that \(\gcd(a_{n+1},a_i)>1\) for every \(i=1,2,\ldots,n\). Prove that there exist positive integers \(T\) and \(L\) such that \[ a_{n+T}=a_n+L \] for every positive integer \(n\).

(Note that \(\gcd(x,y)\) denotes the greatest common divisor of positive integers \(x\) and \(y\).)

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

Solution

We may take \(L\) to be the product of all primes at most \(a_1\).

Put \(A=a_1\) and \(S=\{a_1,a_2,\ldots\}\). The sequence is strictly increasing, hence unbounded. Its defining rule gives the following observation:

If \(x\ge A\) and \(\gcd(x,a_j)>1\) for every term \(a_j<x\), then \(x\in S\).

Indeed, otherwise there would be consecutive terms \(a_k<x<a_{k+1}\), and \(x\) would be an admissible choice smaller than \(a_{k+1}\), a contradiction.

For a positive integer \(x\), define \[ r(x)=\prod_{\substack{p\le A\\ p\text{ prime}\\p\mid x}}p, \] where an empty product is \(1\). Every \(r(a_i)\) is greater than \(1\): this is immediate for \(i=1\), and for \(i>1\) it follows from \(\gcd(a_i,A)>1\).

We claim that \[ \gcd(r(a_i),r(a_j))>1 \qquad\text{for all }i,j. \tag{1} \] Suppose otherwise, and choose the smallest \(n\) for which there is an \(i<n\) with \[ \gcd(r(a_i),r(a_n))=1. \] Since \(\gcd(a_i,a_n)>1\), these two terms have a common prime divisor \(p>A\).

Write \(d=r(a_i)>1\), choose a prime \(q\mid d\), and let \[ b=dq^k, \] where \(k\ge0\) is the smallest integer for which \(dq^k\ge A\). We show that \(b<a_i\). Since \(pd\mid a_i\), if \(k=0\), then \[ b=d<pd\le a_i. \] If \(k\ge1\), minimality of \(k\) gives \(dq^{k-1}<A\), so \[ b<Aq\le Ad<pd\le a_i. \] Thus \(A\le b<a_i\), and the prime divisors of \(b\) are exactly those of \(d\).

By the minimality of \(n\), for every \(j<i\) we have \[ \gcd(r(a_i),r(a_j))>1. \] Consequently, \(\gcd(b,a_j)>1\) for every \(j<i\). In particular, \(b\) shares a prime divisor with every sequence term smaller than \(b\). Our observation therefore shows that \(b\in S\).

However, all prime divisors of \(b\) divide \(r(a_i)\), which is coprime to \(r(a_n)\). As those primes are at most \(A\), none divides \(a_n\). Hence \[ \gcd(b,a_n)=1, \] contradicting the defining condition, since \(b<a_i<a_n\) and both \(b,a_n\) are terms. This proves (1).

Now, for every integer \(x\ge A\), we have \[ x\in S \quad\Longleftrightarrow\quad \gcd(r(x),r(a_j))>1\ \text{for every }j. \tag{2} \] The forward implication follows from (1), including the case \(x=a_j\), since \(r(a_j)>1\). For the reverse implication, the stated condition implies \(\gcd(x,a_j)>1\) for every \(j\), so our observation applies.

Set \[ L=\prod_{\substack{p\le A\\p\text{ prime}}}p. \] For each prime \(p\le A\), we have \(p\mid x\) if and only if \(p\mid x+L\). Therefore \(r(x+L)=r(x)\), and (2) yields \[ x\in S\quad\Longleftrightarrow\quad x+L\in S \qquad(x\ge A). \tag{3} \]

Finally, let \(T\) be the number of terms in the interval \([A,A+L)\). This is a positive integer because \(A\in S\). By (3), translation by \(L\) is an order-preserving bijection from \(S\) onto \(S\cap[A+L,\infty)\). The latter set is obtained by removing precisely the first \(T\) terms of the sequence. Comparing their increasing enumerations gives \[ \boxed{a_{n+T}=a_n+L\qquad\text{for every positive integer }n.} \]

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