Calcula C(n,k) módulo un primo p.
Calcular coeficientes binomiales módulo un primo $p$ es un problema fundamental en la combinatoria aritmética. Aunque puedes calcular coeficientes pequeños con el Triángulo de Pascal o expandiendo factoriales directamente, estos métodos se vuelven imposibles de procesar o teóricamente confusos cuando $n$ y $k$ son muy grandes. La técnica central para resolver estos problemas es el Teorema de Lucas, que te da un atajo muy útil al relacionar el valor de $\binom{n}{k} \pmod{p}$ con las expansiones en base $p$ de $n$ y $k$.
Este concepto es esencial en las matemáticas de competencia porque transforma un problema combinatorio en uno de teoría de números que involucra dígitos. Te permite determinar no solo el residuo, sino también si $\binom{n}{k}$ es divisible por $p$ (lo cual pasa si y solo si el cálculo da $0 \pmod{p}$). La intuición detrás del teorema viene de la aritmética de polinomios sobre campos finitos, específicamente de la propiedad de que elevar un polinomio a la potencia de un primo $p$ se distribuye sobre los términos, algo que a menudo llaman la identidad del "Sueño del Principiante" (Freshman's Dream).
En el contexto del AIME y la USAMO, vas a usar esta técnica seguido para analizar la paridad de los coeficientes binomiales (usando $p=2$), contar el número de entradas impares en una fila del Triángulo de Pascal, o determinar residuos específicos para valores de entrada muy grandes. Te sirve como la herramienta principal antes de pasar a métodos más avanzados como el Teorema de Kummer (que determina la potencia exacta de $p$ que divide a un coeficiente binomial).
Teorema de Lucas Supón que $p$ es un número primo. Toma $n$ y $m$ como enteros no negativos con expansiones en base $p$: $$n = n_k p^k + n_{k-1} p^{k-1} + \dots + n_1 p + n_0$$ $$m = m_k p^k + m_{k-1} p^{k-1} + \dots + m_1 p + m_0$$ donde $0 \le n_i, m_i < p$ para todo $i$. Entonces: $$\binom{n}{m} \equiv \prod_{i=0}^k \binom{n_i}{m_i} \pmod{p}$$
Condición de Divisibilidad Una consecuencia directa del Teorema de Lucas es la condición de divisibilidad por $p$. Como $\binom{a}{b} = 0$ siempre que $b > a$: $$\binom{n}{m} \not\equiv 0 \pmod{p} \iff m_i \le n_i \text{ para todo } i$$ En otras palabras, $p \nmid \binom{n}{m}$ si y solo si no hay acarreos al sumar $m$ y $n-m$ en base $p$.
Identidad Polinomial (El Sueño del Principiante) El motor algebraico detrás de estos resultados es: $$(1+x)^p \equiv 1 + x^p \pmod{p}$$ De forma más general, para cualquier entero $k \ge 0$: $$(1+x)^{p^k} \equiv 1 + x^{p^k} \pmod{p}$$
Demostración del Teorema de Lucas
Usa funciones generatrices sobre el campo de enteros módulo $p$, que escribimos como $\mathbb{Z}_p[x]$.
Paso 1: El Sueño del Principiante Primero, nota que para un primo $p$, el coeficiente binomial $\binom{p}{k}$ es divisible por $p$ para todo $0 < k < p$. Por lo tanto, en la expansión $(1+x)^p = \sum_{k=0}^p \binom{p}{k}x^k$, todos los términos intermedios desaparecen módulo $p$: $$(1+x)^p \equiv 1 + x^p \pmod{p}$$ Por inducción, para cualquier entero no negativo $i$, tienes: $$(1+x)^{p^i} \equiv 1 + x^{p^i} \pmod{p}$$
Paso 2: Expandiendo $(1+x)^n$ Si escribes la expansión en base $p$ de $n$ como $n = \sum_{i=0}^k n_i p^i$, puedes examinar el polinomio $(1+x)^n$ módulo $p$: $$ (1+x)^n = (1+x)^{\sum_{i=0}^k n_i p^i} = \prod_{i=0}^k \left((1+x)^{p^i}\right)^{n_i} $$ Si aplicas la identidad del Paso 1: $$ (1+x)^n \equiv \prod_{i=0}^k (1+x^{p^i})^{n_i} \pmod{p} $$
Paso 3: Extracción de Coeficientes Ahora expande el lado derecho. Para cada término $(1+x^{p^i})^{n_i}$, la expansión binomial te da: $$ (1+x^{p^i})^{n_i} = \sum_{j=0}^{n_i} \binom{n_i}{j} (x^{p^i})^j = \sum_{j=0}^{n_i} \binom{n_i}{j} x^{j \cdot p^i} $$ Si sustituyes esto de vuelta en el producto: $$ (1+x)^n \equiv \prod_{i=0}^k \left( \sum_{j_i=0}^{n_i} \binom{n_i}{j_i} x^{j_i p^i} \right) \pmod{p} $$ El coeficiente de $x^m$ en el lado izquierdo es, por definición, $\binom{n}{m}$. En el lado derecho, formas un término $x^m$ al elegir un término $x^{j_i p^i}$ de cada factor en el producto de tal manera que los exponentes sumen $m$. Por lo tanto, debes tener: $$ m = \sum_{i=0}^k j_i p^i $$ Como $0 \le j_i \le n_i < p$, los valores $j_i$ son precisamente los dígitos $m_i$ de la expansión en base $p$ de $m$. Debido a la unicidad de la representación en base $p$, hay exactamente una forma de formar $x^m$, que corresponde a elegir $j_i = m_i$ para todo $i$.
Paso 4: Conclusión El coeficiente de $x^m$ en el lado derecho es el producto de los coeficientes que elegiste de cada suma: $$ [x^m] \text{RHS} = \prod_{i=0}^k \binom{n_i}{m_i} $$ Si igualas los coeficientes de $x^m$ en ambos lados obtienes: $$ \binom{n}{m} \equiv \prod_{i=0}^k \binom{n_i}{m_i} \pmod{p} $$ $\square$