La sucesión de Fibonacci y los números primos

¿Quién no ha oído hablar de la sucesión de Fibonacci? Bueno, mucha gente, seguro, pero no se puede negar que es una de las sucesiones más famosas en el mundo de las matemáticas. ¿La más famosa? Bueno, yo no diría tanto, a mí la primera sucesión que me enseñaron cuando era un mengajo fue la de los números naturales (1, 2, 3, 4, 5, 6, 7, 8, etc.), pero aún así la de Fibonacci es muy famosa y tiene multitud de propiedades. Pero… ¿habéis oído hablar de los primos de Fibonacci? No, no me refiero a los hijos de sus tíos o sus tías, sino a los términos de dicha sucesión que son números primos…

Pero bueno, empecemos por el principio, diciendo primero en qué consiste dicha sucesión, ya que algunos lectores no la conocerán. Pues es muy sencillo, el primer termino de dicha sucesión será el 1, el siguiente será de nuevo el 1, y a partir de ahora los demás términos se van obteniendo de los dos anteriores, es decir, el tercer término será $latex 1+1=2$, el cuarto término será $latex 1+2=3$, el quinto $latex 2+3=5$, después $latex 3+5=8$ y así:

$latex 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377,610, 987, 1597, 2584, 4181, 6765\dots $

Denotemos $latex F_n$ al elemento en la posición $latex n$ de dicha sucesión. Tendremos entonces que $latex F_1=F_2=1$ y para  n>2 tendremos que $latex F_n=F_{n-1}+F_{n-2}$. Bueno, en algunos sitios la sucesión empieza con $latex F_0=0$, pero vamos, empezar por 1 o por 0 no nos va a afectar mucho.

Si buscáis por internet podréis encontrar muchos datos curiosos de dicha sucesión. Por ejemplo juntando cuadrados cuyos lados vienen dados por dicha sucesión, se puede construir una espiral como la de la imagen de arriba, espiral que por cierto se llama espiral de Fibonacci. Otra curiosidad es que si hacemos el límite de $latex F_n/F_{n-1}$ este será el famoso número aureo $latex \displaystyle \varphi=\frac{1+\sqrt{5}}{2}$, pero es que esta no es su única relación con el número auero, también se tiene que

$latex \displaystyle F_n=\frac{\varphi^n-(1-\varphi)^n}{\sqrt{5}}.$

La primera vez que vi esta última relación me sorprendió mucho, cómo es posible que la expresión que acabo de poner dé un número entero, y encima coincida con la sucesión de Fibonacci. En cualquier caso, no es muy difícil comprobar que dicha igualdad es cierta, se puede hacer por inducción. Y llegar a ella sin conocerla se puede hacer por ejemplo sabiendo diagonalizar matrices.

Pero bueno, voy a centrarme como he dicho al principio en los primos de Fibonacci, que son simplemente los números primos que aparecen en dicha sucesión. Y es que si os fijáis en la sucesión, enseguida se ve que salen varios números primos: 2, 3, 5, 13, 89, 233, 1597… ¿No os da la sensación de que aparecen números primos con demasiada frecuencia? A mí al menos me dio esa sensación. Vamos a observar un poco la sucesión, ¿qué términos son primos? Pues inicialmente tendremos los siguientes:

$latex F_3=2, F_4=3, F_5=5, F_7=13, F_{11}=89, F_{13}=233\dots$

Uhm, ¿no veis algo curioso? Fijaos en los índices, es decir, en los números $latex n$ tales que $latex F_n$ es un número primo. Los que tenemos arriba son $latex 3, 4, 5, 7, 11\text{ y }13$. ¿No veis alguna particularidad? Si nos olvidásemos del 4, todos los demás son números primos. No solo eso, es que hemos empezado por el primer primo impar y aún no nos hemos saltado ningún número primo mayor. ¿Se tendrá que si $latex p$ es un número primo entonces $latex F_p$ también lo es? Bueno, el 2 fallaría, pero ¿qué pasa con los siguientes?  Después del 13, los siguientes números primos son 17, 19, 23 y 29. Pues se tiene que

