Hispanopedia Wiki
Articulo de referencia

Teorema de Lucas

En teoría de números , el teorema de Lucas expresa el resto de la división del coeficiente binomial. ( metro norte ) {\displaystyle {\tbinom {m}{n}}} mediante un número primo p ...

Hispanopedia WikiContenido en espanolLectura gratuita

En teoría de números , el teorema de Lucas expresa el resto de la división del coeficiente binomial.(metronorte){\displaystyle {\tbinom {m}{n}}}mediante un número primo p en términos de las expansiones en base p de los enteros m y n .

El teorema de Lucas apareció por primera vez en 1878 en artículos de Édouard Lucas . [ 1 ]

Declaración

Para enteros no negativos m y n y un primo p , se cumple la siguiente relación de congruencia :

(metronorte)≡∏i=0k(metroinortei)(modpag),{\displaystyle {\binom {m}{n}}\equiv \prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}{\pmod {p}},}

dónde

metro=metrokpagk+metrok−1pagk−1+⋯+metro1pag+metro0,{\displaystyle m=m_{k}p^{k}+m_{k-1}p^{k-1}+\cdots +m_{1}p+m_{0},}

y

norte=nortekpagk+nortek−1pagk−1+⋯+norte1pag+norte0{\displaystyle n=n_{k}p^{k}+n_{k-1}p^{k-1}+\cdots +n_{1}p+n_{0}}

son las expansiones en base p de m y n respectivamente. Esto utiliza la convención de que(metronorte)=0{\displaystyle {\tbinom {m}{n}}=0}si m  < n . 

Pruebas

Existen varias maneras de demostrar el teorema de Lucas.

Prueba combinatoria mediante una acción de grupo

Sea M un conjunto con m elementos, y dividámoslo arbitrariamente en m i ciclos de longitud p i para los distintos valores de i . Entonces, cada uno de estos ciclos puede ser rotado por separado mediante un grupo cíclico C p i , de modo que el grupo G, que es el producto cartesiano de todos estos grupos cíclicos (uno para cada ciclo), actúa sobre M. Por lo tanto, también actúa sobre el conjunto de subconjuntos N de n elementos de M , cuyo número es(metronorte){\displaystyle {\tbinom {m}{n}}}Esta es la acción grupal que analizaremos en la secuela.

Dado que el número de elementos en G es una potencia de p , lo mismo es cierto para cualquiera de sus órbitas , por el teorema del estabilizador de órbitas . Por lo tanto,(metronorte){\displaystyle {\tbinom {m}{n}}}es congruente módulo p con el número de conjuntos N cuya órbita es de tamaño 1, es decir, con el número de puntos fijos de la acción del grupo.

Dado que todos los ciclos pueden ser rotados independientemente por nuestro grupo G , los puntos fijos de la acción son aquellos subconjuntos N que son una unión de algunos de los ciclos. Esto significa que N debe constar de exactamente n i ciclos de tamaño p i para cada i , por la misma razón que el entero n tiene una representación única en base p . Por lo tanto, el número de opciones para N es exactamente ∏i=0k(metroinortei){\displaystyle \prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}}.

Demostración basada en funciones generadoras

Esta prueba se debe a Nathan Fine. [ 2 ]

Si p es un número primo y n es un entero con 1 ≤ n ≤ p − 1, entonces el numerador del coeficiente binomial

(pagnorte)=pag⋅(pag−1)⋯(pag−norte+1)norte⋅(norte−1)⋯1{\displaystyle {\binom {p}{n}}={\frac {p\cdot (p-1)\cdots (p-n+1)}{n\cdot (n-1)\cdots 1}}}

es divisible por p pero el denominador no lo es. Por lo tanto, p divide(pagnorte){\displaystyle {\tbinom {p}{n}}}Debido al teorema del binomio , esto significa que

(1+incógnita)pag≡1+incógnitapag(modpag).{\displaystyle (1+X)^{p}\equiv 1+X^{p}{\pmod {p}}.}

Continuando por inducción , tenemos para cada entero no negativo i que

(1+incógnita)pagi≡1+incógnitapagi(modpag).{\displaystyle (1+X)^{p^{i}}\equiv 1+X^{p^{i}}{\pmod {p}}.}

Ahora sea m un entero no negativo y p un número primo. Escriba m en base p , de modo quemetro=∑i=0kmetroipagi{\displaystyle m=\sum _{i=0}^{k}m_{i}p^{i}}para algún entero no negativo k y enteros m i tales que 0 ≤ m i ≤ p − 1. Entonces

∑norte=0metro(metronorte)incógnitanorte=(1+incógnita)metro=∏i=0k((1+incógnita)pagi)metroi≡∏i=0k(1+incógnitapagi)metroi=∏i=0k(∑ji=0metroi(metroiji)incógnitajipagi)=∑norte=0metro(∏i=0k(metroinortei))incógnitanorte(modpag).{\displaystyle {\begin{aligned}\sum _{n=0}^{m}{\binom {m}{n}}X^{n}&=(1+X)^{m}=\prod _{i=0}^{k}\left((1+X)^{p^{i}}\right)^{m_{i}}\\&\equiv \prod _{i=0}^{k}\left(1+X^{p^{i}}\right)^{m_{i}}\\&=\prod _{i=0}^{k}\left(\sum _{j_{i}=0}^{m_{i}}{\binom {m_{i}}{j_{i}}}X^{j_{i}p^{i}}\right)\\&=\sum _{n=0}^{m}\left(\prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}\right)X^{n}{\pmod {p}}.\end{aligned}}}

