Prove that $x_n$ and $n$ are coprimes I'm here again with a problem of Italian National Math Olympiads 2007. Given the following subcession:

Given the following succession
$$\left\{\begin{matrix} 
x_1=2\\  x_{n+1}=2x_n^2-1
 \end{matrix}\right.$$
Prove that $\gcd(x_n,n)=1 \ \ \ \forall n> 1$

My attempt
I thought that maybe, having the close formula for $x_n$ could simplify the problem. I noticed the the recursion formula is analogous to the cosine duplication formula:
$$\cos(2x)=2\cos^2(x)-1$$
So basically at each iteration step we are duplicating the cosine and:
$$x_n=\cos(2^{n-1}\arccos(x_1))=\cos(2^{n-1}\arccos(2))$$
Calculating $\arccos(2)$ is equivalent to this equation:
$$\cos(x)=2$$
$$\frac{e^{ix}+e^{-ix}}{2}=2$$
Substituting $e^{ix}=t$:
$$t+\frac 1t=4$$
$$t^2-4t+1=0$$
$$t=2\pm \sqrt{3}$$
$$e^{ix}=2\pm \sqrt{3}$$
$$x=\frac{\ln(2\pm \sqrt{3})}{i}$$
So:
$$x_n=\cos\left(2^{n-1}\frac{\ln(2\pm \sqrt{3})}{i}\right) $$
By Euler's formula:
$$x_n=\frac{e^{i2^{n-1}\frac{\ln(2\pm \sqrt{3})}{i}}+e^{-i2^{n-1}\frac{\ln(2\pm \sqrt{3})}{i}}}{2}$$
$$x_n=\frac{(2\pm \sqrt{3})^{2^{n-1}}+(2\pm \sqrt{3})^{-2^{n-1}}}{2}$$
The signs can be determined by checking some values. In the end:
$$x_n=\frac{(2+\sqrt{3})^{2^{n-1}}+(2+ \sqrt{3})^{-2^{n-1}}}{2}$$
$$x_n=\frac{(\sqrt{3}+2)^{2^{n-1}}+(2-\sqrt{3})^{2^{n-1}}}{2}$$
So now we have to proof that if $p|n$ then $p \nmid \frac{(\sqrt{3}+2)^{2^{n-1}}+(2-\sqrt{3})^{2^{n-1}}}{2} $ with $p\in \Bbb{P} $. If $p=2$ the proof is trivial because clearly $x_n \equiv 1 \pmod{2} \ \ \ \ \forall n\geq 2$ . So we can limitate us to study the simplified expression:
$$(\sqrt{3}+2)^{2^{n-1}}+(2-\sqrt{3})^{2^{n-1}}$$
Then I don't know how to continue :(
I tried using Newton binomial we obtain:
$$(\sqrt{3}+2)^{2^{n-1}}+(2-\sqrt{3})^{2^{n-1}}= \sum_{i=0}^{2^{n-1}} {2^{n-1}\choose i} (\sqrt{3})^i 2^{2^{n-1}-i}+\sum_{i=0}^{2^{n-1}} (-1)^i{2^{n-1}\choose i} (\sqrt{3})^i 2^{2^{n-1}-i}$$
Notice that if $i\equiv 1 \pmod{2}$ the terms get simplified so:
$$\sum_{i=0}^{2^{n-2}} {2^{n-1}\choose 2i} 3^{i} 2^{2^{n-1}-2i+1} $$
But then I can't see the pattern :(
Can you help me, I would like to know how to solve this problem and if possible how to continue my solution.
Thank you for your time
 A: 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.
A: Assume, on contrary that there exists a prime number $p>3$ (the cases $p=2,3$ are trivial) such that $p\mid n$ and $p\mid x_n$.
Let $t_1=2+\sqrt 3\in\Bbb F_p[\sqrt 3]$, $t_n=t_1^{2^{n-1}}$.
Then $x_n\bmod p=(t_n+t_n^{-1})/2$, consequently, $t_1^{2^n}=t_n^2=-1$ in $\Bbb F_p[\sqrt 3]$.
Let $g$ be a generator of the multiplicative group of $\Bbb F_p[\sqrt 3]$ and let $m\in\Bbb Z$ such that $t_1=g^m$.
If $\Bbb F_p[\sqrt 3]=\Bbb F_p$, then $g$ has order $p-1$, hence $g^{m2^n}=g^{(p-1)/2}$ implies $2^nm\equiv\frac{p-1}2\pmod{p-1}$, from which $2^p\mid 2^{n+1}\mid (p-1)$, a contradiction.
If $\Bbb F_p[\sqrt 3]\neq\Bbb F_p$, then $g$ has order $p^2-1$, hence $g^{m2^n}=g^{(p^2-1)/2}$ implies $2^nm\equiv\frac{p^2-1}2\pmod{p^2-1}$, from which $2^p\mid 2^{n+1}\mid (p^2-1)$, a contradiction.