$latex F_{17}=1597, F_{19}=4181, F_{23}=28657, F_{29}=514229.$

¿Son números primos? Pues no, 3 de ellos sí, pero nos falla $latex 4181=37\times 113$. ¡Uy!, ¡casi!, no es primo pero solo tiene 2 factores. Una lástima, no tenemos una fórmula para obtener números primos. Aún así da la sensación de que hay muchos en dicha sucesión ¿no? ¿Habrá infinitos primos de Fibonacci? Pues..

Actualmente no se sabe si existen infinitos primos de Fibonacci.

De hecho lo que se ha observado es que la frecuencia de primos de Fibonacci disminuye bastante conforme avanzamos en la sucesión. Aunque de los 10 primeros númeos primos $latex p$ solo haya 2 tales que $latex F_p$ no sea primo, entre los 1229 primeros números primos, solo hay 29 tales que $latex F_p$ es un número primo. El mayor primo de Fibonacci (que está en el puesto número 33) conocido hasta este momento (que yo sepa) es el $latex F_{81839}$ que es un número con más de 17.000 dígitos. Como veis, en matemáticas no está todo inventado. Pero aún nos podemos hacer varias preguntas. Hemos visto que salvo $latex F_4=3$, los primos de Fibonacci que nos han ido saliendo tienen todos un índice primo. ¿Será esto verdad? Pues sí:

Todo primo de Fibonacci distinto a 3 tiene como índice un número primo.

O dicho de otra forma, si $latex n$ no es un número primo y es distinto a 1 y 4, entonces $latex F_n$ tampoco será un número primo. Y como sobre todo esto es de lo que va la entrada de hoy, no me voy a limitar a afirmarlo sino que os lo voy a demostrar de la forma más sencilla que se me ha ocurrido, y que sea autocontenida. Primero vamos a partir de la siguiente afirmación:

Si un número m divide a un número n entonces $latex \boldmath F_m$ divide a $latex F_n$.

Más abajo os demuestro esta afirmación, pero primero vamos a ver cómo esta afirmación nos permite demostrar que todo primo de Fibonacci distinto a 3 tiene índice primo:

Tomemos un primo de Fibonacci $latex F_n$. Si $latex n$ no es un número primo, existirá un número natural $latex m\neq 1$ y menor que $latex n$ que divida a $latex n$, pero entonces por nuestra afirmación tendremos que $latex F_m$ divide a $latex F_n$ por lo que $latex F_n$ no puede ser un número primo. Por tanto no puede pasar que $latex n$ no sea un número primo…

¿Ha sido sencillo? Pues ojo, algún error tiene que tener la demostración ya que si estuviese bien, al ser $latex F_4=3$ un número primo deduciríamos que 4 es un número primo. Venga, antes de seguid leyendo pensad un poquito en cuál es el error y cómo solucionarlo… Os pongo en el siguiente spoiler cuál es el fallo y cómo solucionarlo:

[spoiler]


Bien, el error estar en decir que si $latex F_m$ divide a $latex F_n$ entonces $latex F_n$ no es un número primo. Para poder afirmar esto, primero tenemos que asegurarnos de que $latex F_m$ no es ni 1 ni el propio $latex F_n$. Está claro que si n>2 entonces $latex F_m$ no es $latex F_n$ ya que la sucesión va creciendo y $latex m<n$. Pero la pega está en que podríamos tener que m=2 y por tanto $latex F_m=1$. Y eso es lo que pasa con el número 4, su único divisor distinto a él mismo y a 1 es el número 2 y por eso nos falla en dicha demostración. Sin embargo para cualquier otro número mayor que 4 y que no sea primo, podremos encontrar un divisor distinto a sí mismo y mayor que 2. ¿Cómo podemos afirmar esto? Pues si escribimos $latex n$ como $latex n=p\cdot q$, con $latex p$ un número distinto a 1 y distinto a n, si $latex p$ es distinto a $latex 2$ habríamos terminado, y si no lo es, pues $latex q$ tiene que ser distinto a $latex 2$ puesto que $latex n$ no es $latex 4$.

