Cómo detectar números primos usando el triángulo de Pascal

En el conocidísimo triángulo de Pascal pueden encontrarse multitud de tesoros matemáticos (recopilé unos cuantos aquí). Algunos de ellos son fáciles de localizar, pero otros están algo más escondidos. Hoy hablaremos de cómo encontrar la sucesión de Fibonacci y los ¡¡números primos!! en este interesante triángulo numérico.

¿Que no sabes qué es el triángulo de Pascal? Pues aquí lo tienes. Cada fila tiene unos a izquierda y derecha, y cada posición intermedia se calcula sumando los dos números que tiene justo encima:

Triángulo de Pascal

En este blog ya hemos tratado algunos de estos tesoros de los que hablábamos al principio. Hemos visto su relación con los números de Catalan; vimos cómo encontrar el número e y el número Pique aparecen relacionados con el número 89 y el número 109; presentamos una interesante conjetura sobre sus elementos y también enseñamos una forma de relacionar el triángulo de Pascal y la sucesión de Fibonacci

…y por ahí vamos a comenzar. La relación que vimos en aquella entrada es la que se puede ver en la siguiente imagen:

Pues hace poco me encontré una anotación en Futility Closet en la que daban otra forma de encontrar los números de Fibonacci en el triángulo de Pascal. La cuestión es como sigue:

Coloca la primera fila, el 1, y luego coloca el resto de filas desplazadas una posición hacia la derecha respecto de la fila justo anterior. Si ahora sumamos las columnas que nos quedan, obtenemos los números de la sucesión de Fibonacci:

Precioso, ¿verdad? Pues sí…pero si le echamos un nuevo vistazo a la tabla con las filas desplazadas y a la imagen que puse antes sobre los números de Fibonacci…¿lo veis? Exacto: son la misma cosa. Por lo que, por ahora, esto no aporta mucho más que lo que ya teníamos.

La cosa es que, al final de aquel post de Futility Closet, aparecía un enlace a otro post del mismo blog en el que se hablaba de números primos y el triángulo de Pascal (concretamente éste). Y de ello vamos a hablar ahora.

Lo que nos enseñaba Greg Ross en aquella entrada era una forma de detectar números primos usando los elementos del triángulo de Pascal de una manera cuando menos curiosa, y vamos a explicarla. Creamos una tabla en la que colocamos los enteros mayores o iguales que cero en la primera fila y en la primera columna, y dentro colocamos las filas del triángulo de Pascal de manera que la fila n comience en la columna 2n. Es decir, la fila 0 comenzará en la fila 2·0=0, la fila 1 en la columna 2·1=2, la fila 2 en la columna 2·2=4, y así sucesivamente. Las 8 primeras filas quedarían de la siguiente forma:

¿Cómo podemos ahora detectar números primos? Pues así:

Un número de la fila superior es primo si cada uno de los elementos de su columna es divisible por su correspondiente número de fila.

Podéis ver que este resultado se cumple en la tabla que hemos visto justo antes. Se puede ver que los números primos, recuadrados en rojo, cumplen que todos los elementos de su columna son divisibles entre los de la fila a la que pertenecen:

Este curioso resultado data de 1971 y fue demostrado por Henry B. Mann y Daniel Shanks. Podéis ver la demostración (bastante corta y sencilla) en A necessary and sufficient condition for primality, and its source.


Esta entrada participa en la Edición 8.1 del Carnaval de Matemáticas, que en esta ocasión organiza nuestro querido amigo Tito Eliatron.

Author: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

