mcd(F_m, F_n) = F_mcd(m,n).
La Propiedad del MCD de Fibonacci es un resultado fundamental en la aritmética de la sucesión de Fibonacci que conecta la combinatoria con la teoría de números. Básicamente, dice que la sucesión de Fibonacci es una "sucesión de divisibilidad fuerte". Para ser más exactos, la propiedad dice que el máximo común divisor de dos números de Fibonacci $F_m$ y $F_n$ es simplemente el número de Fibonacci cuyo índice es el máximo común divisor de $m$ y $n$.
Este concepto es clave en las olimpiadas de matemáticas, sobre todo en el AMC 10/12 y el AIME, porque te permite calcular los factores comunes de números grandísimos sin tener que calcular los números como tal. Por ejemplo, encontrar $\gcd(F_{100}, F_{120})$ directamente a mano es imposible, pero con esta propiedad el problema se reduce a encontrar $\gcd(100, 120)$, lo cual es facilísimo.
La intuición detrás de esta propiedad está en la estructura del Algoritmo de Euclides. Las operaciones recursivas que haces para encontrar el MCD de los índices $m$ y $n$ reflejan la reducción recursiva de los valores de Fibonacci. Esta propiedad también implica una regla de divisibilidad más sencilla: si un índice $m$ divide a un índice $n$, entonces el número de Fibonacci $F_m$ divide a $F_n$.
La sucesión de Fibonacci estándar la definimos por $F_0=0, F_1=1, F_2=1$ y $F_n = F_{n-1} + F_{n-2}$.
El Teorema Principal: $$ \gcd(F_m, F_n) = F_{\gcd(m,n)} $$
Propiedad de Divisibilidad: Si $m \mid n$, entonces $F_m \mid F_n$. (Nota: El recíproco es cierto para $m > 2$. Es decir, si $F_m \mid F_n$ y $m > 2$, entonces $m \mid n$.)
Coprimalidad de Términos Adyacentes: $$ \gcd(F_n, F_{n+1}) = 1 $$
Reducción del Paso de Euclides: $$ \gcd(F_m, F_n) = \gcd(F_m, F_{n-m}) \quad \text{para } n > m $$
Aquí tienes la demostración de la propiedad $\gcd(F_m, F_n) = F_{\gcd(m,n)}$ usando el Algoritmo de Euclides y la fórmula de suma de Fibonacci.
Identidad Previa: Usa la fórmula de suma: $$ F_{m+n} = F_{m-1}F_n + F_m F_{n+1} $$ También, recuerda que los números de Fibonacci consecutivos son primos relativos: $\gcd(F_k, F_{k+1}) = 1$.
Paso 1: Lema de Reducción La idea es mostrar que $\gcd(F_m, F_{m+n}) = \gcd(F_m, F_n)$. Si usas la fórmula de suma en el término $F_{m+n}$: $$ \gcd(F_m, F_{m+n}) = \gcd(F_m, F_{m-1}F_n + F_m F_{n+1}) $$ Por las propiedades del MCD, puedes restar múltiplos de $F_m$ del segundo término sin cambiar el MCD. Específicamente, el término $F_m F_{n+1}$ es un múltiplo de $F_m$, así que desaparece módulo $F_m$: $$ \gcd(F_m, F_{m-1}F_n + F_m F_{n+1}) = \gcd(F_m, F_{m-1}F_n) $$ Como $\gcd(F_m, F_{m-1}) = 1$, $F_m$ no comparte factores con $F_{m-1}$. Por lo tanto, cualquier factor común de $F_m$ y el producto $F_{m-1}F_n$ tiene que venir totalmente de $F_n$. Entonces: $$ \gcd(F_m, F_{m-1}F_n) = \gcd(F_m, F_n) $$ Así, queda claro que $\gcd(F_{m+n}, F_m) = \gcd(F_n, F_m)$.
Paso 2: Aplicando el Algoritmo de Euclides El resultado del Paso 1, $\gcd(F_{n+m}, F_m) = \gcd(F_n, F_m)$, muestra que el MCD de los números de Fibonacci se comporta exactamente como el MCD de sus índices cuando haces restas. Si aplicas esto repetidamente (tal como en el algoritmo de Euclides para enteros), obtienes: $$ \gcd(F_n, F_m) = \gcd(F_n, F_{m \pmod n}) $$ Al correr el algoritmo de Euclides en los índices $m$ y $n$, eventualmente reduces los índices a $\gcd(m,n)$ y $0$. $$ \gcd(F_m, F_n) = \gcd(F_{\gcd(m,n)}, F_0) $$
Paso 3: Conclusión Como $F_0 = 0$, y $\gcd(k, 0) = k$ para cualquier entero positivo $k$: $$ \gcd(F_{\gcd(m,n)}, F_0) = \gcd(F_{\gcd(m,n)}, 0) = F_{\gcd(m,n)} $$ Por lo tanto, $\gcd(F_m, F_n) = F_{\gcd(m,n)}$. $\square$