Prove that $x_n$ and $n$ are coprimes

The idea is to study the sequence $x_n$, $n\in\mathbb N$, of the question modulo all primes $p$ and to show that $x_n$ cannot be zero mod $p$ if $n\geq p$. This implies that $x_n$ and $n$ are coprime because $x_n$ is coprime to all primes $p\leq n$.

I will work in the ring of integers modulo some prime $p$ and use the notation $\bar z$ for the residue class modulo $p$, that is $\bar z=z+p\mathbb Z$. Recall that $\bar z\pm\bar y=\overline{z+y},\ \bar z\cdot\bar y=\overline{z\cdot y}$.

If $p=2$ then $\overline{x_{n+1}}=\overline{2x_n^2-1}=\overline{-1}=\bar 1$ for all $n=1,\dots$ by the recursion. Hence $x_n$ is odd for $n\geq2$.

If $p=3$ then $\overline{x_2}=\bar 7=\bar 1$ and it follows by induction that $\overline{x_n}=\bar 1$ for all $n\geq2$: This is true for $n=2$. If it is true for some $n$, then we have $\overline{x_{n+1}}=\bar 2(\overline{x_n})^2-\bar1=\bar2\bar1^2-\bar1=\bar1$.

$\newcommand{\Z}{{\mathbb Z}}$ If $p\geq5$, $p=2m+1$, then consider the set $S=\{\overline{2y^2-1}|y\in\{0,1,\dots m\}\}$ of cardinality $\leq m+1$. Consider also the operator $T:\Z/p\Z\to\Z/p\Z$ defined by $T(\bar z)=\bar 2(\bar z)^2-\bar1$. By induction, we have $\overline{x_n}=T^{n-1}(\bar 2)$ for $n=1,2,\dots$. Now for every element $\bar z\in\Z/p\Z$, we have $\bar z\in\{\bar0,\bar1\dots,\bar m\}$ or $-\bar z\in\{\bar0,\bar1\dots,\bar m\}$. Hence every image $T(\bar z)=\bar 2(\bar z)^2-\bar1=\bar 2(-\bar z)^2-\bar1$ of $T$ is an element of $S$.

In particular the $m+2$ terms $\overline{x_2},...,\overline{x_{m+3}}$ are all in $S$ which has at most $m+1$ elements. Hence at least two of them must be equal, say $\overline{x_{j}}=\overline{x_{j+r}}$, where $2\leq j<j+r\leq m+3$. By induction using $\overline{x_{n+1}}=T\overline{x_{n}}$, we conclude that $\overline{x_{k}}=\overline{x_{k+r}}$ for all $k\geq j$: The subsequence $\overline{x_{n}}$, $n\geq j$, is $r$-periodic.

Claim: None of the terms $\overline{x_{j}},\dots,\overline{x_{j+r-1}}$ equals $\bar0$.

Proof: Otherwise, $\overline{x_{j+r}}$ would be an image $T(\bar0)$ or an image $T^s(\bar0)$ for some integer $s\geq2$. By the definition of $T$, we would have $\overline{x_{j+r}}\in\{-\bar1,\bar1\}$ and hence $\overline{x_{j}}=\overline{x_{j+r}}\in\{\bar1,-\bar1\}$. This would lead to $\overline{x_{j+r}}=T^r(\overline{x_{j}})=\bar 1$ and hence to $\overline{x_{j}}=\bar 1$. This in turn would imply that $\overline{x_{j}}=\overline{x_{j+1}}=\cdots=\overline{x_{j+r-1}}=\bar1$ contradicting the assumption that one of the terms $\overline{x_{j}},\dots,\overline{x_{j+r-1}}$ equals $\bar 0$.

The above Claim and the $r$-periodicity of the subsequence $\overline{x_{n}}$, $n\geq j$, imply that $\overline{x_{n}}\neq\bar0$ for all $n\geq j$. Since $j<j+r\leq m+3\leq2m+1=p$, we conclude that $\overline{x_{n}}\neq\bar0$ for $n\geq p$ as we wanted to show.