Misterios aritméticos de la sucesión de Fibonacci

Piste verte Le 20 mars 2014  - Ecrit par  Shalom Eliahou
Le 4 mars 2019  - Traduit par  Jimena Royo-Letelier, Julio E. De Villegas
Article original : Mystères arithmétiques de la suite de Fibonacci Voir les commentaires
Lire l'article en  

¿Pensaba usted que lo sabía todo acerca de nuestra vieja amiga la secuencia de Fibonacci ? ¡Desengáñese !

La secuencia de Fibonacci

La secuencia de Fibonacci —bien conocida por aquellos que la conocen bien, como diría un famoso colega de Nueva York— comienza así :

\[ 0,\, 1,\, 1,\, 2,\, 3,\, 5,\, 8,\, 13,\, 21,\, 34,\, 55,\, 89,\, 144,\, 233,\, ... \]

Sus dos primeros términos son $0$ y $1$, y luego cada término sucesivo es la suma de los dos términos anteriores. Así, $0+1=1$, $1+1 = 2$, $1 + 2 = 3$, $2 + 3 = 5$, $3 + 5 = 8$, etc.

Como es costumbre, vamos a denotar por $F_n$ el $n$-ésimo término de esta secuencia, comenzando por $n = 0$. Así, la secuencia de Fibonacci $F_0$, $F_1$, $F_2$, $\dots$ puede ser completamente definida por las fórmulas siguientes :
\[ \begin{eqnarray*} F_0 & = & 0 \\ F_1 & = & 1 \\ F_n & = & F_{n-2}+F_{n-1} \,\,\, \text{ para } n \ge 2. \end{eqnarray*} \]

Su inventor es Leonardo de Pisa (1175 $-$ hacia 1250), también conocido bajo el nombre de Leonardo Fibonacci, quien trajo desde Oriente la notación numérica indoárabe, escribió y tradujo influyentes libros de matemáticas.

Introducido como un problema recreativo en su famosa obra Liber Abaci, la secuencia de Fibonacci puede ser considerada como el primer modelo matemático en dinámica de poblaciones. En efecto, ella describe el crecimiento de una población de conejos bajo hipótesis muy simplificadas, a saber : cada pareja de conejos, desde su tercer mes de existencia, engendra cada mes una nueva pareja de conejos, y así indefinidamente.

Partamos entonces con una pareja de conejos el primer mes. El segundo mes tenemos solo la misma pareja, pero en el tercer mes ya hay $2$ parejas, después $3$ parejas el cuarto mes, $5$ parejas el quinto mes, etc. El crecimiento de esta población está bien descrito por la secuencia de Fibonacci.

Los números primos

Recordemos que un número primo es un número natural que tiene exactamente dos divisores, a saber, 1 y él mismo —lo que excluye al 1 como número primo—. La secuencia de números primos comienza así :

\[ 2,\, 3,\, 5,\, 7,\, 11,\, 13,\, 17,\, 19,\, 23,\, 29,\, 31,\, \dots . \]

Estos números son los ladrillos fundamentales a partir de los cuales se puede obtener, por multiplicación, todos los otros números naturales. Por ejemplo, $24$ se obtiene multiplicando los números primos $2$ (repetido tres veces) y $3$ :
\[ 24 \,=\, 2 \times 2 \times 2 \times 3. \]

Una primera pregunta

Uno de los primeros misterios aritméticos de la secuencia de Fibonacci es el siguiente :

Pregunta. ¿Contiene la secuencia de Fibonacci una infinidad de números primos ?

¡Se ignora ! Solamente se sabe que si $F_n$ es primo, entonces $n$ es a su vez primo. Pero el recíproco no es cierto : por ejemplo $n=19$ es primo, mientras que $F_{19}$ no lo es, ya que
\[F_{19} \, = \, 4\:181\, =\, 37 \times 113.\]

