# 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.

• $x_n$ is A002812 at the OEIS. It seems that the least prime factor of $x_n$ is larger than (or equal to) $2^{n+1}-1$. See the comments at A002812 where the question whether for $n>1$, equality holds iff $2^{n+1}-1$ is a Mersenne prime is raised. – René Gy Dec 7 '18 at 20:36
• $x_{n+1} = \sum_k {2^n \choose 2k} 3^k2^{2^n-2k}$ . Not sure that this explicit expression can be useful here. – René Gy Dec 7 '18 at 21:32
• Also $x_n-1=3\cdot2^{2n-1}\cdot \prod_{j=2}^{n-2}x_j^2$ for $n>2$. But it is not clear how this could be used. – René Gy Dec 8 '18 at 12:01
• Would it be possible to show that for $n>1$, any prime divisor $p$ of $x_n$ verify $p \equiv \pm 1 \bmod {2^n}$ ? That would imply a proof of the OP. – René Gy Dec 8 '18 at 12:42

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.

• In order to be able to work in $\mathbb{F}_{p^2}$, we need $\tau \in \mathbb{F}_{p^2}$, right? For this, don't we need that $3$ be quadratic non-residue $\bmod p$? If yes, how is this justified? – René Gy Dec 16 '18 at 11:25
• @RenéGy If $3$ is a quadratic residue $\bmod p$, then $2+\sqrt{3}\in \mathbb{F}_p\subset\mathbb{F}_{p^2}$. – Carl Schildkraut Dec 16 '18 at 17:45

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.

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


===========