Ahora sí, teniendo en cuenta este pequeño detalle, hemos probado que salvo el $latex F_4=3$, todo primo de Fibonacci tiene que tener índice primo.


[/spoiler]

Nos quedaría solo probar que si $latex m$ divide a $latex n$ entonces $latex F_m$ divide a $latex F_n$. Si buscáis por internet, se puede ver que se deduce a partir de la siguiente curiosa propiedad de la sucesión de Fibonacci. Para $latex n, m$ dos números, denotemos por $latex MCD(n,m)$ el máximo común divisor de dichos números, es decir, el mayor número entero que divida a ambos números, se tiene entonces que:

$latex MCD(F_n,F_m)=F_{MCD(n,m)}.$

A partir de esta propiedad sería inmediato probar lo que queremos. Pero claro, tendríamos que probar esta propiedad también. No es excesivamente complicado, pero como sale demasiado larga voy a probar por otro camino más corto. Aún así merecía la pena comentaros la relación de la sucesión de Fibonacci con el máximo común divisor. Voy a probar primero la siguiente propiedad:

$latex F_{m+k}=F_{m-1} F_{k}+F_m F_{k+1},$

donde $latex m, k$ son números enteros positivos. Para ver esto, voy a fijar un número entero positivo $latex k$ y voy a hacer inducción sobre el elemento $latex m$. Os acabo de poner un link sobre lo que es la inducción (matemática), pero vamos, no hace falta que lo leáis, lo vais a ver claro. La prueba os la pongo en el siguiente spoiler:

[spoiler]


Primer paso: comprobamos que dicha igualdad es cierta para m=1,2. Y efectivamente,  para m=1 se tiene que $latex F_{m-1}=F_0=0$ y $latex F_m=F_1=1$ y por tanto:

$latex F_{m-1} F_{k}+F_m F_{k+1}=0 F_{k}+1 F_{k+1}=F_{k+1}=F_{m+k}.$

Y para m=2 se tiene que $latex F_{m-1}=F_1=1$ y $latex F_m=F_2=1$ así que

$latex F_{m-1} F_k+F_m F_{k+1}=1 F_{k}+1 F_{k+1}=F_{k+2}=F_{m+k}.$

Segundo paso: sabemos que es válido hata m=2. Supongamos que es válida hasta cierto $latex n$ con $latex n$ al menos 2.

Tercer paso: sabiendo que la igualdad se cumple para m=n, veamos si se cumple para m=n+1. Pues bien, tenemos que demostrar que la igualdad se cumple al cambiar  m por n+1, es decir

$latex F_{n+1+k}=F_n F_k+F_{n+1} F_{k+1}.$

Por hipótesis de inducción (segundo paso) estamos suponiendo que la propiedad se cumple al cambiar m por n o por n-1, es decir, sabemos que:

$latex F_{n+k}=F_{n-1} F_{k}+F_n F_{k+1}.$

$latex F_{n-1+k}=F_{n-2} F_{k}+F_{n-1} F_{k+1}.$

Ahora bien, por definición tenemos que $latex F_{n+1+k}=F_{n+k}+F_{n-1+k}$ por lo que sumando las dos igualdades anteriores tendremos que $latex F_{n+1+k}$ es igual a

$latex F_{n-1} F_k+F_n F_{k+1}+F_{n-2} F_{k}+F_{n-1} F_{k+1}.$

Sacando factor común por un lado $latex F_k$ y por otro $latex F_{k+1}$ se tiene que