Más generalmente, nos gustaría mucho entender las propiedades aritméticas de los números de Fibonacci $F_n$. Por ejemplo, si uno tiene un número primo $p$, ¿cuáles son todos los $F_n$ que son divisibles por $p$ ? ¿Hay una infinidad ? Y entre ellos, ¿cuáles son divisibles por $p^2$ ? La conjetura que nos tendrá ocupados aquí tiene que ver precisamente con estas preguntas.

La conjetura

Esta es la conjetura principal de este artículo. Podrá parecer un poco misteriosa en un principio, pero se verá después que tiene una interpretación muy interesante en términos de longitudes de ciertos períodos.

Conjetura 1. Sea $p$ un número primo. Entonces la secuencia de Fibonacci contiene un término $F_n$ que es divisible por $p$ pero no por $p^2$.

Veamos lo que pasa con los números primos inferiores a $10$, a saber, $p = $ $2$, $3$, $5$ y $7$.

  • Para $p=2$ : se tiene $F_3 = 2$, divisible por $2$ pero no por $4$.
  • Para $p=3$ : se tiene $F_4 = 3$, divisible por $3$ pero no por $9$.
  • Para $p=5$ : se tiene $F_5 = 5$, divisible por $5$ pero no por $25$.
  • Para $p=7$ : se tiene $F_8 = 21$, divisible por $7$ pero no por $49$.

¿Qué pasa entonces con los $F_n$ que son divisibles por los cuadrados de estos primeros números primos ?

El número más pequeño de Fibonacci no nulo divisible por $4$ es $F_6 = 8$. Para $p = 3$, $5$ y $7$, hay que esperar hasta
\[ F_{12} \,=\, 144,\quad F_{25} \,=\, 75\:025\quad \text{y } \quad F_{56} \,=\, 225\:851\:433\:717 \,=\, 49 \times 4\:609\:212\:933 \]
para encontrar un número de Fibonacci divisible por $9$, $25$ y $49$, respectivamente.

Como esas observaciones lo sugieren, la Conjetura 1 es de hecho equivalente a la formulación un poco más precisa que sigue.

Conjetura 2. Sea $p$ un número primo. Entonces el primer número de Fibonacci $F_n$ no nulo y divisible por $p$ no es divisible por $p^2$.

Esta conjetura se presta para una verificación parcial por computadora, como lo mostrará implícitamente la continuación de este artículo. Donald D. Wall, su autor, la verificó en 1960 para todos los primos $p$ hasta $10^4=10\:000$ [1], y esta verificación se extendió en 2007 para todos los primos $p$ hasta $2 \times 10^{14}$ [2]. Sin embargo, desde hace medio siglo hasta ahora ¡nadie ha podido dar una demostración !

El Número de Oro

Para quien deseara comprobar esta conjetura sin reflexionar demasiado en un comienzo, un obstáculo aparece de inmediato : la secuencia de Fibonacci crece muy rápido, de manera exponencial.

¿Cuál es su tasa exacta de crecimiento ? Pues es conocida muy bien y tiende al Número de Oro. Recordemos que esta famosa constante, generalmente denotada $\varphi$, es definida así :
\[ \varphi \,=\, \frac{\sqrt{5}+1}2. \]
He aquí un valor aproximado, con sus diez primeros decimales :
\[ \varphi \,\sim\, 1,6180339887\dots \]
Se puede demostrar que el cociente entre dos números de Fibonacci sucesivos, o sea $\displaystyle \frac{F_{n+1}}{F_n}$, tiende efectivamente hacia $\varphi$ cuando $n$ aumenta. Por ejemplo, para $n=20$, se tiene
\[ \frac{F_{21}}{F_{20}} \,=\, \frac{10\:946}{6\:765} \,\sim\, 1,\color{red}{6180339}985218033\dots, \]
que coincide con $\varphi$ en sus 7 primeros decimales. Y a partir de $n = 26$, los números $\varphi$ y $\displaystyle \frac{F_{n+1}}{F_n}$ coinciden por lo menos en sus $10$ primeros decimales.

Aritmética Modular

Un medio muy simple para amagar este obstáculo de crecimiento rápido consiste en utilizar la reducción módulo $m$, una herramienta clásica en teoría de números.

