Teorema de Lucas

En teoría de números,o teorema de Lucas expresa o resto da división do coeficiente binomial ${\tbinom {m}{n}}$ por un número primo p en función da expansión en base p dos enteiros m e n.

Teorema

Para os enteiros non negativos m e n e un primo p, cúmprese a seguinte relación de congruencia:

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

onde

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

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

son as expansións en base p de m e n respectivamente. Utilizando a convención ${\tbinom {m}{n}}=0$ se m < n .

Proba

 

Proba baseada en funcións xeradoras

Esta proba débese a Nathan Fine.

Se p é primo e n é un enteiro con 1 ≤ n ≤ p − 1, daquela o numerador do coeficiente binomial

${\binom {p}{n}}={\frac {p\cdot (p-1)\cdots (p-n+1)}{n\cdot (n-1)\cdots 1}}$

é divisible por p mais o denominador non o é. De aquí que p divide a ${\tbinom {p}{n}}$. En termos da función xeradora ordinaria, isto significa que

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

Continuando por indución, temos para todo enteiro non negativo i que

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

Agora sexa m un enteiro non negativo, e sexa p un primo. Escribimos m en base p, $m=\sum _{i=0}^{k}m_{i}p^{i}$ para algún enteiro non negativo k e enteiros m_i con 0 ≤ m_i ≤ p-1. Daquela

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

onde no produto final, n_i é o i-ésimo díxito na representación en base p de n. Isto proba o teorema de Lucas.

Consecuencias

• Un coeficiente binomial ${\tbinom {m}{n}}$ é divisible por un primo p se e só se polo menos un dos díxitos en base p de n é maior que o correspondente de m.
• En particular, ${\tbinom {m}{n}}$ é impar se e só se os díxitos binarios (bits) na expansión binaria de n son un subconxunto dos bits de m.

Variacións e xeneralizacións

• O teorema de Kummer afirma que o maior enteiro k tal que p^k divide o coeficiente binomial ${\tbinom {m}{n}}$ (ou noutras palabras, a valoración do coeficiente binomial con respecto ao primo p) é igual ao número de carrexos que se producen cando sumamos n e m − n en base p.

• Davis e Webb (1990) e Granville (1997) ofrecen xeneralizacións do teorema de Lucas para o caso de que p sexa unha potencia prima.
• O teorema de q-Lucas é unha xeneralización para os coeficientes q-binomiais, probado por primeira vez por J. Désarménien.

Véxase tamén

Outros artigos

Teorema de Kummer.

Ligazóns externas

• Lucas's Theorem at PlanetMath.
• A. Laugier; M. P. Saikia (2012). "A new proof of Lucas' Theorem" (PDF). Notes on Number Theory and Discrete Mathematics 18 (4): 1–6. arXiv:1301.4250. 
• R. Meštrović (2014). "Lucas' theorem: its generalizations, extensions and applications (1878–2014)". arXiv:1409.3820 [math.NT].