Hallar los divisores comunes de $a_{1986}$ y $a_{6891}$

Question

Sea $(a_n)_{n \in \mathbb{N}}$ sea la secuencia de enteros definida recursivamente por $a_0 = 0$ , $a_1 = 1, a_{n+2} = 4a_{n+1}+a_{n}$ para $n \geq 0$ . Hallar los divisores comunes de $a_{1986}$ y $a_{6891}$ .

Creo que es cierto que $\gcd(a_m,a_n) = a_{\gcd(m,n)}$ pero no estoy seguro de cómo demostrarlo. De aquí se deduce la respuesta ya que $\gcd(1986,6891) = 3$ y así $\gcd(a_{1986,6891}) = a_3 = 17$ .

Answer 1

Su $\,a_i\,$ cumplen la misma ley de adición que los números de Fibonacci (con la misma facilidad de demostración que en esta respuesta mediante multiplicación matricial). Por lo tanto, la breve demostración que di en esta respuesta muestra que esta secuencia también es una secuencia de divisibilidad fuerte es decir $\, (a_m,a_n) = a_{\large (m,n)}\,$ que produce inmediatamente el resultado buscado.

Observación $\ $ En respuesta a los comentarios, a continuación se ofrecen más detalles. Como en el primer enlace tenemos

$$ \begin{bmatrix}a_2 &a_1\\ a_1 & a_0\end{bmatrix} = \begin{bmatrix}4 &1\\ 1 & 0\end{bmatrix},\quad \begin{bmatrix} a_{n+2} &\!\!\! a_{n+1}\\ a_{n+1} & \!\!\!a_n\end{bmatrix} = \begin{bmatrix} a_{n+1} &\!\! a_{n}\\ a_{n} & \!\!\!\!a_{n-1}\end{bmatrix} \begin{bmatrix}4 &1\\ 1 & 0\end{bmatrix}$$

Así pues, deducimos por inducción

$$ A_n := \begin{bmatrix} a_{n+1} &\!\! a_{n}\\ a_{n} &\!\!\! a_{n-1}\end{bmatrix} = \begin{bmatrix}4 &1\\ 1 & 0\end{bmatrix}^n\! =\, A_1^n $$

Por lo tanto, deducimos que $\,A_{m+n} = A_1^{m+n} = A_1^m A_1^n = A_m A_n,\ $ es decir

$$ \begin{align} \begin{bmatrix} a_{m+n+1} &\!\! a_{m+n}\\ a_{m+n} &\!\!\!\! a_{m+n-1}\end{bmatrix} &= \begin{bmatrix} a_{m+1} &\!\! a_{m}\\ \!a_{m} & \!\!\!\!a_{m-1}\end{bmatrix} \begin{bmatrix} a_{n+1} &\!\! a_{n}\\ a_{n} & \!\!\!\!a_{n-1}\end{bmatrix}\\[.5em] &= \begin{bmatrix}a_{m+1}a_{n+1}+a_m a_n &\! a_{m+1}a_n+a_m a_{n-1}\\ a_m a_{n+1}+a_{m-1}a_n &\! a_m a_n + a_{m-1} a_{n-1} \end{bmatrix}\\ \end{align} $$

Se obtiene la ley de adición $\ a_{m+n} =\, a_{m+1} a_n +a_m a_{n-1}.\ $ Por ejemplo

$$ \begin{align} \begin{bmatrix}a_8 & a_7\\ a_7 & a_6\end{bmatrix} &= \begin{bmatrix}a_4 & a_3\\ a_3 & a_2\end{bmatrix} \begin{bmatrix}a_5 & a_4\\ a_4 & a_3\end{bmatrix}\\[.4em] &= \begin{bmatrix}72 & \!17\\ 17 &\! 4\end{bmatrix} \begin{bmatrix}305 &\!\!\!\!72\\ 72 &\!\!\!\!\! 17\end{bmatrix} = \begin{bmatrix}23184 &\!\!\! 5473\\ 5473 &\!\!\! 1292\end{bmatrix} \end{align} $$

---

En relación con $\,f_n = \dfrac{x^n-y^n}{x-y},\,$ que satisface $\,f_{n+2} = (x\!+\!y) f_{n+1}-xy\, f_n,\,$ una prueba similar a la anterior demuestra que cumple la ley de adición $\, f_{m+n} = f_{m+1} f_n - xy\, f_m f_{n-1},\ $ es decir

$$ \dfrac{x^{m+n}\!-y^{m+n}}{x-y}\,=\, \dfrac{x^{m+1}\!-y^{m+1}}{x-y}\,\dfrac{x^{n}\!-y^{n}}{x-y} - xy\, \dfrac{x^{m}-y^{m}}{x-y}\,\dfrac{x^{n-1}-y^{n-1}}{x-y}$$

Para ayudar a disipar dudas en los comentarios, aquí%2F(x-y)%20%3D%20-xy(x%5E(m)-y%5E(m))%2F(x-y)(x%5E(n-1)-y%5E(n-1))%2F(x-y)%2B(x%5E(m%2B1)-y%5E(m%2B1))%2F(x-y)(x%5E(n)-y%5E(n))%2F(x-y)%3F) es una verificación Alfa de la ecuación anterior.

Answer 2

Utilizando el polinomio característico (puedes demostrar lo siguiente por inducción) obtenemos que $x^{n+2}=4x^{n+1}+x^n$ lo que implica que $$a_n=\left(2+\sqrt{5}\right)^{n}+\left(2-\sqrt{5}\right)^n$$ por lo que podemos denotarlo con $\alpha^n+\beta^n.$

Primero dejamos que $k$ sea un entero impar no negativo, y obsérvese que $a_n>0$ y que $\frac{a_kn}{a_n}$ es racional. Entonces, por expansión, obtenemos que

$$\frac{a_{kn}}{a_n}=\alpha^{(k-1)n}-\alpha^{(k-2)n}\beta^n+...+\beta^{(k-1)n}$$

lo que significa que $\frac{a_{kn}}{a_n}$ es de la forma $a+b\sqrt{5}$ . Recordando que efectivamente es racional, obtenemos que debe ser un número entero, por lo que $a_n \vert a_{kn}$ .

En el caso de que $k$ es par,

$$\frac{a_{kn}}{a_n}=\frac{\alpha^{kn}+\beta^{kn}}{\alpha^n+\beta^n}=\sum_{i=0}^{k-1}(-1)^i\cdot\alpha^{k-1-i}\cdot\beta^k+2\beta^k$$

que es de nuevo de la forma $a+b\sqrt{5}$ así que aquí tenemos un argumento similar.

Así, obtenemos que si $m \vert n$ entonces $a_m \vert a_n$ .