5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ $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. $\endgroup$ – René Gy Dec 7 '18 at 20:36
  • $\begingroup$ $ x_{n+1} = \sum_k {2^n \choose 2k} 3^k2^{2^n-2k}$ . Not sure that this explicit expression can be useful here. $\endgroup$ – René Gy Dec 7 '18 at 21:32
  • $\begingroup$ 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. $\endgroup$ – René Gy Dec 8 '18 at 12:01
  • 1
    $\begingroup$ 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. $\endgroup$ – René Gy Dec 8 '18 at 12:42
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – René Gy Dec 16 '18 at 11:25
  • $\begingroup$ @RenéGy If $3$ is a quadratic residue $\bmod p$, then $2+\sqrt{3}\in \mathbb{F}_p\subset\mathbb{F}_{p^2}$. $\endgroup$ – Carl Schildkraut Dec 16 '18 at 17:45
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

===========

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.