¿De qué se trata ? Comencemos con un ejemplo : la reducción de $167$ módulo $10$ vale $7$, su última cifra.

En toda generalidad, démonos un entero natural $m$ no nulo, el ’’módulo’’. Entonces, para todo número entero $n$, la reducción de $n$ módulo $m$, llamada también la clase de $n$ módulo $m$, es definida como el resto de la división euclidiana de $n$ por $m$.

Así por ejemplo, para el módulo $m=2$, la clase de un entero $n$ módulo 2 revela su paridad : la clase vale 0 si $n$ es par y 1 si $n$ es impar. Y para $m=10$, la clase de $n$ módulo $10$ es dada por su última cifra, como vimos para 167.

Notemos que la secuencia de enteros naturales pasa a ser periódica cuando se la reduce módulo $m$. Por ejemplo, para $m=3$ tenemos :
\[ \begin{eqnarray*} \text{ antes de la reducción : } & 0, & 1, & 2, & 3, & 4, & 5, & 6, & 7, & 8, & 9, & 10, & \dots\\ \text{ después de la reducción : } & \color{red}{0,} & \color{red}{1,} & \color{red}{2}, & 0, & 1, & 2, & 0, & 1, & 2, & 0, & 1, & \dots. \end{eqnarray*} \]
Se obtiene una secuencia periódica de longitud 3, con período $\color{red}{0, 1, 2}$, que simplemente se repite indefinidamente.

Una ventaja mayor de la reducción módulo $m$ es que, por definición, el resultado queda confinado entre los enteros $0, 1, \dots, m-1$.

¡Es un homomorfismo !

Una propiedad fundamental de la reducción módulo $m$ es su compatibilidad con la adición, en el sentido explicado más abajo.

Pero introduzcamos primero una notación útil para la discusión. Para todo entero $n$, notemos $cl(n)$ su reducción o su clase módulo $m$ [3].

Sean ahora $a$ y $b$ dos números enteros. Se ve que para calcular la clase de $a+b$ módulo $m$, es decir para determinar $cl(a+b)$, basta con

  • determinar $cl(a)$ y $cl(b)$,
  • calcular su suma, es decir $cl(a)+cl(b)$,
  • y luego reducir el resultado módulo $m$.

Una fórmula corta lo muestra mucho mejor :
\[ \begin{equation} cl\left(\,a+b\,\right) \,=\, cl\left(\, cl(a) + cl(b)\, \right). \end{equation} \]

Por ejemplo, para $m=2$, esta fórmula vuelve a decir algo que todo lector de este artículo conoce bien, a saber, que

par + par = par,

par + impar = impar,

impar + impar = par.

La ventaja de esta propiedad es clara : para reducir una suma módulo $m$, uno puede comenzar por reducir los sumandos módulo $m$, lo que generalmente facilita las cosas, permitiendo trabajar con números más pequeños.

Aplicada al cálculo de la secuencia de Fibonacci reducida módulo $m$, esta propiedad se revela decisiva. Así, para $m = 3$ por ejemplo, y para construir la secuencia de Fibonacci módulo $3$, no hay ninguna necesidad de calcular los verdaderos números de Fibonacci antes de la reducción. Basta con reducir módulo $3$ en cada etapa. Vamos entonces : sabiendo que
\[ \begin{eqnarray*} 1+1 & = 2 & \text{ módulo } 3,\\ 1+2 & = 0 & \text{ módulo } 3,\\ 2+2 & = 1 & \text{ módulo } 3, \end{eqnarray*} \]
y que sumar $0$ módulo $3$ no cambia nada, igual que la adición ordinaria de $0$, la secuencia de Fibonacci módulo $3$ se reduce a :
\[ \color{red}{0,\, 1},\, 1,\, 2,\, 0,\, 2,\, 2,\, 1,\, \color{red}{0,\, 1},\, 1,\, 2,\, 0,\, 2,\, 2,\, 1,\, \color{red}{0,\, 1},\, 1, \, 2,\, 0,\, 2,\, 2,\, 1,\, \color{red}{0,\, 1},\,1, \, \dots \]
Uno parte con $0,1$ y cada término sucesivo es la suma —módulo $3$, por supuesto— de los dos términos precedentes.