En la última igualdad utilizamos la propiedad distributiva y el hecho de que la representación de n en base p es única, donde n i es el i -ésimo dígito en la representación de n en base p . Comparando los coeficientes de X n en la primera y la última suma, obtenemos el teorema de Lucas.

Triángulo de Pascal, que muestra los coeficientes binomiales impares en negro.

Consecuencias

Una consecuencia del teorema de Lucas es que el coeficiente binomial(metronorte){\displaystyle {\tbinom {m}{n}}}es divisible por el primo p si y solo si al menos uno de los dígitos de la representación en base p de n es mayor que el dígito correspondiente de m . En particular,(metronorte){\displaystyle {\tbinom {m}{n}}}Un número es impar si y solo si las posiciones de los unos en la expansión binaria de n son un subconjunto de las posiciones de los unos en la de m . Esto da lugar a una distribución peculiar de los números impares en el triángulo de Pascal , similar al triángulo de Sierpiński , que se muestra a la derecha.

Módulos no primos

El teorema de Lucas se puede generalizar para dar una expresión para el resto cuando(metronorte){\displaystyle {\tbinom {m}{n}}}se divide por una potencia prima p k . Sin embargo, las fórmulas se vuelven más complicadas.

Si el módulo es el cuadrado de un primo p , se cumple la siguiente relación de congruencia para todo 0 ≤ s ≤ r ≤ p − 1, a ≥ 0 y b ≥ 0:

(paga+rpagb+s)≡(ab)(rs)(1+paga(Hr−Hr−s)+pagb(Hr−s−Hs))(modpag2),{\displaystyle {\binom {pa+r}{pb+s}}\equiv {\binom {a}{b}}{\binom {r}{s}}(1+pa(H_{r}-H_{rs})+pb(H_{rs}-H_{s})){\pmod {p^{2}}},}

dóndeHnorte=1+12+13+⋯+1norte{\displaystyle H_{n}=1+{\tfrac {1}{2}}+{\tfrac {1}{3}}+\cdots +{\tfrac {1}{n}}}es el n -ésimo número armónico . [ 3 ] También se dan generalizaciones del teorema de Lucas para potencias primas superiores p k por Davis y Webb (1990) [ 4 ] y Granville (1997). [ 5 ]

El teorema de Kummer afirma que el mayor entero k tal que p k divide el coeficiente binomial(metronorte){\displaystyle {\tbinom {m}{n}}}(o en otras palabras, la valoración del coeficiente binomial con respecto al primo p ) es igual al número de acarreos que ocurren cuando se suman n y m  − n en la base p . 

coeficientes q -binomiales

Existe una generalización del teorema de Lucas para los coeficientes q -binomiales . Afirma que si a , b , r , s , k son enteros, donde 0 ≤ b , s < k , entonces [ka+bkr+s]q≡(ar)[bs]qmodΦk,{\displaystyle {\begin{bmatrix}ka+b\\kr+s\end{bmatrix}}_{q}\equiv {\binom {a}{r}}{\begin{bmatrix}b\\s\end{bmatrix}}_{q}\mod {\Phi _{k}},}donde​[ka+bkr+s]q{\displaystyle {\begin{bmatrix}ka+b\\kr+s\end{bmatrix}}_{q}}y​​[bs]q{\displaystyle {\begin{bmatrix}b\\s\end{bmatrix}}_{q}}son coeficientes q -binomiales ,(ar){\displaystyle {\binom {a}{r}}}es un coeficiente binomial usual, yΦk{\displaystyle \Phi _{k}}es el k -ésimo polinomio ciclotómico (en la variable q ). [ 6 ]

Referencias

  1. ↑
  2. ↑ Fine, Nathan (1947). "Coeficientes binomiales módulo un primo". American Mathematical Monthly . 54 (10): 589– 592. doi : 10.2307/2304500 . JSTOR 2304500 . 
  3. ↑ Rowland, Eric (2022). "Teorema de Lucas módulo p 2 ". American Mathematical Monthly . 129 (9): 846– 855. arXiv : 2006.11701v3 . doi : 10.1080/00029890.2022.2038004 .
  4. ↑ Kenneth S. Davis, William A. Webb (1990). "Teorema de Lucas para potencias primas". European Journal of Combinatorics . 11 (3): 229– 233. doi : 10.1016/S0195-6698(13)80122-9 .
  5. ↑ Andrew Granville (1997). "Propiedades aritméticas de los coeficientes binomiales I: Coeficientes binomiales módulo potencias primas" (PDF) . Actas de la Conferencia de la Sociedad Matemática Canadiense . 20 : 253–275 . MR 1483922. Archivado del original (PDF) el 2 de febrero de 2017. 
  6. ^ Désarménien, Jacques (marzo de 1982). "Un Analogue des Congruences de Kummer pour les q-nombres d'Euler". Revista europea de combinatoria . 3 (1): 19– 28. doi : 10.1016/S0195-6698(82)80005-X .
  • El teorema de Lucas en PlanetMath .
  • A. Laugier; MP Saikia (2012). "Una nueva demostración del teorema de Lucas" (PDF) . Notas sobre teoría de números y matemáticas discretas . 18 (4): 1– 6. arXiv : 1301.4250 .
  • R. Meštrović (2014). "Teorema de Lucas: sus generalizaciones, extensiones y aplicaciones (1878–2014)". arXiv : 1409.3820 [ math.NT ].