Demostrar que para todos los $n$ $\gcd(n, x_n)=1$ , dado $x_{n+1}=2(x_n)^2-1$ y $x_1=2$

Question

Tengo una secuencia $x_{n+1} = 2(x_n)^2-1$ los primeros valores son $2, 7, 97, 18817,\dots$ Me he dado cuenta de que si prime $p$ divide $x_n$ entonces $x_{n+1} \equiv -1\pmod p$ y para todos $k>n+1$ , $x_k\equiv 1\pmod p$ . Pero no tengo ni idea de qué hacer a continuación.

Answer 1

Podemos escribir

$$x_n=\frac{1}{2}\left[\tau^{2^{n-1}}+\tau^{-2^{n-1}}\right]$$

donde $\tau=2+\sqrt{3}$ . Ahora, dado un primo impar $p$ , $p|x_n$ si y sólo si

$$\tau^{2^{n-1}}+\tau^{-2^{n-1}}=0$$

(donde trabajamos en $\mathbb{F}_{p^2}$ ). Esto se reduce a

$$\tau^{2^n}= -1.$$

Dejemos que $k$ sea el orden multiplicativo de $\tau$ (el menor número entero positivo para $\tau^k=1$ ). Entonces tenemos

$$\tau^{2^{n+1}}=1,\tau^k=1\implies \tau^{\gcd\left(2^{n+1},k\right)}=1,$$

lo que implica $k|2^{n+1}$ como $k$ es mínima. Sin embargo, si $k=2^m$ con $m\leq n$ entonces

$$-1=\tau^{2^n}=\left(\tau^{2^m}\right)^{2^{n-m}}=1^{2^{n-m}}=1,$$

una contradicción, por lo que $k=2^{n+1}$ . El resultado es que $2^{n+1}$ divide el orden de $\mathbb{F}_{p^2}^{\times}$ que es $p^2-1$ esto implica que $2^n$ divide $p\pm 1$ en particular,

$$p\geq 2^n-1>n$$

(donde la segunda condición se cumple si $n>1$ ). Sólo $p=2$ divide $x_n=1$ y si $p=2$ entonces $p|x_n$ si $n=1$ . Por lo tanto, cualquier primo $p$ que divide $x_n$ es mayor que $n$ , lo que finaliza nuestra prueba.

Answer 2

Voy a hacer mi juego habitual y veré qué pasa.

tl;dr - Nada más que callejones sin salida.

Si $x_{n+1} = 2(x_n)^2-1 $ entonces $x_{n+1} -1 = 2(x_n)^2-2 = 2(x_n^2-1) = 2(x_n-1)(x_n+1) $ .

Por lo tanto, si $y_n =x_n-1$ entonces $y_{n+1} =2y_n(y_n+2) $ .

Desde $x_1 = 2$ , $y_1 = 1$ .

Por lo tanto, $y_2 = 2\cdot 1\cdot 3 = 6$ , $y_3 = 2\cdot 6\cdot 8= 96$ , $y_4 = 2\cdot 96\cdot 98 = 18616$ , y $y_5 = 2\cdot 18616\cdot 18618 = 693185376$ .

Si podemos demostrar que $n | y_n$ , entonces $(n, x_n) = 1$ ya que, si $d|n$ y $d|x_n$ y $d \ge 2$ entonces $d | n | y_n$ así que $d | (x_n-1)$ implica $d | 1$ .

Desgraciadamente, esto no funciona como $y_5$ espectáculos.

Siguiente intento: ver si puedo encontrar $a_n, b_n$ tal que $na_n-x_nb_n = 1$ . Esto demostrará que $(n, x_n) = 1$ .

Si $na_n-x_nb_n = 1$ y $(n+1)a_{n+1}-x_{n+1}b_{n+1} = 1$ entonces

$\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} $

y no sé a dónde ir desde aquí.

Espero que alguien más pueda hacer uso de esto.

Answer 3

Este es el principio del encasillamiento. Entre los primos Impares $p,$ hay soluciones para $2t^2 - 1 \equiv 0 \pmod p$ si y sólo si $p \equiv \pm 1 \pmod 8.$

Para tal primo $p,$ hay algunos $\frac{p+1}{2}$ valores distintos $\pmod p$ de $2x^2 - 1.$ Por lo tanto, tomando $p \geq 17,$ si tomamos, digamos, $p-5$ pasos de su secuencia, sólo hay dos posibilidades: o bien

(I) hay una repetición de algún valor $\pmod p$ que no es uno de $-1,0,1.$ En este caso, la secuencia se repite una y otra vez, para siempre. Por lo tanto, este primo $p$ nunca es un factor de cualquiera de sus $x_n.$ O

(II) al menos uno de los siguientes $-1,0,1$ se produce por el $p-5$ plazo. Tenga en cuenta que $0$ debe ser lo primero de estos tres, ya que $2 \cdot 1^2 - 1 \equiv 2 \cdot (-1)^2 - 1 \equiv 1 \pmod p,$ mientras que la única forma de conseguir $-1$ es $2 \cdot 0^2 - 1 \equiv -1 \pmod p.$

Eso es todo. Si $p$ será nunca un factor de cualquier $x_n,$ es porque, digamos, $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

\=======================

Los buenos primos hasta 30.000 son

2
7
31
97
127
607
8191
12289
22783

\===========