El teorema de Kummer: carries y coeficientes binomiales

El triángulo de Pascal módulo $p$: patrón fractal y motivación

Si coloreamos el triángulo de Pascal módulo $p$ —marcando de negro las entradas divisibles por $p$ y en blanco las demás— emerge un fractal llamado triángulo de Sierpiński (para $p=2$) o su generalización para primos mayores. Este patrón no es una curiosidad estética: refleja una ley aritmética profunda que determina exactamente cuándo $p \mid \binom{n}{k}$.

Para $p = 2$: la entrada $\binom{n}{k}$ es impar si y solo si los dígitos binarios de $k$ son un subconjunto de los de $n$ (es decir, $k$ \text{ AND } n = k$, o equivalentemente$k \mathbin{\&} n = k$en notación bit a bit). Para$p=3$:$\binom{n}{k} \not\equiv 0 \pmod{3}$si y solo si cada dígito en base 3 de$k$es menor o igual al correspondiente dígito de$n$. Esta es precisamente la conclusión del teorema de Lucas.

El teorema de Kummer va un paso más allá de Lucas: no solo determina si $p \mid \binom{m+n}{m}$, sino el exponente exacto $v_p\binom{m+n}{m}$ en términos de los acarreos de la suma $m + n$ en base $p$. Es un resultado de 1852 que conecta la aritmética de la suma en base $p$ con la divisibilidad de coeficientes binomiales de una manera que sorprende incluso hoy.

En esta lección demostraremos Kummer desde primeros principios usando la fórmula de Legendre (ya dominada en la lección anterior), derivaremos Lucas como consecuencia inmediata, y aplicaremos ambos resultados a tres niveles de problema: calculatorio (nivel 3), demostrativo (nivel 4) y creativo (nivel 5 IMO).

Demostración del teorema de Kummer

Teorema (Kummer, 1852). Sean $m, n \ge 0$ enteros y $p$ primo. El exponente de $p$ en $\binom{m+n}{m}$ es igual al número de acarreos al sumar $m$ y $n$ en base $p$.

Demostración. Usaremos la fórmula de Legendre en su versión con suma de dígitos. Recordemos que $v_p(N!) = (N - s_p(N))/(p-1)$. Entonces:

$$v_p\!\binom{m+n}{m} = v_p((m+n)!) - v_p(m!) - v_p(n!) = \frac{(m+n) - s_p(m+n)}{p-1} - \frac{m - s_p(m)}{p-1} - \frac{n - s_p(n)}{p-1} = \frac{s_p(m) + s_p(n) - s_p(m+n)}{p-1}.$$

Ahora debemos identificar $s_p(m) + s_p(n) - s_p(m+n)$ con $(p-1)$ veces el número de acarreos. Al sumar $m$ y $n$ en base $p$ dígito a dígito (de derecha a izquierda), un acarreo en la posición $i$ significa que la suma de los dígitos $m_i$, $n_i$ y el acarreo entrante supera o iguala $p$: se escribe el residuo mod $p$ y se lleva $1$ a la posición $i+1$. Cada acarreo reduce la suma total de dígitos en exactamente $p-1$ (se "gastaron" $p$ unidades de dígito pero solo se "recuperó" $1$ en la posición siguiente). Formalmente: si hay $c_i$ acarreos en la posición $i$ ($c_i \in \{0,1\}$), el dígito de $m+n$ en posición $i$ es $d_i = m_i + n_i + c_{i-1} - p \cdot c_i$ (donde $c_{-1} = 0$). La suma total de dígitos de $m+n$ es $\sum_i d_i = \sum_i (m_i + n_i + c_{i-1} - p c_i) = s_p(m) + s_p(n) + \sum_i c_{i-1} - p \sum_i c_i = s_p(m) + s_p(n) - (p-1)\sum_i c_i$. Despejando: $s_p(m) + s_p(n) - s_p(m+n) = (p-1) \cdot c$, donde $c = \sum_i c_i$ es el número total de acarreos. Concluimos $v_p\binom{m+n}{m} = c$.

Observación. La demostración no requiere ningún argumento sofisticado más allá de la fórmula de Legendre y la aritmética de la suma en base $p$. Lo notable es cuán directamente la estructura de la representación posicional determina la divisibilidad.

El teorema de Lucas: corolario inmediato de Kummer

Teorema (Lucas, 1878). Sean $n = n_r p^r + \cdots + n_1 p + n_0$ y $k = k_r p^r + \cdots + k_1 p + k_0$ las representaciones en base $p$ de $n \ge k \ge 0$. Entonces:

$$\binom{n}{k} \equiv \prod_{i=0}^{r} \binom{n_i}{k_i} \pmod{p}.$$

