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). \quad (*)$$

$$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 $(*)$ 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.