Loading [MathJax]/jax/element/mml/optable/BasicLatin.js

6 votos

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

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.

2voto

Carl Schildkraut Puntos 2479

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.

1voto

marty cohen Puntos 33863

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.

1voto

Stephan Aßmus Puntos 16

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

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

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X