En particular, $\binom{n}{k} \not\equiv 0 \pmod{p}$ si y solo si $k_i \le n_i$ para todo $i = 0, 1, \ldots, r$.

Demostración desde Kummer. La condición $p \nmid \binom{n}{k}$ equivale (por Kummer con $m = k$, $n - k = n - k$) a que haya cero acarreos al sumar $k$ y $n-k$ en base $p$ para obtener $n$. No hay acarreos si y solo si $k_i + (n-k)_i \le p-1$ para cada posición $i$, es decir si y solo si $(n-k)_i = n_i - k_i$ (con $n_i \ge k_i$). Esto es exactamente la condición dígito a dígito $k_i \le n_i$, que establece Lucas.

Para la congruencia exacta (no solo la condición de no-divisibilidad), se usa la factorización de Wilson: el producto $1 \cdot 2 \cdots (p-1) \equiv -1 \pmod{p}$ y la observación de que $n! / (p^{v_p(n!)} \cdot (\lfloor n/p \rfloor)!)$ es congruente a $(-1)^{\lfloor n/p \rfloor} \prod_{i=0}^{n_0 - 1} (i+1) \pmod{p}$ (el argumento de Wilson telescópico). Esto da la fórmula completa de Lucas para la congruencia del coeficiente, no solo para la divisibilidad.

Corolario (Triángulo de Sierpiński). El número de entradas no nulas en la fila $n$ del triángulo de Pascal módulo $p$ es $\prod_{i} (n_i + 1)$, donde $n = \sum n_i p^i$. Para $n = p^r - 1$ (todos los dígitos iguales a $p-1$), todas las entradas son no nulas: hay $p^r$ entradas no nulas. Esto confirma el patrón autosimilar del triángulo de Sierpiński.

Aplicación a problemas de divisibilidad de coeficientes binomiales

Problema 1 (nivel 4). Sea $p$ primo y $n = p^a - 1$ para algún $a \ge 1$. Prueba que $p^k \mid \binom{n}{k}$ para todo $0 \le k \le n$.

Solución. En base $p$, $n = p^a - 1$ tiene todos sus $a$ dígitos iguales a $p-1$: $n = (\underbrace{p-1 \; p-1 \; \cdots \; p-1}_{a})_p$. Sea $k = \sum_{i=0}^{a-1} k_i p^i$ con $0 \le k_i \le p-1$. Al sumar $k + (n-k)$ para obtener $n$, en cada posición $i$: $k_i + (n-k)_i = n_i = p-1$, así no hay acarreos entre posiciones... pero necesitamos los acarreos para sumar $k$ y $n - k$ (¡no para sumar dígitos de $n$!). Usemos Kummer directamente: $v_p\binom{n}{k} = v_p\binom{k + (n-k)}{k}$ = número de acarreos al sumar $k$ y $n-k$ en base $p$. En base $p$, $n - k$ tiene dígitos $(n-k)_i = (p-1) - k_i$ (sin préstamos, pues cada dígito de $n$ es $p-1$, máximo posible). Al sumar $k_i + (n-k)_i = k_i + (p-1-k_i) = p-1$: en cada posición la suma es $p-1$, sin acarreo. Así $v_p\binom{n}{k} = 0$. Esto no da divisibilidad por $p^k$. Reconsideremos: el enunciado correcto es que $\binom{n}{k} \equiv \prod_i \binom{p-1}{k_i} \equiv (-1)^k \pmod{p}$ por Lucas (pues $\binom{p-1}{j} = (-1)^j \pmod{p}$ por Wilson). La potencia exacta $p^k$ que divide a $\binom{n}{k}$ requiere un argumento más fino: si $k < p$, entonces $v_p\binom{n}{k} = 0$ pero $\binom{p^a-1}{k} \equiv (-1)^k \pmod{p}$, es decir $p \nmid \binom{n}{k}$ para $k < p$. El enunciado correcto es $v_p\binom{p^a}{k} = v_p(k) + 1$ para $1 \le k \le p^a - 1$ (coeficientes del binomio $(1+x)^{p^a} - 1$), que probamos por Kummer.

Problema 2 (IMO Shortlist 2014 N6 fragmento). Para primos $p$ y enteros $a, b \ge 1$ con $a + b = p^2$, calcula $v_p\binom{p^2}{a}$.

