Teorema de Kummer

Teoría

El Teorema de Kummer te da el exponente exacto de la mayor potencia de un primo $p$ que divide a un coeficiente binomial. Específicamente, para enteros $m, n \ge 0$ y un primo $p$, la valuación $p$-ádica de $\binom{m+n}{m}$ es igual al número de "acarreos" realizados al sumar $m$ y $n$ en base $p$. Este teorema te sirve como un puente entre las propiedades aritméticas de los coeficientes binomiales y la estructura digital de los enteros en bases primas.

Este teorema es una herramienta fundamental en competencias de teoría de números, sobre todo para problemas que involucran la divisibilidad de cantidades combinatorias. Te permite determinar la divisibilidad sin tener que calcular factoriales explícitamente, los cuales crecen demasiado rápido como para manejarlos directamente. Se usa seguido para demostrar propiedades como la paridad de los coeficientes binomiales (relacionado con el Teorema de Lucas) o para contar cuántos coeficientes binomiales en una fila son divisibles por un primo específico.

La intuición detrás del teorema se basa en la Fórmula de Legendre, que relaciona la valuación de un factorial $n!$ con la suma de los dígitos de $n$ en base $p$. Como un coeficiente binomial es una razón de factoriales, su valuación depende del cambio en la suma de los dígitos al sumar los componentes. En la aritmética de base $p$, la suma de los dígitos disminuye exactamente cuando ocurre un acarreo (agrupando $p$ unidades en $1$ unidad de la siguiente potencia mayor), lo que te da el vínculo directo entre la valuación y los acarreos.

Fórmulas Clave

Teorema de Kummer Toma un primo $p$ y enteros $m, n$ no negativos. El exponente de la mayor potencia de $p$ que divide a $\binom{m+n}{m}$ está dado por: $$v_p\left(\binom{m+n}{m}\right) = \text{número de acarreos al sumar } m \text{ y } n \text{ en base } p.$$

Fórmula de Legendre (Prerrequisito) Para demostrar el Teorema de Kummer, usa la Fórmula de Legendre para la valuación $p$-ádica de los factoriales: $$v_p(n!) = \frac{n - S_p(n)}{p-1}$$ donde $S_p(n)$ es la suma de los dígitos de $n$ al escribirlo en base $p$.

Forma Alternativa Si tomas $N = m+n$ y $k = m$, el teorema se aplica a $\binom{N}{k}$. La valuación $v_p\binom{N}{k}$ es igual al número de acarreos al sumar $k$ y $N-k$ en base $p$.

Demostración

La demostración del Teorema de Kummer se hace usando la Fórmula de Legendre.

Paso 1: Expresa la valuación usando factoriales Por definición, $\binom{m+n}{m} = \frac{(m+n)!}{m!n!}$. Usando la propiedad de que $v_p(xy/z) = v_p(x) + v_p(y) - v_p(z)$, puedes escribir: $$v_p\left(\binom{m+n}{m}\right) = v_p((m+n)!) - v_p(m!) - v_p(n!)$$

Paso 2: Aplica la Fórmula de Legendre Sustituye la Fórmula de Legendre $v_p(x!) = \frac{x - S_p(x)}{p-1}$ en la ecuación de arriba: $$v_p\left(\binom{m+n}{m}\right) = \frac{(m+n) - S_p(m+n)}{p-1} - \frac{m - S_p(m)}{p-1} - \frac{n - S_p(n)}{p-1}$$

Paso 3: Simplifica la expresión Combina las fracciones. Nota que los términos lineales $(m+n) - m - n$ se cancelan y dan cero: $$\begin{aligned} v_p\left(\binom{m+n}{m}\right) &= \frac{(m+n) - m - n - S_p(m+n) + S_p(m) + S_p(n)}{p-1} \ &= \frac{S_p(m) + S_p(n) - S_p(m+n)}{p-1} \end{aligned}$$

Paso 4: Analiza la suma en base $p$ Toma las expansiones en base $p$ de $m$ y $n$ como $m = \sum_{i=0}^k a_i p^i$ y $n = \sum_{i=0}^k b_i p^i$, donde $0 \le a_i, b_i < p$. Define $c_i$ como el acarreo generado en la posición $i$ (que se pasa a la posición $i+1$) al sumar $m$ y $n$. Toma $c_0 = 0$. El dígito en la posición $i$ de la suma $m+n$, que puedes llamar $s_i$, cumple la relación: $$a_i + b_i + c_i = s_i + c_{i+1}p$$ Aquí, $c_{i+1}$ es o bien 0 o bien 1.

Paso 5: Relaciona las sumas de dígitos con los acarreos Suma la relación $a_i + b_i + c_i = s_i + c_{i+1}p$ sobre todas las posiciones $i$: $$\sum a_i + \sum b_i + \sum c_i = \sum s_i + p \sum c_{i+1}$$ Por definición, $\sum a_i = S_p(m)$, $\sum b_i = S_p(n)$ y $\sum s_i = S_p(m+n)$. También nota que $\sum c_{i+1} = \sum c_i$ (ya que la suma es sobre todos los acarreos distintos de cero). Si $C = \sum c_i$ es el número total de acarreos, la ecuación se convierte en: $$S_p(m) + S_p(n) + C = S_p(m+n) + pC$$ Reacomoda los términos para aislar la diferencia de la suma de dígitos: $$S_p(m) + S_p(n) - S_p(m+n) = pC - C = (p-1)C$$

Paso 6: Conclusión Sustituye este resultado de vuelta en la ecuación del Paso 3: $$v_p\left(\binom{m+n}{m}\right) = \frac{(p-1)C}{p-1} = C$$ Así, la valuación es exactamente igual a $C$, el número total de acarreos. $\square$