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 en 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 artículos de Édouard Lucas . ^[1]

Declaración

Para números enteros no negativos myn 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 en base p de myn respectivamente . Esto utiliza la convención de que si m  <  n . ${\displaystyle {\tbinom {m}{n}}=0}$

Pruebas

Hay varias formas 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 distintos valores de i . Entonces cada uno de estos ciclos se puede rotar por separado, de modo que un grupo G que es el producto cartesiano de grupos cíclicos C _{p ⁱ} actúa sobre M . Por tanto, también actúa sobre subconjuntos N de tamaño n . Dado que el número de elementos en G es una potencia de p , lo mismo ocurre con cualquiera de sus órbitas. Por lo tanto, para calcular el módulo p , solo necesitamos considerar puntos fijos de esta acción grupal. Los puntos fijos son aquellos subconjuntos N que son unión de alguno 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 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}}}$

Prueba basada en funciones generadoras.

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

Si p es primo y n es un número 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 tanto p divide . 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}}.}$

Ahora sea m un número entero no negativo y sea p un número primo. Escribe 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 prueba el teorema de Lucas.

Consecuencias

• Un coeficiente binomial es divisible por un primo p si y solo 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}}}$

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 añaden en la base p . ${\displaystyle {\tbinom {m}{n}}}$

• Davis y Webb (1990) ^[3] y Granville (1997) dan generalizaciones del teorema de Lucas para el caso de que p sea una potencia prima. ^[4]

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

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. Bien, Nathan (1947). "Coeficientes binomiales módulo primo". Mensual Matemático Estadounidense . 54 (10): 589–592. doi :10.2307/2304500. JSTOR  2304500.
3. Kenneth S. Davis, William A. Webb (1990). "Teorema de Lucas para los poderes primos". Revista europea de combinatoria . 11 (3): 229–233. doi :10.1016/S0195-6698(13)80122-9.
4. Andrés Granville (1997). "Propiedades aritméticas de los coeficientes binomiales I: coeficientes binomiales módulo de potencias primas" (PDF) . Actas de la conferencia de la Sociedad Canadiense de Matemáticas . 20 : 253–275. SEÑOR  1483922. Archivado desde el original (PDF) el 2 de febrero de 2017.
5. 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; Diputado Saikia (2012). "Una nueva prueba del teorema de Lucas" (PDF) . Apuntes 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 [matemáticas.NT].