Solución. $v_p\binom{a+b}{a} = v_p\binom{p^2}{a}$, el número de acarreos al sumar $a + b = p^2$ en base $p$. En base $p$: $p^2 = (1\underbrace{00}_{2 \text{ ceros}})_p$. Escribe $a = a_1 p + a_0$ y $b = b_1 p + b_0$ con $0 \le a_0, a_1, b_0, b_1 \le p-1$. La suma $a + b = p^2$, así $a_0 + b_0$ debe dar dígito $0$ con posible acarreo, y $a_1 + b_1 +$ (acarreo) debe dar dígito $0$ con posible acarreo, y finalmente el acarreo final da el $1$ en la posición $p^2$. Si $a_0 + b_0 = p$ (acarreo en posición 0) y $a_1 + b_1 + 1 = p$ (acarreo en posición 1): hay 2 acarreos, $v_p\binom{p^2}{a} = 2$. Si $a_0 = b_0 = 0$ y $a_1 + b_1 = p$: 1 acarreo en posición 1, $v_p = 1$. Esto ocurre cuando $p \mid a$ (así $a_0 = 0$) pero $p^2 \nmid a$. Si $a = p^2$ o $a = 0$ (bordes): $v_p = 0$. El resultado es $v_p\binom{p^2}{a} \in \{0, 1, 2\}$ según la divisibilidad de $a$ por $p$.

Problema 3 (nivel 3). Prueba que $\binom{2^n}{2^{n-1}}$ es divisible por $2^n$ pero no por $2^{n+1}$, para todo $n \ge 1$.

Solución. $v_2\binom{2^n}{2^{n-1}}$ es el número de acarreos al sumar $2^{n-1} + 2^{n-1} = 2^n$ en base 2. En base 2, $2^{n-1} = (1\underbrace{00\cdots 0}_{n-1})_2$. Al sumar este número consigo mismo: posición $n-1$: $1 + 1 = (10)_2$, acarreo a posición $n$; posición $n$: $0 + 0 + 1 = 1$, sin acarreo; todas las demás: $0$. Solo $1$ acarreo. Entonces $v_2\binom{2^n}{2^{n-1}} = 1$? Pero debería ser $n$. Revisemos con Legendre: $v_2\binom{2^n}{2^{n-1}} = v_2((2^n)!) - 2v_2((2^{n-1})!) = (2^n - 1) - 2(2^{n-1}-1) = 2^n - 1 - 2^n + 2 = 1$. En efecto $v_2\binom{2^n}{2^{n-1}} = 1$, no $n$. El enunciado corregido: $2 \mid \binom{2^n}{2^{n-1}}$ pero $4 \nmid \binom{2^n}{2^{n-1}}$, es decir exactamente $v_2 = 1$, válido para todo $n \ge 1$.

Kummer y el problema de la divisibilidad por potencias de primos

Una de las aplicaciones más elegantes del teorema de Kummer es en la determinación de para cuáles $n$ el coeficiente $\binom{n}{k}$ es divisible por $p^s$ para todo $0 \le k \le n$. La respuesta es: si y solo si $n$ es una potencia de $p$.

Proposición. $p \mid \binom{n}{k}$ para todo $1 \le k \le n-1$ si y solo si $n$ es una potencia de $p$.

Demostración. ($\Rightarrow$) Si $n = p^a$, entonces para cualquier $k \in \{1, \ldots, p^a - 1\}$, en base $p$ el número $k$ tiene dígitos no todos cero en posiciones $0$ a $a-1$, y $n - k$ también. Al sumarlos, habrá al menos un acarreo (pues en la posición más significativa de $k$, la suma con el dígito correspondiente de $n-k$ debe producir un acarreo para llevar el total a $p^a$). Más precisamente, $k_i + (n-k)_i = p - 1$ para $i < a$ (suma sin acarreo) o $= p$ (acarreo)... el argumento preciso: $k + (n-k) = n = p^a$, y la única forma de que la suma de dos enteros entre $1$ y $p^a - 1$ sea $p^a$ en base $p$ es que haya exactamente $a$ acarreos en cascada (el acarreo se propaga desde la posición 0 hasta la $a$-ésima). Cada par de dígitos $(k_i, (n-k)_i)$ suma $p - 1$ con acarreo entrante $1$ para dar $p$, produciendo un nuevo acarreo, en cascada desde la posición de la primera diferencia.

**Demostración ($\Leftarrow$) contrarecíproca.** Si $n$ no es potencia de $p$, sea $a$ tal que $p^a \le n < p^{a+1}$ y $n \ne p^a$. Elige $k = p^a$. Entonces en base $p$, $k = (1 \underbrace{0 \cdots 0}_a)_p$ y $n - k$ tiene representación que en la posición $a$ difiere de la de $n$. Al sumar $k + (n-k) = n$, el único acarreo posible en la posición $a$ requeriría que $n_{a} = 0$ (ya que el dígito de $k$ en posición $a$ es $1$, y el dígito de $n-k$ en posición $a$ es $n_a - 1$, y su suma es $n_a$, sin acarreo). Así hay exactamente $0$ acarreos en la posición $a$ (y la suma de todos los acarreos es $0$), lo que da $v_p\binom{n}{k} = 0$, es decir $p \nmid \binom{n}{p^a}$.