La estructura obtenida es muy simple : es una secuencia periódica, de período $0,\, 1,\, 1,\, 2,\, 0,\, 2,\, 2,\, 1$ de longitud $8$, que se repite indefinidamente. Y para descubrirla, una vez más ¡no hubo ninguna necesidad de calcular explícitamente los verdaderos números de Fibonacci ! Lo más interesante de la reducción módulo $3$, o más generalmente módulo $m$, es justamente su compatibilidad con la adición.

En términos científicos, se dice que la reducción módulo $m$ es un homomorfismo, justamente en virtud de su compatibilidad con la adición, tal como lo muestra la igualdad (1) de arriba.

Ahí uno comprende mejor por qué los matemáticos son tan apasionados de los homomorfismos. Como se ve en este ejemplo, es porque estos —cuando están disponibles— permiten hacer interactuar entre sí diferentes estructuras matemáticas de una manera coherente [4].

Periodicidad

Nos enfrentamos ahora a una pregunta absolutamente natural : ¿es cierto que para todo otro valor del módulo $m$, la secuencia de Fibonacci reducida módulo $m$ es periódica ?

Para hacernos una idea probemos de nuevo el caso $m=2$. Un simple cálculo muestra que uno obtiene de nuevo una secuencia periódica, aquí con un período de longitud $3$ :

\[ \color{red}{0,\, 1},\, 1,\, \color{red}{0,\, 1}, \, 1,\, \color{red}{0,\, 1},\, 1,\, \dots . \]

Esta estructura revela además que el hecho de que una de cada tres veces, o sea para $n=0, 3, 6, 9$, etc., el número de Fibonacci $F_n$ es par, y en los otros casos es impar.

Lo estábamos sospechando : este fenómeno de periodicidad es completamente general. Fue Lagrange quien parece haberlo observado primero hace más de dos siglos.

Teorema. Para todo entero natural $m$, la secuencia de Fibonacci reducida módulo $m$ es periódica.

Demostración informal

Como en el caso $m=3$ y $m=2$, está claro que tan pronto se encuentre $0,1$ como par consecutivo en la secuencia reducida, esta se vuelve periódica a partir de este punto, ya que todo par consecutivo determina el ’’futuro’’ de la secuencia, tanto original como reducida.

Falta entender por qué necesariamente encontraremos $0,1$ como par consecutivo. Bueno, dado que los términos posibles de la secuencia reducida están confinados entre $0$ y $m-1$, no hay sino un número finito de pares consecutivos posibles, a saber, a lo más $m^2$.

Por lo tanto, al ser la secuencia infinita, al menos una pareja consecutiva $a,b$ va a encontrarse repetida en dos lugares diferentes de la secuencia reducida. Esto determina todos los términos posteriores a $b$. Sin embargo, y aquí hay un punto clave, esto determina también los términos anteriores a $a$. En efecto, la fórmula
\[ F_{n+2}  \, = \, F_{n} + F_{n+1}, \]
que implica que todo par consecutivo en la secuencia,determina también su futuro, equivale a esta :
\[ F_{n}  \, = \, F_{n+2} - F_{n+1}. \]
Esta fórmula implica que todo par consecutivo de la secuencia determina igualmente el pasado, es decir, ¡los términos que vienen antes !

Por lo tanto, en la secuencia de Fibonacci reducida módulo $m$, el primer par consecutivo $a,b$ que se repite es necesariamente el par $0,1$, ya que este es ’’el padre de los pares consecutivos sucesivos’’. Dicho de otra manera, el par $0,1$ reaparece antes que todos los demás.

Esto demuestra —informalmente, pero todas las ideas están allí— la periodicidad de la secuencia de Fibonacci reducida módulo $m$. Notemos además una consecuencia imprevista de esta demostración : la longitud del período no puede en ningún caso exceder a $m^2$.

Una consecuencia

