75th NMO Selection Tests

Let $b_0=1$ and write $b_n=a_n+1$, $n\ge 1$. Clearly, $b_{n+1}=b_n^2+1$, $n\ge 0$. If $n>m\ge 1$, it then follows that $a_n-a_m=b_n-b_m=b_{n-1}^2-b_{m-1}^2=(b_{n-1}-b_{m-1})(b_{n-1}-b_{m-1})$, so

$$a_n-a_m=b_n-b_m=(b_{n-m}-b_0)\prod _{k=0}^{m-1}(b_{n-m+k}+b_k).(\ast )$$

$$a_{2p}-a_p=b_{2p}-b_p=(b_p-b_0)\prod _{k=0}^{p-1}(b_{p+k}+b_k).$$ As parities of the $b_n$ alternate and $p$ is odd, so is each of the factors above. We will prove that the $p$ factors $b_{p+k}+b_k$ are pairwise coprime, whence the conclusion.

Let $0\le k<\ell \le p-1$ and let $d=\gcd (b_{p+k}+b_k,b_{p+\ell }+b_{\ell })$. By the preceding, $d$ is odd. Suppose, if possible, that $d>1$ and let $\equiv$ denote congruence modulo $d$. Then $b_{p+k}\equiv -b_k$, so $b_{p+k+1}=b_{p+k}^2+1\equiv b_k^2+1=b_{k+1}$. Continuing, $b_{p+k+2}=b_{p+k+1}^2+1\equiv b_{k+1}^2+1=b_{k+2}$ and so on and so forth all the way up to get $b_{p+\ell }\equiv b_{\ell }$. On the other hand, $b_{p+\ell }\equiv -b_{\ell }$, so $2b_{\ell }\equiv 0$. Hence $b_{\ell }\equiv 0$, as $d$ is odd, so $b_{\ell +1}=b_{\ell }^2+1\equiv b_0$. Consider any index $j$ in the range $0$ through $p-1$ and use $(\ast )$ to get $$b_{j+\ell +1}-b_j=(b_{\ell +1}-b_0)\prod _{i=0}^{j-1}(b_{\ell +1+i}+b_i)\equiv 0,$$ as $b_{\ell +1}\equiv b_0$, by the preceding paragraph. Hence $b_{j+\ell +1}\equiv b_j$. Similarly, $b_{j+2(\ell +1)}\equiv b_{j+\ell +1}$, then $b_{j+3(\ell +1)}\equiv b_{j+2(\ell +1)}$ and so on and so forth to conclude recursively that the sequence $(b_n)$ is periodic modulo $d$. Let $t$ be the smallest period of the $b_n$ (mod $d$). Recall that $b_{p+k+1}\equiv b_{k+1}$, so $t$ divides $p$. As $p$ is prime, either $t=1$ or $t=p$. The former case is ruled out, as $b_0=1\ne 2=b_1$, so $t=p$. Hence $b_k\equiv b_{p+k}\equiv -b_k$, so $b_k\equiv 0$, as $d$ is odd. Recalling that $b_{\ell }\equiv 0$, it follows that $\ell -k$ is divisible by $p$. This is a contradiction, as $0<\ell -k<p$. Consequently, the $p$ numbers $b_{p+k}+b_k$, $k=0,1,\dots ,p-1$, are pairwise coprime, as stated. This ends the proof and completes the solution.