Cfrgtkky

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 -1pmod p$ and for all $k>n+1$, $x_kequiv 1pmod p$. But I have no idea what to do next.

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=1implies tau^{gcdleft(2^{n+1},kright)}=1,$$

which implies $k|2^{n+1}$ as $k$ is minimal. However, if $k=2^m$ with $mleq 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 $ppm 1$; in particular,

$$pgeq 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.

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 = 2cdot 1cdot 3 = 6$,
$y_3 = 2cdot 6cdot 8= 96$,
$y_4 = 2cdot 96cdot 98 = 18616$,
and
$y_5 = 2cdot 18616cdot 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

===========