Una consecuencia interesante de esta periodicidad es que, para todo entero natural $m$, hay una infinidad de números de Fibonacci $F_n$ que son divisibles por $m$.

En efecto, como la secuencia comienza por $0$ y es periódica módulo $m$, encontraremos $0$ una infinidad de veces en la sucesión reducida módulo $m$. Ahora bien, un número que da $0$ módulo $m$, no es sino que un múltiplo de $m$ [5]. Por lo tanto, la infinidad de $0$ dentro de la secuencia de Fibonacci reducida módulo $m$ corresponde a la infinidad de términos $F_n$ que son divisibles por $m$.

En particular, sabemos ahora que para todo primo $p$, existe una infinidad de términos $F_n$ que son divisibles por $p$. Y también que, entre ellos, una infinidad serán divisibles por $p^2$. Sabemos también que se encuentra periódicamente, con la regularidad de un reloj. Pero esos dos conjuntos, los $F_n$ divisibles por $p$ y aquellos divisibles por $p^2$, ¿pueden coincidir al menos para ciertos primos $p$ exóticos ? Se sospecha fuertemente que no. Es precisamente lo que predice la Conjetura 1.

¿Longitud del período ?

Vimos que, para un módulo $m$ dado, la secuencia de Fibonacci reducida módulo $m$ es periódica. Muy bien. ¿Pero qué longitud de período se encuentra ? Es ahí cuando el asunto se complica. No sabemos la respuesta en general.

Para un entero natural $m$ dado, notemos $L(m)$ la longitud del período de la secuencia de Fibonacci reducida módulo $m$. Por ejemplo, vimos más arriba que $L(2)=3$ y $L(3)=8$. Pese a que numerosas propiedades de la función $L(m)$ son conocidas, esta nos resulta aún muy misteriosa.

Aquí hay un ejemplo de un resultado conocido, en este caso debido a Donald D. Wall y datando de 1960 [6].

Teorema. Sea $p$ un número primo.

  • Si la clase de $p$ módulo $5$ vale $1$ o $4$, entonces $L(p)$ divide a $p-1$.
  • Si la clase de $p$ módulo $5$ vale $2$ o $3$, entonces $L(p)$ divide a $2(p+1)$.

Desgraciadamente, si bien a menudo $L(p)$ es igual a $p-1$ o $2(p+1)$, a veces también sucede que es bastante más pequeño que esos valores máximos respectivos. ¿A qué divisor de $p-1$ o de $2(p+1)$ corresponde el número $L(p)$ ? ¡La respuesta a esta pregunta es en general desconocida !

La Conjetura 1 reexaminada

Sea $p$ un número primo. Acabamos de ver que el valor exacto de $L(p)$ es desconocido en general. Pero ahora, si después de haber reducido la secuencia de Fibonacci módulo $p$, se la reduce también módulo $p^2$, ¿cómo se comparan las longitudes obtenidas $L(p)$ y $L(p^2)$ ? Ahí, la situación es claramente mejor... hasta cierto punto.

Para empezar, veamos lo que se encuentra para $p = 2$ y para $p=3$.

  • Módulo $2$ : $\color{red}{0, 1}, 1, \color{red}{0, 1}, 1, \dots $
  • Módulo $4$ : $\color{red}{0, 1}, 1, 2, 3, 1, \color{red}{0, 1}, 1, \dots$

Obtenemos entonces :
\[ \begin{eqnarray*} L(2) & = & 3, & & \\ L(4) & = & 6 & = & 2 \times L(2). \end{eqnarray*} \]

  • Módulo $3$ : $\color{red}{0, 1}, 1, 2, 0, 2, 2, 1, \color{red}{0, 1}, 1, \dots$
  • Módulo $9$ : $\color{red}{0, 1}, 1, 2, 3, 5, 8, 4, 3, 7, 1, 8, 0, 8, 8, 7, 6, 4, 1, 5, 6, 2, 8, 1, \color{red}{0, 1}, 1, \dots$

