Teorema de Lucas

Teoría

El Teorema de Lucas es un resultado fundamental en teoría de números y combinatoria que te da un método muy eficiente para calcular coeficientes binomiales módulo un número primo $p$. Aunque calcular $\binom{m}{n}$ para valores grandes de $m$ y $n$ suele ser imposible o te da números demasiado grandes para manejarlos directamente, el Teorema de Lucas reduce el problema a calcular el producto de coeficientes binomiales de los dígitos de $m$ y $n$ en base $p$. Este teorema es súper útil en problemas de olimpiada que involucran paridad (módulo 2) o divisibilidad por primos pequeños.

El poder del teorema está en que te permite "digitalizar" el coeficiente binomial. Dice que el residuo de $\binom{m}{n}$ al dividirlo entre un primo $p$ depende solamente de los coeficientes binomiales de los dígitos correspondientes en las expansiones en base $p$ de $m$ y $n$. Si algún dígito del número de abajo $n$ es estrictamente mayor que el dígito correspondiente del número de arriba $m$, el coeficiente binomial es divisible entre $p$ (es decir, congruente a 0).

La intuición detrás del Teorema de Lucas nace del comportamiento algebraico de los polinomios en aritmética modular, específicamente de la propiedad $(1+x)^p \equiv 1+x^p \pmod p$. Si tratas la expansión binomial como un polinomio sobre el campo $\mathbb{F}_p$,