Triángulo de Pascal y números primos

Question

Cuando estaba en el instituto, me interesé mucho por la teoría numérica, en concreto por los números primos y los números prefijos. Solía pasarme la noche en vela con un montón de borradores intentando dar con una fórmula para generar/comprobar números primos. Descubrí muchas cosas por mi cuenta como $p(p + 1)/2$ es un número perfecto cuando p es un primo de Mersenne .

Estaba tan obsesionado por aquel entonces que solía hacer cálculos mentales mientras dormía, recuerdo que un día me desperté muy emocionado porque había descubierto que $2^p - 2 = 0 \pmod p$ cuando $p$ es un primo, sólo para descubrir unas semanas más tarde que Pierre de Fermat había una idea similar pero, desafortunadamente no funcionó para pseudoprimes . Yo estaba muy decepcionado en ese entonces y empecé a jugar con el Triángulo de Pascal .

Blaise Pascal, Marin Mersenne y Pierre de Fermat fueron contemporáneos y compartieron pensamientos con letras, de hecho si se piensa un poco tanto la fórmula prima de Mersenne como la prueba de primalidad de Fermat parecen estar estrechamente relacionadas con las filas del triángulo de Pascal (la suma de todos los números de la fila $n$ es $2^n$ donde el primer y el último número son $1$ de ahí el $-1$ en la fórmula de Mersenne y $-1$ o $-2$ en las pruebas de primalidad).

Codifiqué un generador de triángulos Pascal con PHP y HTML que resaltaba todos los números que eran múltiplos de un número específico y los resultados me asombraron, y hasta el día de hoy no sé por qué sucede esto y me gustaría mucho saber por qué. En lugar de intentar explicarlo, publicaré aquí las imágenes.

Ejemplo compuesto:

Un buen ejemplo:

Creo que la diferencia [entre los casos primo y compuesto] es obvia, pero si estás confundido sólo dilo e intentaré profundizar un poco más...

¿Puede alguien explicarme por qué ocurre esto?

Answer 1

No estoy convencido de que esto sea MO-apropiado, pero estoy publicando una respuesta porque lo que tendría que decir es probablemente demasiado largo para un comentario.

Ampliando el comentario de Reid. Sí, el teorema de Lucas es bonito. El teorema de Lucas es uno de los muchos resultados combinatorios que pueden considerarse como "primeros pasos hacia ". p - los números radicales". ¿Qué significa eso? Hay un valor absoluto "diferente" que puedes definir en los números racionales, que tiene muchas de las mismas propiedades que el valor absoluto habitual, pero que en otros aspectos se comporta de forma totalmente distinta. En realidad hay un número infinito de estos tipos, uno por cada primo $p$ ¡! Se llama p -valor absoluto radical, y puedes leer sobre ello en Wikipedia .

¿Qué p -Los números ádicos ayudan a sortear el siguiente obstáculo: Supongamos que queremos saber si un cociente de dos números.., $\frac{a}{b}$ es divisible por $p$ . (Supondremos por ahora que $\frac{a}{b}$ es definitivamente un número entero, aunque esto acaba no importando en absoluto. Pero la "divisibilidad" es una noción más complicada para los no enteros). Si $a$ es divisible por $p$ y $b$ no lo es, entonces es obvio que $\frac{a}{b}$ es; si $a$ no es divisible por $p$ entonces, por supuesto $\frac{a}{b}$ no lo es. Pero las cosas se ponen difíciles si ambos $a$ y $b$ son divisibles por $p$ podría ocurrir que $a$ es divisible por $p^2$ y $b$ es divisible por $p$ pero no por $p^2$ . O que $a$ es divisible por $p^{17}$ y $b$ es divisible por $p^{14}$ pero no por $p^{15}$ . Ya ves lo confuso que resulta. El p -adic absolute value codifica este tipo de información para usted.

Esto también explica por qué no trabajamos con, digamos, números de 10 enteros en matemáticas; es porque si tomas los enteros pero consideras que dos enteros son iguales si tienen el mismo resto al dividir por $n$ puedes seguir multiplicando, sumando y restando perfectamente. Entonces obtienes algo llamado anillo. Y si $n$ es primo, ¡también puedes dividir números! (Bueno, no se puede dividir por 0, o por un múltiplo del primo, que es "lo mismo que" 0. Pero esto es cierto pase lo que pase, así que no es un problema real). Pero esto no es cierto para los compuestos.

