Prove that for all $n$ $\gcd(n, x_n)=1$, given $x_{n+1}=2(x_n)^2-1$ and $x_1=2$ I have a sequence $x_{n+1} = 2(x_n)^2-1$; first values are $2, 7, 97, 18817,\dots$
I noticed that if prime $p$ divides $x_n$, then $x_{n+1} \equiv -1\pmod p$ and for all $k>n+1$, $x_k\equiv 1\pmod p$. But I have no idea what to do next.
 A: We can write
$$x_n=\frac{1}{2}\left[\tau^{2^{n-1}}+\tau^{-2^{n-1}}\right]$$
where $\tau=2+\sqrt{3}$. Now, given an odd prime $p$, $p|x_n$ if and only if
$$\tau^{2^{n-1}}+\tau^{-2^{n-1}}=0$$
(where we work in $\mathbb{F}_{p^2}$). This reduces to
$$\tau^{2^n}= -1.$$
Let $k$ be the multiplicative order of $\tau$ (the smallest positive integer so $\tau^k=1$). Then we have
$$\tau^{2^{n+1}}=1,\tau^k=1\implies \tau^{\gcd\left(2^{n+1},k\right)}=1,$$
which implies $k|2^{n+1}$ as $k$ is minimal. However, if $k=2^m$ with $m\leq n$ then
$$-1=\tau^{2^n}=\left(\tau^{2^m}\right)^{2^{n-m}}=1^{2^{n-m}}=1,$$
a contradiction, so $k=2^{n+1}$. A result of this is that $2^{n+1}$ divides the order of $\mathbb{F}_{p^2}^{\times}$, which is $p^2-1$; this implies that $2^n$ divides $p\pm 1$; in particular,
$$p\geq 2^n-1>n$$
(where the second condition holds if $n>1$). Only $p=2$ divides $x_n=1$, and if $p=2$, then $p|x_n$ iff $n=1$. So, any prime $p$ that divides $x_n$ is greater than $n$, which finishes our proof.
A: I'll do my usual playing around
and see what happens.
tl;dr - Nothing but dead ends.
If
$x_{n+1} 
= 2(x_n)^2-1
$
then
$x_{n+1} -1
= 2(x_n)^2-2
= 2(x_n^2-1)
= 2(x_n-1)(x_n+1)
$.
Therefore,
if $y_n =x_n-1$ then
$y_{n+1}
=2y_n(y_n+2)
$.
Since
$x_1 = 2$,
$y_1 = 1$.
Therefore
$y_2 = 2\cdot 1\cdot 3 = 6$,
$y_3 = 2\cdot 6\cdot 8= 96$,
$y_4 = 2\cdot 96\cdot 98 = 18616$,
and
$y_5 = 2\cdot 18616\cdot 18618 = 693185376$.
If we can show that
$n | y_n$,
then
$(n, x_n) = 1$
since,
if $d|n$ and $d|x_n$
and $d \ge 2$
then
$d | n | y_n$
so
$d | (x_n-1)$
implies
$d | 1$.
Unfortunately,
this doesn't work
as $y_5$ shows.
Next try:
see if can find
$a_n, b_n$ such that
$na_n-x_nb_n = 1$.
This will show that
$(n, x_n) = 1$.
If
$na_n-x_nb_n = 1$
and
$(n+1)a_{n+1}-x_{n+1}b_{n+1} = 1$
then
$\begin{array}\\
1
&=(n+1)a_{n+1}-(2x_n^2-1)b_{n+1}\\
&=na_{n+1}+a_{n+1}-2x_n^2b_{n+1}+b_{n+1}\\
&=na_{n}+n(a_{n+1}-a_n)+a_{n+1}-x_n(2x_nb_{n+1})+b_{n+1}\\
&=x_nb_n+1+n(a_{n+1}-a_n)+a_{n+1}-x_n(2x_nb_{n+1})+b_{n+1}\\
&=1+n(a_{n+1}-a_n)+a_{n+1}-x_n(2x_nb_{n+1}+b_{n})+b_{n+1}\\
\text{so}\\
0
&=n(a_{n+1}-a_n)+a_{n+1}-x_n(2x_nb_{n+1}+b_{n})+b_{n+1}\\
\end{array}
$
and I don't know where to go from here.
Hope someone else can make use of these.
A: This is the pigeonhole principle. Among odd primes $p,$ there are solutions to $2t^2 - 1 \equiv 0 \pmod p$ if and only if $p \equiv \pm 1 \pmod 8.$
For such a prime $p,$ there are some $\frac{p+1}{2}$ distinct values $\pmod p$ of $2x^2 - 1.$ Therefore, taking $p \geq 17,$ if we take, say, $p-5$ steps of your sequence, there are just two possibilities: either 
(I) there is a repetition of some value $\pmod p$ that is not one of $-1,0,1.$ In this case, the sequence repeats again and again, forever. Thus, this prime $p$ is never a factor of any of your $x_n.$   OR
(II) at least one of $-1,0,1$ occurs by the $p-5$ deadline. Note that $0$ must come first out of these three, as $2 \cdot 1^2 - 1 \equiv 2 \cdot (-1)^2 - 1 \equiv 1 \pmod p,$ while the only way to get $-1$ is $2 \cdot 0^2 - 1 \equiv -1 \pmod p.$
That's it. If $p$ will ever be a factor of any $x_n,$ it is because, say, $x_{p-2} \equiv 1 \pmod p$
jagy@phobeusjunior:~$ ./mse 
7
       2       0      -1

17
       2       7      12      15       7

23
       2       7       5       3      17       2

31
       2       7       4       0      -1

41
       2       7      15      39       7

47
       2       7       3      17      13       8      33      15      26      35
       5       2

71
       2       7      26       2

73
       2       7      24      56      66      24

79
       2       7      18      15      54      64      54

89
       2       7       8      38      39      15       4      31      52      67
      77      20      87       7

97
       2       7       0      -1


 good primes 
2
7
31
97

=======================
The good primes up to 30,000 are
2
7
31
97
127
607
8191
12289
22783

===========
