Teorema de Lucas

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

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

Declaración

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

${\displaystyle {\binom {m}{n}}\equiv \prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}{\pmod {p}},}$

dónde

${\displaystyle m=m_{k}p^{k}+m_{k-1}p^{k-1}+\cdots +m_{1}p+m_{0},}$

y

${\displaystyle n=n_{k}p^{k}+n_{k-1}p^{k-1}+\cdots +n_{1}p+n_{0}}$

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

Pruebas

Hay varias maneras de demostrar el teorema de Lucas.

Prueba combinatoria

Sea M un conjunto con m elementos, y divídalo en m _i ciclos de longitud p ⁱ para los diversos valores de i . Entonces cada uno de estos ciclos puede rotarse por separado, de modo que un grupo G que es el producto cartesiano de grupos cíclicos C _{p ⁱ} actúa sobre M . Por lo tanto, también actúa sobre subconjuntos N de tamaño n . Como el número de elementos en G es una potencia de p , lo mismo es cierto para cualquiera de sus órbitas. Por lo tanto, para calcular el módulo p , solo necesitamos considerar puntos fijos de esta acción de grupo. Los puntos fijos son aquellos subconjuntos N que son una unión de algunos de los ciclos. Más precisamente, se puede demostrar por inducción sobre k - i , que N debe tener exactamente n _i ciclos de tamaño p ⁱ . Por lo tanto, el número de opciones para N es exactamente . ${\displaystyle {\tbinom {m}{n}}}$ ${\displaystyle \prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}{\pmod {p}}}$

Demostración basada en funciones generadoras

Esta prueba se debe a Nathan Fine. ^[2]

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

${\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 a . En términos de funciones generadoras ordinarias, esto significa que ${\displaystyle {\tbinom {p}{n}}}$

${\displaystyle (1+X)^{p}\equiv 1+X^{p}{\pmod {p}}.}$

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

${\displaystyle (1+X)^{p^{i}}\equiv 1+X^{p^{i}}{\pmod {p}}.}$

Sea ahora m un entero no negativo y sea p un primo. Escriba m en base p , de modo que para algún entero no negativo k y enteros m _i con 0 ≤ m _i ≤ p -1. Entonces ${\displaystyle m=\sum _{i=0}^{k}m_{i}p^{i}}$

${\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)\\&=\prod _{i=0}^{k}\left(\sum _{j_{i}=0}^{p-1}{\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}}}$

como la representación de n en base p es única y en el producto final, n _i es el i- ésimo dígito en la representación de n en base p . Esto demuestra el teorema de Lucas.

Consecuencias

• Un coeficiente binomial es divisible por un primo p si y sólo si al menos uno de los dígitos de la base p de n es mayor que el dígito correspondiente de m . ${\displaystyle {\tbinom {m}{n}}}$
• En particular, es impar si y sólo si los dígitos binarios ( bits ) en la expansión binaria de n son un subconjunto de los bits de m . ${\displaystyle {\tbinom {m}{n}}}$

Módulos no primos

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

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

${\displaystyle {\binom {pa+r}{pb+s}}\equiv {\binom {a}{b}}{\binom {r}{s}}(1+pa(H_{r}-H_{r-s})+pb(H_{r-s}-H_{s})){\pmod {p^{2}}},}$

donde es el n ^-ésimo número armónico . ^[3] ${\displaystyle H_{n}=1+{\tfrac {1}{2}}+{\tfrac {1}{3}}+\cdots +{\tfrac {1}{n}}}$

^{Davis y Webb (1990) [4]} y Granville (1997) también ofrecen generalizaciones del teorema de Lucas para potencias primos superiores p ^{k . [5]}

Variaciones y generalizaciones

• El teorema de Kummer afirma que el mayor entero k tal que p ^k divide el coeficiente binomial (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 n y m  −  n se suman en la base p . ${\displaystyle {\tbinom {m}{n}}}$

• El teorema q -Lucas es una generalización de los coeficientes q -binomiales, demostrado por primera vez por J. Désarménien. ^[6]

Referencias

1. • Édouard Lucas (1878). "Teoría de las funciones numéricas simples y periódicas". Revista Estadounidense de Matemáticas . 1 (2): 184-196. doi :10.2307/2369308. JSTOR  2369308. SEÑOR  1505161.(parte 1);
   • Édouard Lucas (1878). "Teoría de las funciones numéricas simples y periódicas". Revista Estadounidense de Matemáticas . 1 (3): 197–240. doi :10.2307/2369311. JSTOR  2369311. SEÑOR  1505164.(parte 2);
   • Édouard Lucas (1878). "Teoría de las funciones numéricas simples y periódicas". Revista Estadounidense de Matemáticas . 1 (4): 289–321. doi :10.2307/2369373. JSTOR  2369373. SEÑOR  1505176.(parte 3)
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 (21 de junio de 2020). "Teorema de Lucas módulo p ² ". arXiv : 2006.11701 [math.NT].
4. Kenneth S. Davis, William A. Webb (1990). "Teorema de Lucas para potencias primos". Revista Europea de Combinatoria . 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 primos" (PDF) . Actas de la conferencia de la Sociedad Matemática Canadiense . 20 : 253–275. MR  1483922. Archivado desde el 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.

Enlaces externos

• Teorema de Lucas en PlanetMath .
• A. Laugier; MP Saikia (2012). "Una nueva prueba 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].