De todos modos, los patrones de los primos en el triángulo de Pascal son bastante conocidos. Busca en Google "triángulo de Pascal módulo" (sin comillas, probablemente) para encontrar más cosas. Los compuestos no se comportan tan bien, por las razones que Wikipedia y yo mencionamos brevemente, pero las potencias de los primos tienen patrones interesantes, que se pueden leer en el artículo maravillosamente titulado " El cerebro de Zaphod Beeblebrox y la quincuagésima novena fila del triángulo de Pascal ".

Espero que le sirva de ayuda.

Answer 2

El caso mod 2 está relacionado con el Triángulo de Sierpinski .

Answer 3

Al considerar la divisibilidad de los coeficientes binomiales, es muy instructivo considerar también los coeficientes q-binomiales.

Los coeficientes q-bimonales son polinomios en q definido por la fórmula ${{\textstyle a} \choose {\textstyle b}}_q = \frac{{\textstyle a}\underset{\textstyle .}q}{{\textstyle b}\underset{\textstyle .}q{\textstyle (a-b)}\underset{\textstyle .}q}$ ,
donde ${\textstyle n}\underset{\textstyle .}{\scriptstyle q}:=(1-q)(1-q^2)(1-q^3)\ldots (1-q^n)$ denota el q -factorial. Satisfacen ${{\textstyle a} \choose {\textstyle b}}_q | _ { q = 1 } = {{\textstyle a} \choose {\textstyle b}}$ .
El símbolo es una "q" con un punto debajo, para recordarnos el símbolo "!". Quizá no sea la notación más estándar, pero me parece irresistiblemente simpática. Véase aquí para una exposición más detallada, con notaciones algo más estándar.

Al igual que los números enteros pueden factorizarse en primos, los polinomios pueden factorizarse en polinomios irreducibles. Los polinomios que aparecen en la factorización de coeficientes de binomios cuánticos son los llamados polinomios ciclotómicos φ _n ( q ), de los cuales hay uno por cada número natural n . Para tu problema, el hecho relevante sobre los polinomios ciclotómicos es que φ _n (1) es fácil de calcular. Es p cuando n \= p a para algún número primo p y es 1 en caso contrario. Así que si tienes una factorización de algún coeficiente q-binomio en polinomios ciclotómicos, puedes deducir la factorización en números primos de los correspondientes coeficientes binomiales usuales introduciendo q \=0.

Ahora bien, a diferencia de lo que ocurre con los coeficientes binomiales habituales, la factorización del coeficiente q-bimonal no tiene multiplicidad: ¡no hay exponentes! Además, es mucho más fácil determinar cuándo φ _n divide ${{\textstyle a} \choose {\textstyle b}}$ que ocurre si y sólo si (resto de b modulo n ) + (resto de ( a -1) módulo n ) + 1 < n . Esta última condición corresponde a un patrón de triángulos mucho más regular que las imágenes que has publicado más arriba. Obtienes tu imagen superponiendo los distintos patrones que acabo de describir.

Answer 4

También quería dar una respuesta muy breve. Deje que $p$ sea un número primo. Es fácil ver que el coeficiente binomial $\left(p\atop n\right)$ es divisible por $p$ para $1\le n\le p-1$ . Así que el $p$ -La enésima línea tiene el siguiente aspecto $1,0,0,\ldots,0,1$ mod $p$ . Entonces, por la definición recursiva del triángulo de Pascal, un nuevo triángulo comienza a la izquierda y a la derecha (hasta que se encuentran en el medio en alguna parte). Y este proceso sigue y sigue. Probablemente la línea $\left(p^2\atop *\right)$ también es una línea con esta propiedad, etc. Esto explica la naturaleza recursiva de este fenómeno.

Answer 5

Parece que algunas personas ya han dado algunas respuestas mejores, así que mencionaré rápidamente que puede que te guste resolver problemas en ProjectEuler.net, ya que algunos de los problemas se ajustan a esta forma de pensar.

Para uno de los problemas he creado la siguiente manera de determinar el número de veces que p divide a M elija N:

M!/(N!*(M-N)!)
K(M,p)-K(N,p)-K(M-N,p)
Where K(X,p) is the number of times p divides X! and is equal to:
K(X,p)=Floor(X/p)+Floor(X/p^2)+Floor(X/p^3)+...

(Explicación rápida: Incluso para cada p^2 por debajo de X hay dos factores de p añadidos al producto, pero uno ya estaba contado en Floor(X/p), así que simplemente añadimos el extra para la nueva potencia de p)

Probablemente no sea original, pero fue divertido inventarlo.

Dan