Y aquí obtenemos :
\[ \begin{eqnarray*} L(3) & = & 8, & & \\ L(9) & = & 24 & = & 3 \times L(3). \end{eqnarray*} \]
¡Ah ! ¿Estaremos por casualidad frente a un comportamiento regular ? Podría uno esperar una fórmula general de la forma $L(p^2) \, = \, p \times L(p)$ ?

¡Casi ! Aquí damos otro resultado de Donald D. Wall, del mismo artículo de 1960 citado antes.

Teorema. Sea $p$ un número primo. Una de dos : o bien $L(p^2)=L(p)$, o bien $L(p^2)=p \times L(p)$. Además, si hay un número de Fibonacci $F_n$ que sea divisible por $p$ pero no por $p^2$, entonces es la segunda alternativa la que prevalece :
\[ L(p^2) \, = \, p \times L(p). \]

En lo que respecta a la motivación principal de la Conjetura 1, ¡todo se ilumina ! En efecto, dado el resultado de arriba, su validez supondría que, aún cuando las longitudes $L(p)$ y $L(p ^2)$ para $p$ primo sigan siendo desconocidas en general, su cuociente valdría siempre exactamente $p$.

Delante del océano de misterios aritméticos de una secuencia tan célebre, sería un lindo granito de arena.

Trabajos prácticos

Probar la Conjetura 1 a mano para los pequeños números primos puede ser muy entretenido, y podría inspirar a los adolescentes y otros humanos en busca de liberación —al menos temporal— de la influencia de sus smartphones.

Para un número primo $p$ dado, encontrar un $F_n$ divisible por $p$ pero no por $p^2$ puede hacerse reduciendo simultáneamente la secuencia de Fibonacci módulo $p$ y módulo $p^2$, esperando que al nivel del primo $0$ hallado en la reducción módulo $p$, el término correspondiente sea no nulo módulo $p^2$.

Ilustremos esto con el caso $p=11$.
\[ \begin{eqnarray*} \text{Módulo } 11 & &: & & 0 & & 1 & & 1 & & 2 & & 3 & & 5 & & 8 & & 2 & & 10 & & 1 & & \color{red}{0} & & \dots \\ \text{Módulo } 11^2 & &: & & 0 & & 1 & & 1 & & 2 & & 3 & & 5 & & 8 & & 13 & & 21 & & 34 & & \color{red}{55} & & \dots \end{eqnarray*} \]

La presencia de $0$ en la décima posición de la primera línea indica que $F_{10}$ es divisible por $11$. Pero como el término correspondiente es no nulo en la segunda línea, se deduce que $F_{10}$ ¡no es divisible por $11^2$ ! Ahí está entonces la Conjetura 1 validada en el caso $p = 11$.

¿Fácil, verdad ? Entonces, ¡a divertirse !

Post-scriptum :

El autor agradece intensamente a los relectores con seudónimos Serma, Bruno Langlois, Cidrolin y julesdesp por su atenta relectura y sus comentarios constructivos, así como a Carole Gaboriau y Maï Huong Pham-Sauvageot por su valiosa ayuda.

Article original édité par Shalom Eliahou

Notes

[1En esa época remota donde los computadores no corrían por las calles, el hecho de que D.D. Wall trabajara en IBM facilitó ciertamente la realización de ese cálculo.

[2R.J. Mcintosh y E.L. Roettger, A search for Fibonacci-Wieferich and Wolstenholme Primes, Math. Comp. 76 (2007) 2087-2094.

[3En principio, habrá que incluir $m$ en la notación, pero se puede evitar si esta está establecida en la discusión.

[4¡Ah, la coherencia ! De verdad uno de los más altos valores del pensamiento matemático.

[5Por definición de la reducción módulo $m$, como resto de la división euclidiana por $m$.

[6D.D. Wall, Fibonacci series modulo $m$, American Math. Monthly vol. 67 (1960), 525-532.

Partager cet article

Pour citer cet article :

Julio E. De Villegas, Jimena Royo-Letelier — «Misterios aritméticos de la sucesión de Fibonacci» — Images des Mathématiques, CNRS, 2019

Commentaire sur l'article

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?