IMC 2013 · Day 2 · P9

The answer is yes. We construct an infinite sequence $1 = n_1 < 2 = n_2 < n_3 < \dots$ so that $n_i + n_j$ is square-free for all $i < j$. Suppose that we already have some numbers $n_1 < \dots < n_k$ ($k \ge 2$), which satisfy this condition and find a suitable number $n_{k+1}$ to be the next element of the sequence.

We will choose $n_{k+1}$ of the form $n_{k+1} = 1 + Mx$, with $M = ((n_1 + \dots + n_k + 2k)!)^2$ and some positive integer $x$. For $i = 1, 2, \dots, k$ we have $n_i + n_{k+1} = 1 + Mx + n_i = (1 + n_i) m_i$, where $m_i$ and $M$ are co-prime, so any perfect square dividing $1 + Mx + n_i$ is co-prime with $M$.

In order to find a suitable $x$, take a large $N$ and consider the values $x = 1, 2, \dots, N$. If a value $1 \le x \le N$ is not suitable, this means that there is an index $1 \le i \le k$ and some prime $p$ such that $p^2 \mid 1 + Mx + n_i$. For $p \le 2k$ this is impossible because $p \mid M$. Moreover, we also have $p^2 \le 1 + Mx + n_i < M(N+1)$, so $2k < p < \sqrt{M(N+1)}$.

For any fixed $i$ and $p$, the values for $x$ for which $p^2 \mid 1 + Mx + n_i$ form an arithmetic progression with difference $p^2$. Therefore, there are at most $\frac{N}{p^2} + 1$ such values. In total, the number of unsuitable values $x$ is less than $$\begin{align*} \sum_{i=1}^{k} \sum_{2k < p < \sqrt{M(N+1)}} \left( \frac{N}{p^2} + 1 \right) &< k \left( N \cdot \sum_{p > 2k} \frac{1}{p^2} + \sum_{p < \sqrt{M(N+1)}} 1 \right) < \\ &< k N \sum_{p > 2k} \frac{1}{(p-1) p} + k \sqrt{M(N+1)} < \frac{N}{2} + k \sqrt{M(N+1)}. \end{align*}$$ If $N$ is big enough then this is less than $N$, and there exist

a suitable choice for $x$.