The 14th Thailand Mathematical Olympiad

We will prove that such a sequence exists. First we prove the following lemma.

Lemma. Let $q$ be a prime such that $q\equiv 3(\mathrm{mod}4)$. If $n\equiv q(\mathrm{mod}{q}^2)$ then $n$ cannot be written as the sum of two squares.

Proof. Let $q$ be a prime such that $q\equiv 3(\mathrm{mod}4)$, and $n$ be an integer satisfying $n\equiv q(\mathrm{mod}{q}^2)$. Let $k$ be the integer where $q=4k+3$. Assume to the contrary that $n$ can be written as $a^2+b^2$ for some integers $a$ and $b$. Suppose $q\mid a$. Then since $q\mid a^2+b^2$, we get $q\mid b$ and so $q^2\mid a^2+b^2$, contradicting our assumption. Hence $q\nmid a$, and analogously, $q\nmid b$. By Fermat's little theorem we have $$a^{q-1}\equiv b^{q-1}\equiv 1(\mathrm{mod}q).(1)$$ On the other hand we have $a^2\equiv -b^2(\mathrm{mod}q)$, raising this to the $(2k+1)$-th power yields: $$a^{4k+2}\equiv (a^2{)}^{2k+1}\equiv (-b^2{)}^{2k+1}\equiv -b^{4k+2}(\mathrm{mod}q).$$ Since $q-1=4k+2$, this contradicts (1), thus $n$ cannot be written as the sum of two squares. $\square$

To construct the required sequence, let $q_1,q_2,\dots ,q_{2017}$ be primes congruent to $3$ modulo $4$, and consider the following system of congruences: $$\begin{array}{l}n\equiv q_1(\mathrm{mod}{q}_1^2)n+1\equiv q_2(\mathrm{mod}{q}_2^2)⋮n+2016\equiv q_{2017}(\mathrm{mod}{q}_{2017}^2)\end{array}$$ Since all moduli are pairwise relatively prime, by the Chinese Remainder Theorem there exists a solution to this system modulo ${\prod }_{i=1}^{2017}{q}_i^2$. Let $N>0$ be a solution, then the lemma implies that $N,N+1,\dots ,N+2016$ cannot be written as the sum of two squares.