Demuestre que$x_n$ y$n$ son coprimes

Question

Estoy aquí de nuevo con un problema de la Nacional italiana de Matemáticas Olimpiadas de 2007. Dada la siguiente subcession:

Dada la siguiente sucesión

$$\left\{\begin{matrix} x_1=2\\ x_{n+1}=2x_n^2-1 \end{de la matriz}\right.$$

Demostrar que $\gcd(x_n,n)=1 \ \ \ \forall n> 1$

Mi intento

Pensé que tal vez, tener la estrecha fórmula para $x_n$ podría simplificar el problema. Me di cuenta de la recursividad fórmula es análoga a la del coseno de la duplicación de la fórmula:

$$\cos(2x)=2\cos^2(x)-1$$

Así que, básicamente, en cada iteración paso vamos a duplicar el coseno y:

$$x_n=\cos(2^{n-1}\arccos(x_1))=\cos(2^{n-1}\arccos(2))$$

El cálculo de $\arccos(2)$ es equivalente a la siguiente ecuación:

$$\cos(x)=2$$ $$\frac{e^{ix}+e^{-ix}}{2}=2$$

Sustituyendo $e^{ix}=t$:

$$t+\frac 1t=4$$ $$t^2-4t+1=0$$ $$t=2\pm \sqrt{3}$$ $$e^{ix}=2\pm \sqrt{3}$$ $$x=\frac{\ln(2\pm \sqrt{3})}{i}$$

Así:

$$x_n=\cos\left(2^{n-1}\frac{\ln(2\pm \sqrt{3})}{i}\right) $$

Por la fórmula de Euler:

$$x_n=\frac{e^{i2^{n-1}\frac{\ln(2\pm \sqrt{3})}{i}}+e^{-i2^{n-1}\frac{\ln(2\pm \sqrt{3})}{i}}}{2}$$ $$x_n=\frac{(2\pm \sqrt{3})^{2^{n-1}}+(2\pm \sqrt{3})^{-2^{n-1}}}{2}$$

Los signos pueden ser determinados mediante la comprobación de algunos valores. En la final: $$x_n=\frac{(2+\sqrt{3})^{2^{n-1}}+(2+ \sqrt{3})^{-2^{n-1}}}{2}$$ $$x_n=\frac{(\sqrt{3}+2)^{2^{n-1}}+(2-\sqrt{3})^{2^{n-1}}}{2}$$

Así que ahora tenemos la prueba de que si $p|n$ entonces $p \nmid \frac{(\sqrt{3}+2)^{2^{n-1}}+(2-\sqrt{3})^{2^{n-1}}}{2} $ con $p\in \Bbb{P} $. Si $p=2$ la prueba es trivial porque claramente $x_n \equiv 1 \pmod{2} \ \ \ \ \forall n\geq 2$ . Así podemos limitar a estudiar la expresión simplificada:

$$(\sqrt{3}+2)^{2^{n-1}}+(2-\sqrt{3})^{2^{n-1}}$$

Entonces no sé cómo continuar :(

He intentado usando el binomio de Newton obtenemos:

$$(\sqrt{3}+2)^{2^{n-1}}+(2-\sqrt{3})^{2^{n-1}}= \sum_{i=0}^{2^{n-1}} {2^{n-1}\choose i} (\sqrt{3})^i 2^{2^{n-1}-i}+\sum_{i=0}^{2^{n-1}} (-1)^i{2^{n-1}\choose i} (\sqrt{3})^i 2^{2^{n-1}-i}$$

Observe que si $i\equiv 1 \pmod{2}$ los términos simplificada así:

$$\sum_{i=0}^{2^{n-2}} {2^{n-1}\choose 2i} 3^{i} 2^{2^{n-1}-2i+1} $$

Pero entonces no puedo ver el patrón :(

Me puedes ayudar, me gustaría saber cómo solucionar este problema y si es posible cómo continuar mi solución.

Gracias por su tiempo

Answer 1

La idea es estudiar la secuencia de $x_n$, $n\in\mathbb N$, de la pregunta modulo de todos los números primos $p$ , y para mostrar que $x_n$ no puede ser cero mod $p$ si $n\geq p$. Esto implica que $x_n$ e $n$ son coprime porque $x_n$ es coprime a todos los números primos $p\leq n$.

Voy a trabajar en el anillo de los enteros modulo algunos prime $p$ y el uso de la notación $\bar z$ para el residuo de la clase modulo $p$, que es $\bar z=z+p\mathbb Z$. Recordemos que $\bar z\pm\bar y=\overline{z+y},\ \bar z\cdot\bar y=\overline{z\cdot y}$.

Si $p=2$ entonces $\overline{x_{n+1}}=\overline{2x_n^2-1}=\overline{-1}=\bar 1$ para todos los $n=1,\dots$ por la recursividad. Por lo tanto $x_n$ es extraño $n\geq2$.

Si $p=3$ entonces $\overline{x_2}=\bar 7=\bar 1$ y sigue por la inducción que $\overline{x_n}=\bar 1$ para todos los $n\geq2$: Esto es cierto para $n=2$. Si es verdad para algunos $n$, luego tenemos a $\overline{x_{n+1}}=\bar 2(\overline{x_n})^2-\bar1=\bar2\bar1^2-\bar1=\bar1$.

$\newcommand{\Z}{{\mathbb Z}}$ Si $p\geq5$, $p=2m+1$, entonces considere el conjunto a$S=\{\overline{2y^2-1}|y\in\{0,1,\dots m\}\}$ de cardinalidad $\leq m+1$. Tenga en cuenta también el operador $T:\Z/p\Z\to\Z/p\Z$ definido por $T(\bar z)=\bar 2(\bar z)^2-\bar1$. Por inducción, tenemos $\overline{x_n}=T^{n-1}(\bar 2)$ para $n=1,2,\dots$. Ahora, para cada elemento $\bar z\in\Z/p\Z$, tenemos $\bar z\in\{\bar0,\bar1\dots,\bar m\}$ o $-\bar z\in\{\bar0,\bar1\dots,\bar m\}$. Por lo tanto cada imagen $T(\bar z)=\bar 2(\bar z)^2-\bar1=\bar 2(-\bar z)^2-\bar1$ de $T$ es un elemento de $S$.

En particular, el $m+2$ términos de $\overline{x_2},...,\overline{x_{m+3}}$ están todos en $S$ que tiene en la mayoría de las $m+1$elementos. Por lo tanto, al menos dos de ellos deben ser iguales, decir $\overline{x_{j}}=\overline{x_{j+r}}$, donde $2\leq j<j+r\leq m+3$. Por inducción el uso de $\overline{x_{n+1}}=T\overline{x_{n}}$, llegamos a la conclusión de que $\overline{x_{k}}=\overline{x_{k+r}}$ para todos los $k\geq j$: El subsequence $\overline{x_{n}}$, $n\geq j$, es $r$-periódico.

Reclamo: Ninguno de los términos de $\overline{x_{j}},\dots,\overline{x_{j+r-1}}$ es igual a $\bar0$.

Prueba: de lo Contrario, $\overline{x_{j+r}}$ sería una imagen $T(\bar0)$ o una imagen $T^s(\bar0)$ para algunos entero $s\geq2$. Por la definición de $T$, tendríamos $\overline{x_{j+r}}\in\{-\bar1,\bar1\}$ y, por tanto, $\overline{x_{j}}=\overline{x_{j+r}}\in\{\bar1,-\bar1\}$. Esto llevaría a $\overline{x_{j+r}}=T^r(\overline{x_{j}})=\bar 1$ y, por tanto, a $\overline{x_{j}}=\bar 1$. Esto a su vez implicaría que $\overline{x_{j}}=\overline{x_{j+1}}=\cdots=\overline{x_{j+r-1}}=\bar1$ contradiciendo la suposición de que uno de los términos de $\overline{x_{j}},\dots,\overline{x_{j+r-1}}$ es igual a $\bar 0$.

La anterior Afirmación y la $r$-periodicidad de la subsequence $\overline{x_{n}}$, $n\geq j$, implica que $\overline{x_{n}}\neq\bar0$ para todos los $n\geq j$. Desde $j<j+r\leq m+3\leq2m+1=p$, llegamos a la conclusión de que $\overline{x_{n}}\neq\bar0$ para $n\geq p$ como queríamos demostrar.