$latex F_{n+1+k}=\large{(}F_{n-1}+F_{n-2}\big{)} F_k+\left(F_n+F_{n-1}\right) F_{k+1}.$

Por último, como sabemos que $latex F_n=\large{(}F_{n-1}+F_{n-2}\big{)}$ y $latex F_{n+1}\left(F_n+F_{n-1}\right)$ la igualdad anterior se convierte en

$latex F_{n+1+k}=F_n F_k+F_{n+1} F_{k+1},$

y con esto queda completado el tercer paso y con ello la prueba por inducción.

¿Entendéis por qué esto nos permite comprobar que la igualdad es cierta para todo $latex n$? Bien, en el Paso 1 hemos visto que era cierto para 1 y 2. Como es cierto para 1 y 2, el Paso 3 nos permite deducir que es cierto para 3. Una vez que sabemos que es cierto también para 3, el Paso 3 nos permite deducir que también lo es para 4, luego para 5, luego para 6 y así con cualquier número natural.


[/spoiler]

Ya podemos ver que si m divide a n entonces $latex F_m$ divide a $latex F_n$. Esta misma afirmación la reescribimos de la siguiente forma:

Si $latex n=d\cdot m$ entonces $latex F_m$ divide a $latex F_n$.

Y esto lo vamos a demostrar de nuevo por inducción, en este caso sobre d:

Paso 1: Claramente es cierto para $latex d=1$ ya que en ese caso $latex n=m$ y por ello $latex F_m=F_n$.

Paso 2: Supongamos que la afirmación es cierta para cierto $latex d$, es decir $latex F_m$ divide a $latex F_{d\cdot m}$.

Paso 3: Veamos qué pasa para $latex n=(d+1)\cdot m$. Utilizando la igualdad

 $latex F_{m+k}=F_{m-1} F_{k}+F_m F_{k+1}$

con $latex k=d\cdot m$ se tiene que

$latex F_{n}=F_{m+d\cdot m}=F_{m-1} F_{d\cdot m}+F_m F_{d\cdot m+1}.$

Ahora bien, por hipótesis de inducción (Paso 2) se tiene que existe un número entero $latex q$ tal que $latex F_{d\cdot m}= q F_m$ y por tanto

$latex F_n=F_{m-1}\cdot q\cdot F_m+F_m F_{d\cdot m+1}=F_m (F_{m-1}\cdot q+F_{d\cdot m+1})$

y por tanto tenemos que $latex F_m$ divide a $latex F_n$.

Espero que os haya resultado tan curioso como a mí.

PD: Con esta entrada participo en la Edición 4.12310 del Carnaval de Matemáticas cuyo blog anfitrión es Geometría dinámica.

