Teorema de Lucas

En teoría de números,o teorema de Lucas expresa o resto da división do coeficiente binomial $(\binom{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}}) (\mod p),

onde

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

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

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

Un coeficiente binomial $(\binom{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, $(\binom{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.

O teorema de Kummer afirma que o maior enteiro k tal que p^k divide o coeficiente binomial $(\binom{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) ^[1] e Granville (1997)^[2] 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. ^[3]