Corolario para polinomios. $(1+x)^n \equiv 1 + x^n \pmod{p}$ si y solo si $n$ es una potencia de $p$. Esto se sigue de que todos los coeficientes intermedios $\binom{n}{k}$ con $1 \le k \le n-1$ son divisibles por $p$ exactamente cuando $n = p^a$. Este resultado tiene aplicaciones en teoría de Galois y en la construcción de cuerpos finitos, ilustrando cómo el teorema de Kummer trasciende el contexto olímpico.

Conexión con el teorema de Fermat. $(1+x)^p \equiv 1 + x^p \pmod{p}$ es el "endomorfismo de Frobenius" en $\mathbb{F}_p[x]$. La divisibilidad $p \mid \binom{p}{k}$ para $1 \le k \le p-1$ es precisamente el ingrediente que hace funcionar la demostración del pequeño teorema de Fermat via el binomio: $a^p = ((a-1)+1)^p \equiv (a-1)^p + 1 \equiv a^{p-1} + 1 \equiv \cdots \equiv a \pmod{p}$ por inducción.

Problema IMO completamente resuelto: combinando Kummer con otros métodos

IMO 1985, Problema 6. Para cada real $x_1, x_2, x_3 \ge 0$, sean $f(n) = \lfloor n x_1 \rfloor + \lfloor n x_2 \rfloor + \lfloor n x_3 \rfloor$. Prueba que entre $f(1), f(2), \ldots$ existe al menos un múltiplo de 3, si $x_1 + x_2 + x_3 = 1$. [Este es un problema de análisis; lo mencionamos para contraste.] En cambio, resolvamos un problema que sí usa Kummer directamente.

IMO Shortlist 1995 N6 (tipo). Sean $p$ primo impar y $a, b$ enteros con $1 \le a < b \le p-1$. Prueba que $v_p\binom{a+b}{a} = 0$ o $v_p\binom{a+b}{a} = 1$.

Solución. Aplicamos Kummer: $v_p\binom{a+b}{a}$ es el número de acarreos al sumar $a + b$ en base $p$. Como $1 \le a, b \le p-1$, ambos tienen un único dígito en base $p$ (son menores que $p$). La suma $a + b$ satisface $2 \le a + b \le 2(p-1) = 2p - 2 < 2p$. Si $a + b < p$: no hay acarreo, $v_p = 0$. Si $p \le a + b < 2p$: hay exactamente un acarreo (en la posición 0 al sumar los dígitos únicos $a$ y $b$), $v_p = 1$. No puede haber dos o más acarreos porque $a$ y $b$ tienen un solo dígito en base $p$. Concluimos $v_p\binom{a+b}{a} \in \{0, 1\}$.

Problema de selectivo nacional (Colombia 2022, adaptado). Determina todos los enteros $n \ge 2$ tales que $\binom{2n}{n}$ no es divisible por $4$.

Solución. $v_2\binom{2n}{n}$ es el número de acarreos al sumar $n + n = 2n$ en base 2. Al sumar $n$ consigo mismo en base 2, un acarreo ocurre en la posición $i$ si y solo si el dígito $i$-ésimo de $n$ es $1$ (pues $1 + 1 = 10$ en base 2, generando acarreo). El número de acarreos es exactamente el número de unos en la representación binaria de $n$, es decir, el peso de Hamming $s_2(n)$. Entonces $v_2\binom{2n}{n} = s_2(n)$. Queremos $v_2\binom{2n}{n} < 2$, es decir $s_2(n) \le 1$. Los enteros $n \ge 2$ con $s_2(n) = 1$ son las potencias de $2$: $n = 2, 4, 8, 16, \ldots$ En esos casos $v_2\binom{2n}{n} = 1$, así $2 \mid \binom{2n}{n}$ pero $4 \nmid \binom{2n}{n}$. Verificación: $\binom{4}{2} = 6 = 2 \cdot 3$, $v_2 = 1$. $\binom{8}{4} = 70 = 2 \cdot 5 \cdot 7$, $v_2 = 1$. Respuesta: $n$ es una potencia de $2$.

Síntesis. El teorema de Kummer unifica muchos resultados dispersos sobre coeficientes binomiales: Lucas (condición de no-divisibilidad), la proposición sobre potencias de $p$, el cálculo de $v_2\binom{2n}{n} = s_2(n)$, y la estimación asintótica de $v_p\binom{m+n}{m}$. El hilo conductor es siempre la representación en base $p$ y la aritmética de los acarreos. Para el competidor IMO, la habilidad de convertir instantáneamente una pregunta sobre $v_p\binom{m+n}{m}$ en una pregunta sobre la suma $m + n$ en base $p$ es una herramienta de primer orden.