Prove that for all $n$ $\gcd(n, x_n)=1$, given $x_{n+1}=2(x_n)^2-1$ and $x_1=2$

Question

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.

Answer 1

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.

Answer 2

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

===========

Answer 3

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.