19 Comments

  1. Del tri{angulo de Pascal también se puede deducir un caso del Pequeño Teorema de Fermat: «Cuando 2 elevado a la n menos 2 es igual a m, si m es multiplo de n, entonces n es primo.»

    Post a Reply
    • Es falso lo que dices, el enunciado correcto es el recíproco. Por ejemplo, es fácil ver que  2^{2047}\equiv 2 \ mod \ 2047 por lo que tendríamos que 2 elevado a la 2047 menos 2 es múltiplo de 2047 pero 2047 no es primo, de hecho 2047=23*89 . Saludos

      Post a Reply
      • Hola Cristhuk, no entiendo cómo dices que 2^2047 es congruente con 2 en módulo 2047 si ninguna potencia de 2 es impar.

        Post a Reply
        • No se que tiene que ver.

          4096 es congruente con 2 modulo 2047 y es par..

          4096 = 2047 * 2 + 2

          Cristhuk tienen razon, los primos cumplen que 2^(n-1) es congruente con 1 modulo n.
          Pero hay números no primos que también cumplen esa propiedad.

          Post a Reply
    • Hola Nilton, yo también he llegado a esa conclusión y acortando un poquito más, sería (2^(n-1)-1)/n

      Post a Reply
  2. Al observar el triangulo puedo ver que el segundo numero de la n-esima fila es el mismo que el n-esimo elemento de la serie de fibonacci. Por lo menos viendo los del grafico de arriba, el 5 esta en la 5ta fila, como segundo numero. Y el 8 esta en la octava fila, segundo numero. ¿Saben si se cumple para todo elemento de la serie?

    Post a Reply
    • La deducción es general para todas las filas con n número natural {1,2,3,..}, y no solo para la serie de Fibonacci, sino para todas las series de naturales: Ej, para los primos, en la 7ma fila el segundo número es el 7…
      _____________________________________________________
      primos (con un numero primo de digits) sueltos:
      1111111111111111111 – 19d
      22333555557777777111111111111111111111113131313131313131313131313171717171717171717171717171717171737 – 101d(un primo mayor de Google)
      23571113171923293137414347535961677173798389971011031071091131271311371391491511571631671731791811951 – 101d
      11111111111111111111111 – 23d
      10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000267 – 101d(el primer primo mayor de Google)
      primos procesados en numberempire.com
      lo mismo que 100.000! : https://magicterra.blogspot.com/2017/07/factorial-de-100mil.html

      Post a Reply
    • Uhhh, comentario tan sencillo pero hay que hincarle el diente con cuidado!
      Tu comentario esta divido en dos partes que son diferentes:
      PRIMERA. «Al observar el triángulo puedo ver que el segundo número de la n-ésima fila es el mismo que el n-ésimo elemento de la serie de fibonacci»
      Así dicho, la conclusión es equivocada: por contraejemplo, en la 4-ésima fila del Triángulo, el segundo número es el 4 (y 4 no es el 4-ésimo elemento de la serie de Fibonacci >>> el 4-ésimo elemento de esa serie es el 3).
      SEGUNDA. «Por lo menos viendo los del gráfico de arriba, el 5 esta en la 5ta fila, como segundo número. Y el 8 esta en la octava fila, segundo número» (que es una afirmación diferente a la PRIMERA).
      Dicho así, tampoco se cumple. Se cumple tu ejemplo, siempre y cuando cambiamos la expresiones 5ta por 5-ésima y octava por 8-ésima. Lo que pasa es que se cumple para todos los números n>0, (de la 1-ésima fila en adelante y NO SOLO para los n que se correspondan con un numero de mi amigo Fibo).
      La observación, con esas condiciones, se cumple porque por definición los números de la la 1-ésima fila del Triángulo son 1, 1 (segundo número es el 1), y en las demás filas el segundo número es la suma de 1 + el segundo número de la fila anterior, y por lo tanto esos segundos números son , 2, 3, 4 .. etc, etc, y se corresponderan con los filas 2. 3. 4, … etc, etc -ésimas.
      POR FIN, con todas las anteriores aclaraciones, la respuesta a tu pregunta es …es … …es …es … SI!!

      Post a Reply
  3. Gracias Miguel Angel… estoy sorprendido!. Qué bellas son las mates!!!

    Post a Reply
  4. Hay algo más en el triángulo de Pascal con relación a los primos. El primer número después del 1 cuando es primo, todos los demás de su fila son múltiplos de él a excepción del 1, con el resto de los números no ocurre, así por ejemplo en la fila del 9 hay un 84 que no es múltiplo de 9. Voy a probar un poco más.

    Post a Reply
    • Donde no hay patrón, no hay patrón. Se rompe en el 19.

      Post a Reply
      • Me equivoqué en las sumas, hasta el 23 se sigue cumpliendo que los números de su fila en el triángulo son múltiplos. Como hacer todas las sumas es muy pesado y muy fácil equivocarse, también he observado que el tercer número, sin contar el 1, solo es múltiplo cuando la fila es de un primo.
        7-35 11-165 13-286 17-680 19-969 23-1771

        Post a Reply
        • Sigo avanzando, ahora ya se aplicar el binomio de Newton, y cuando m=primo da lo mismo n que utilice que el resultado siempre es múltiplo de m. Sin embargo, con los impares compuestos, el resultado no es múltiplo de m cuando n es un divisor de m.
          Por ejemplo para m=77 ,no he calculado todo el desarrollo, pero n=7 y n=11 no dan múltiplos de 77. Con m=21 pasa igual, falla n=3 y n=7.

          Post a Reply
    • En mi hoja de calculo (de IBM lotus symphony) se cumple hasta el 61 y empieza a fallar en el 67 { 7 trillones886 597 962 249 170 000/67 no da entero}[pero no se si es por capacidad de calculo con numeros grandes? (me refiero a que después de cierto número la hoja de calculo cambia los dígitos finales de un número por ceros)]

      Post a Reply
    • En mi hoja de calculo (de IBM lotus symphony) se cumple hasta el 61 y empieza a fallar en el 67 { 7 trillones886 597 962 249 170 000/67 no da entero}[pero no se si es por capacidad de calculo con numeros grandes? (me refiero a que después de cierto número la hoja de calculo cambia los dígitos finales de un número por ceros)]
      ( …. continuación)
      correspondiente a la fila 67-ésima y la columna 29-ésima y por lo tanto su valor es el del coeficiente binomial
         \binom{67}{29} = \frac{67!}{29!*(67-29)!} = \frac{67!}{29!*38!}
      = 7886597962249166160
      por contraposición al
      = 7886597962249170000 que dio mi hoja de calculo en la casilla correspondiente, lo que confirma mis sospechas sobre la maligna hoja de calculo.
      Superemoslo y verifiquemos que 7886597962249166160 / 67 es igual a 117710417347002480 que efectivamente es un entero y por lo tanto 7886597962249166160 es múltiplo de 67 y según LA CONJETURA DE Y.G., [DEL 05/04/2018 [EN MAYÚSCULAS Y CON FECHA por si nadie la había enunciado antes >> eso sí, sin premio de un millón ni nada de esas jodas >> a menos que Y.G. sea un millonario loco que (me) lo ofreciese], sigue siendo número primo (que alivio!).
      Pero volvamos a la fórmula, (teniendo en cuenta que para nuestro propósito el número f de fila, (f-ésima), coincide con el número que esta en la segunda columna, [la columna 1-+ésima] ), alegremente al 67 lo podemos llamar genéricamente f, y a la columna llamémosla c, y a la diferencia f-c llamémosla d. Para el 67 habría que demostrar que

        \binom{67}{c} = \frac{67!}{c!*(67-c)!} = \frac{67!}{c!*d!}

      es divisible entre 67, [siempre que d (y por consiguiente c) estén entre 1 y 66, (es decir, entre 1 y f-1, hablando inclusivamente, ó, entre 0 y f hablando de manera exclusiva)].

      generalizando:

      CONJETURA de Y.G. (definicion de numero primo basada en el Triángulo de un tal Pascual**)

      Todo número natural f, del 2 en adelante, es primo, si, y sólo si, para cualquier c, (natural entre 0 y f exclusivamente), se tiene que:

        \binom{f}{c} = \frac{f!}{c!*(f-c)!}  es divisible por f

      O, enunciado alternativo de la CONJETURA de Y.G (en lenguaje odioso*):

        \forall{n,p \in{ℕ} \, con  \, p>1 \wedge  \, 0<n<p ; \, {p\in{ℙ}}\Longleftrightarrow{\frac{p*p!}{n!*(p-n)!} \in{ℤ}}}

      *y despues que por que la gente "odia" las matemáticas ??

      O, (el que me gusta mas), enunciado [casi] original, de la

      CONJETURA de Y.G en lenguaje amable:

      "Hay algo más en el triángulo de Pascal con relación a los primos. El primer número después del 1 cuando es primo, todos los demás de su fila son múltiplos de él, a excepción del 1, con el resto de los números no ocurre; así por ejemplo, en la fila del 9 hay un 84 que no es múltiplo de 9. Voy a probar un poco más."

      _________________________

      Esto se me hace PARECIDO, al teorema de Wilson, enunciado alternativo:

      Para p natural del 2 en adelante , p es primo si, y sólo si, (p-1)!+1 es divisible por p

      (aunque a mi me gusta más esta enunciación del TdW:

      p es primo si, y sólo si, (p-1)!+1 / p es impar

      lcon la cual no hay que nombra "mayor que" ni "natural", ni …etc; y se constituye en el enunciado de primalidad en la fórmula más corta, veamos otros para comparar:

      p es primo si, y sólo si, tiene 2, y sólo 2, divisores

      p es primo si, y sólo si, cuando le preguntan cuántos divisores tiene, responde 2)

      y esta última autorreferente:

      p es primo, si y sólo si, el único divisor primo que tiene, es él mismo).

      Post a Reply
      •    \underbrace{\qquad  \qquad  \,  Fe  \, de  \, Erratas \qquad  \qquad  \,}

        No
        …»para CUALQUIER c, (natural entre 0 y f exclusivamente), se tiene que:»….
        Sino
        …»para TODO c, (natural entre 0 y f exclusivamente), se tiene que:» …

        Post a Reply
    •  \text{reposicion de}
        \exists{n\in{ℤ}}

      ____________________
      O, enunciado alternativo de la CONJETURA de Y.G (en lenguaje odioso*):

        \forall{n,p \in{}}   \wedge  \, p>1 \wedge  \, 0<n<p    :

        p\in{} \Longleftrightarrow{\frac{p*p!}{n!*(p-n)!} \in{}}

      ______________
       ^*  \text{ y despues que porque la gente "odia" las matematicas ??}

      Post a Reply
    • …o más bien ???:

        \forall{n,p \in{}}    \wedge \, p>1 \rightarrow{}  p\in{}  \Longleftrightarrow{\frac{p*p!}{n!*(p-n)!} \in{}}   \, \forall{\, 0<n<p}

      que.. entre otras, te tengo noticias Y.G., no es tu conjetura. Aquí [http://www.estadisticaparatodos.es/taller/triangulo/triangulo.html] lo nombran como una propiedad del Triángulo de Pas¿cual? y al final de la pagina encontraras un generador on line de TdP tipo hoja de calculo.

      Post a Reply

Trackbacks/Pingbacks

  1. Bitacoras.com - Información Bitacoras.com Valora en Bitacoras.com: En el conocidísimo triángulo de Pascal pueden encontrarse multitud de tesoros matemáticos (recopilé unos…

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Submit a Comment

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.