21 Responses to “La sucesión de Fibonacci y los números primos”

  1. […] La sucesión de Fibonacci y los números primos (Zurditorium) […]

  2. Elruso dice:

    “Todo primo de Fibonacci distinto a 5 tiene como índice un número primo.” Debería aparecer 3, no 5.

  3. Carlos dice:

    @Elruso:
    Cierto, que $latex F_4=3$ y no 5 como había puesto. Ahora mismo lo edito y pongo el 3 en los que corresponda (espero no saltarme ninguno).

    ¡Gracias!

  4. La sucesión de Fibonacci y los números primos…

    ¿Quién no ha oído hablar de la sucesión de Fibonacci? Bueno, mucha gente, seguro, pero no se puede negar que es una de las sucesiones más famosas en el mundo de las matemáticas. ¿La más famosa? Bueno, yo no dirí…

  5. César dice:

    Yo soy muy poco diestro en matemáticas. De hecho soy nulo en matemáticas. Pero leyendo esto me asaltó una duda: si empezásemos la serie en 0 (y no en 1), ¿F1 (no sé poner subíndices en la web) no sería igual a 0, por ser el primer término de la serie? ¿O si empezamos la serie en 0, tendríamos que marcar necesariamente que F0=0 para que así F1=1, y lo sucesivo?

  6. Carlos dice:

    @César:
    Normalmente cuando se empieza por 0 a ese término se le llama $latex F_0$, así lo que por ejemplo he comentado aquí seguiría siendo válido. Si 0 fuese el $latex F_1$, de hecho no sería verdad lo de que si es primo su subíndice es primo.

    Saludos

  7. XDuende dice:

    Toda mi vida, habia pensado que la serie de Fibo, comenzaba en 0 y no en 1, ademas si seguimos la regla el tercer termino (1), es la suma de los 2 anteriores.

  8. Carlos dice:

    @XDuende:
    Como acabo de contestar a César, se puede empezar por 0, pero en tal caso ese es el elemento 0, es decir $latex F_0=0$, $latex F_1=1$, $latex F_2=1$ y $latex F_3=2$. Dicho de otra forma, el término 1 es el 1 y el término 0 (que podemos considerar o no) es el 0.

  9. MFC dice:

    Sin embargo, si la frecuencia de términos de la sucesión en los que se da que para un n primo tenemos un Fn primo tiende a cero cuando n tiende a infinito, no podríamos asegurar que NO hay infinitos términos tal que n sea primo y Fn también?

  10. Carlos dice:

    @MFC:
    Eso pone en el artículo, que no se sabe.

  11. Karmela dice:

    “Para poder afirmar esto, primero tenemos que asegurarnos de que F_m no es ni 1 ni el propio F_n”, esto ya está considerado en la hipótesis

  12. Karmela dice:

    Enuncia el caso d+1, pero no utiliza n=(d+1)*m en la inducción. Me huele a machetazo.

  13. Carlos dice:

    @Karmela:
    Sobre tu primer comentario, a ver, no, porque en un principio en la hipótesis dice que m no es 1 y que es menor que n, pero solo eso no basta ya que por ejemplo m podría ser 2 (y n ser 4). Y en el caso de m=2 se tiene que $latex F_m=1$, así que como ves la hipótesis (a no ser que te refieras a otra) no impide que $latex F_m$ pueda valer 1.

    Y sobre lo que dices de la inducción, te has liado, ¿eh? Digo que voy a demostrar el caso n=(d+1)*m, y evidentemente para demostrar ese caso NO puedo utilizar el caso n=(d+1)*m. Si lo quiero demostrar no lo puedo usar para demostrarlo. Lo que sí utilizo es el caso n=d*m que es el que sí podía usar.

    Échale un vistazo y si sigues sin entender algo me lo dices e intento aclarártelo.

  14. mariano dice:

    pero esos calculos no estavan ya cerrados a mi me suena a canelo para vender

  15. Carlos dice:

    @mariano:
    ¿Cómo? Si lo que estás diciendo es que estoy escribiendo cosas que ya se sabían, sí, es así, si fuera algo nuevo lo habría escrito para un artículo, no para el blog.

  16. PeterPan dice:

    La serie de fibo tiene valor 0 en la posición 1, no hay a donde perderse.

  17. click this link now

    Zurditorium, como si se hiciera con la mano izquierda

  18. Angel Moreno dice:

    Otra curiosidad importante (no se si es cierta):

    Si Fib(p) es primo ==> Fib(p)+1 es divisible por p, o bien, Fib(p)-1 es divisible por p.

    F(11) = 89 = 8*11 + 1
    F(17) = 1597 = 94*17 – 1

  19. Angel Moreno dice:

    Hay que exceptuar el 5.
    F(5) = 5.

    F(19) = 4181 = 37 * 113 = (2*17 – 1) * (6*17 – 1)

  20. Angel Moreno dice:

    Me equivoque:

    F(19) = 4181 = 37 * 113 = (2*19 – 1) * (6*19 – 1)

  21. Julio dice:

    Solo Para presentarme… no estoy a vuestra altura matematica… pero los estoy intentando seguir … …

Leave a Reply