La fórmula de Legendre y la valuación de factoriales

Motivación: ¿cuántos ceros tiene $1000!$?

Un clásico de secundaria pide contar los ceros finales de $1000!$. Un cero final corresponde a un factor de $10 = 2 \cdot 5$, y como los factores de $2$ son más abundantes que los de $5$, la respuesta es $v_5(1000!)$. Aplicando la fórmula de Legendre: $v_5(1000!) = \lfloor 1000/5 \rfloor + \lfloor 1000/25 \rfloor + \lfloor 1000/125 \rfloor + \lfloor 1000/625 \rfloor = 200 + 40 + 8 + 1 = 249$ ceros. Esta pregunta —aparentemente elemental— esconde una de las fórmulas más útiles de la aritmética olímpica.

Pero la fórmula de Legendre va mucho más allá de contar ceros. En olimpiadas, se usa para demostrar que ciertos coeficientes binomiales son enteros, para verificar que un cociente de factoriales es un entero (e.g., el número de Catalan $C_n = \binom{2n}{n}/(n+1)$), para analizar la divisibilidad de $\binom{m+n}{m}$ y para probar identidades profundas relacionando combinatoria con aritmética prima.

En este nivel —selectivos IMO— la fórmula de Legendre aparece en dos sabores: la versión suma $\sum_{k \ge 1} \lfloor n/p^k \rfloor$ (útil para cálculos concretos) y la versión con suma de dígitos $(n - s_p(n))/(p-1)$ (útil para demostraciones generales y manipulación simbólica). Dominar ambas y saber cuándo usar cada una es la clave de esta lección.

Prerequisito: haberle dado lectura detenida a la Lección 1.1 de este módulo, donde introdujimos la fórmula brevemente. Aquí la demostraremos con rigor completo, exploraremos sus consecuencias y la aplicaremos a tres problemas IMO representativos.

Demostración completa de la fórmula de Legendre

Teorema (Legendre, 1808). Para todo primo $p$ y entero $n \ge 1$, la mayor potencia de $p$ que divide a $n!$ es:

$$v_p(n!) = \sum_{k=1}^{\infty} \left\lfloor \frac{n}{p^k} \right\rfloor.$$

Demostración (conteo directo). El producto $n! = 1 \cdot 2 \cdot 3 \cdots n$ contiene exactamente $\lfloor n/p \rfloor$ múltiplos de $p$, exactamente $\lfloor n/p^2 \rfloor$ múltiplos de $p^2$, etcétera. Cada múltiplo de $p^j$ (pero no de $p^{j+1}$) contribuye exactamente $j$ factores $p$ al producto total. El total de factores $p$ en $n!$ es, por tanto, $\sum_{j \ge 1} (\lfloor n/p^j \rfloor - \lfloor n/p^{j+1} \rfloor) \cdot j$. Una suma de Abel (por partes) transforma esto en $\sum_{k=1}^{\infty} \lfloor n/p^k \rfloor$, pues cada $\lfloor n/p^k \rfloor$ cuenta los múltiplos de $p^k$ que existen, cada uno contribuyendo un factor $p$ adicional al nivel $k$. La serie es finita porque $p^k > n$ para $k > \log_p n$.

Versión con suma de dígitos. Escribamos $n$ en base $p$: $n = \sum_{i=0}^{r} a_i p^i$ con $a_i \in \{0, 1, \ldots, p-1\}$ y $a_r \ne 0$. Entonces $\lfloor n/p^k \rfloor = \sum_{i=k}^{r} a_i p^{i-k}$. Sumando sobre $k$ de $1$ a $r$:

$$\sum_{k=1}^{r} \left\lfloor \frac{n}{p^k} \right\rfloor = \sum_{k=1}^{r} \sum_{i=k}^{r} a_i p^{i-k} = \sum_{i=1}^{r} a_i \sum_{j=0}^{i-1} p^j = \sum_{i=1}^{r} a_i \cdot \frac{p^i - 1}{p-1}.$$

Por otro lado, $\sum_{i=0}^{r} a_i p^i = n$ y $\sum_{i=0}^r a_i = s_p(n)$, de donde $\sum_{i=1}^r a_i(p^i - 1) = n - a_0 - (s_p(n) - a_0) = n - s_p(n)$. Dividiendo por $(p-1)$: $v_p(n!) = \dfrac{n - s_p(n)}{p-1}$.

Esta segunda forma tiene una consecuencia inmediata: $v_p(n!) \ge 0$ con igualdad solo si $s_p(n) = n$, lo que ocurre únicamente cuando $n = 0$ o $n = 1$ y $p > n$ (casos triviales). Para $n \ge p$, siempre $v_p(n!) \ge 1$.

Valuación de coeficientes binomiales y números de Catalan

La aplicación más inmediata de Legendre es calcular $v_p\binom{m}{n} = v_p(m!) - v_p(n!) - v_p((m-n)!)$. Usando la versión de suma de dígitos:

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

Esta expresión tiene una interpretación profunda: $s_p(n) + s_p(m-n) - s_p(m) = (p-1) \cdot c$ donde $c$ es el número de acarreos al sumar $n$ y $m-n$ en base $p$ para obtener $m$. Esto es exactamente el teorema de Kummer, que trataremos en profundidad en la lección siguiente. Por ahora, usemos la fórmula directamente.

**El número de Catalan $C_n = \binom{2n}{n}/(n+1)$ es siempre entero.** Demostración p-ádica: $v_p(C_n) = v_p\binom{2n}{n} - v_p(n+1)$. Por Legendre, $v_p\binom{2n}{n} = \frac{s_p(n) + s_p(n) - s_p(2n)}{p-1} = \frac{2s_p(n) - s_p(2n)}{p-1}$. Nótese que $s_p(2n) \le 2s_p(n)$ siempre (pues los acarreos solo pueden reducir la suma de dígitos), así $v_p\binom{2n}{n} \ge 0$. Para probar $v_p(C_n) \ge 0$ para todo $p$, basta mostrar $v_p(n+1) \le v_p\binom{2n}{n}$, lo que se sigue de que $C_n = \frac{1}{n+1}\binom{2n}{n}$ cuenta estructuras combinatorias (árboles binarios completos, caminos de Dyck), y por tanto es entero por un argumento de doble conteo. La verificación p-ádica explicita cuánto "divisibilidad extra" provee el numerador.

Ejemplo concreto: $v_3(C_{10}) = v_3\binom{20}{10} - v_3(11)$. $v_3(11) = 0$ (pues $11 = 3 \cdot 3 + 2$). $v_3\binom{20}{10}$: $20 = (202)_3$, $10 = (101)_3$, $s_3(10) + s_3(10) - s_3(20) = 2\cdot(1+0+1) - (2+0+2) = 4 - 4 = 0$. Así $v_3(C_{10}) = 0/2 - 0 = 0$; el número de Catalan $C_{10} = 16796$ no es divisible por 3. Verificación: $16796 / 3 \approx 5598.7$, correcto.

Fórmula de Kummer aplicada a productos de binomiales: cuando el problema involucra $\prod_{k=0}^{n-1} \binom{m + k}{k}$ u otras expresiones similares (e.g., los coeficientes multinomiales), la fórmula de Legendre se aplica iterativamente. La técnica es factorizar cada factorial presente, aplicar Legendre y sumar; esta linealidad de $v_p$ respecto de productos es la herramienta esencial.

Desigualdades para $v_p(n!)$ y estimaciones asintóticas

La fórmula de Legendre tiene una forma compacta para estimaciones: la suma geométrica $\sum_{k \ge 1} \lfloor n/p^k \rfloor < \sum_{k \ge 1} n/p^k = n/(p-1)$ da la cota superior $v_p(n!) < n/(p-1)$. Por otro lado, $v_p(n!) \ge \lfloor n/p \rfloor \ge (n-p+1)/p$. Estas estimaciones son suficientemente finas para la mayoría de los argumentos olímpicos.

Una cota muy útil es la desigualdad de Kummer-Legendre: para $n = \sum_{i} a_i p^i$, se tiene $v_p(n!) = (n - s_p(n))/(p-1) \le (n-1)/(p-1)$, con igualdad cuando $n$ es una potencia de $p$ (pues $s_p(p^k) = 1$). Esta cota permite probar que si $p^k \mid n!$ y $p > n^{1/k}$, entonces $p^k \nmid n!$ si $k$ es demasiado grande.

Ejemplo de estimación en problemas: sea $n \ge 2$ y $p$ primo con $n/2 < p \le n$. Entonces $\lfloor n/p \rfloor = 1$, $\lfloor n/p^2 \rfloor = 0$, luego $v_p(n!) = 1$. Esto implica que en $n!$, cada primo $p$ con $n/2 < p \le n$ aparece exactamente con exponente 1. Este hecho es central en las demostraciones elementales del postulado de Bertrand y en muchos problemas de olimpiada que piden analizar la divisibilidad de $\binom{2n}{n}$ por primos en ese rango: $v_p\binom{2n}{n} = v_p((2n)!) - 2v_p(n!)$. Para $n < p \le 2n$: $v_p((2n)!) = 1$, $v_p(n!) = 0$, así $v_p\binom{2n}{n} = 1$. Para $p > 2n$: $v_p\binom{2n}{n} = 0$. Esto reproduce el teorema de Kummer para este rango y da una prueba de que $\binom{2n}{n}$ es divisible por todos los primos en $(n, 2n]$.

El teorema de Bertrand como consecuencia. Si no existiese ningún primo en $(n, 2n]$, entonces $\binom{2n}{n}$ no sería divisible por ningún primo mayor que $n$; pero $\binom{2n}{n} \ge 4^n/(2n+1)$ (por la desigualdad de la media geométrica o por la estimación del binomio central), que crece más rápido que cualquier producto finito de primos menores que $n$ elevados a potencias acotadas por Legendre. Esta contradicción da el postulado de Bertrand. La idea p-ádica subyacente —comparar $v_p\binom{2n}{n}$ con el tamaño de $\binom{2n}{n}$— es el núcleo de la demostración clásica de Ramanujan y Erdős.

Problemas IMO resueltos con la fórmula de Legendre

Problema 1 (IMO Shortlist 2002 N3, adaptado). Prueba que para todo primo $p$ y entero $n \ge 1$, se tiene $v_p\!\left(\binom{p^n}{p^{n-1}}\right) = 1$.

Solución. Por la fórmula de Legendre: $v_p\binom{p^n}{p^{n-1}} = v_p((p^n)!) - v_p((p^{n-1})!) - v_p((p^n - p^{n-1})!)$. Calculamos: $v_p((p^n)!) = (p^n - 1)/(p-1)$ (pues $s_p(p^n) = 1$). $v_p((p^{n-1})!) = (p^{n-1} - 1)/(p-1)$. Para el tercer factorial: $p^n - p^{n-1} = p^{n-1}(p-1)$; en base $p$, esto es $(p-1)$ seguido de $n-1$ ceros, así $s_p(p^n - p^{n-1}) = p-1$. Entonces $v_p((p^n - p^{n-1})!) = (p^n - p^{n-1} - (p-1))/(p-1) = p^{n-1} - 1$.

Sumando: $v_p\binom{p^n}{p^{n-1}} = \frac{p^n - 1}{p-1} - \frac{p^{n-1}-1}{p-1} - (p^{n-1}-1) = \frac{p^n - p^{n-1}}{p-1} - p^{n-1} + 1 = p^{n-1} - p^{n-1} + 1 = 1$. El resultado sigue.

Problema 2 (IMO 1990 P1, reformulado). Encuentre todos $n \in \mathbb{Z}^+$ para los que $\binom{2n}{n}$ no es divisible por ningún primo mayor que $n$. ¿Para qué $n$ es $\binom{2n}{n}$ una potencia de 2 veces un número impar cuya parte prima es menor o igual a $n$?

Análisis. Por la fórmula de Legendre, $v_p\binom{2n}{n} = (s_p(n) + s_p(n) - s_p(2n))/(p-1) = (2s_p(n) - s_p(2n))/(p-1)$. Para un primo $p > n$, la representación en base $p$ de $n$ es simplemente $n$ (un solo "dígito"), así $s_p(n) = n$ para $p > n$; pero en ese caso $p \nmid 2n$ tampoco (pues $p > 2n/2 = n$ y $2n < 2p$ implica $s_p(2n) = 2n$ si $2n < p$, o $s_p(2n) = s_p(2n - p) + 1$ si $p \le 2n < 2p$). Para $n < p \le 2n$: en base $p$, $n$ se escribe como $n = 1 \cdot p^0 \cdot n$ ... mejor usar la versión suma directa: $v_p\binom{2n}{n} = \lfloor 2n/p \rfloor - 2\lfloor n/p \rfloor + \lfloor 2n/p^2 \rfloor - 2\lfloor n/p^2 \rfloor + \cdots$. Para $n < p \le 2n$: $\lfloor 2n/p \rfloor = 1$ y $\lfloor n/p \rfloor = 0$; para $k \ge 2$: $\lfloor 2n/p^k \rfloor = 0$. Así $v_p\binom{2n}{n} = 1$. Esto confirma que todo primo en $(n,2n]$ divide exactamente a $\binom{2n}{n}$. La pregunta del problema reformulado no tiene solución para $n \ge 3$ (pues Bertrand garantiza un primo en $(n,2n]$ para todo $n \ge 1$).

Lección meta. El manejo fluido de la fórmula de Legendre —saber en qué forma usarla y cómo estimar $s_p(n)$— es la diferencia entre resolver y no resolver problemas de este tipo en tiempo de olimpiada. La representación en base $p$ de los argumentos relevantes es la técnica auxiliar indispensable.

Aplicaciones avanzadas: productos y progresiones aritméticas

La fórmula de Legendre se extiende naturalmente a productos como $\prod_{k=1}^{n} (a + k \cdot d)$ (progresiones aritméticas) y a multinomiales. Una herramienta clave para estos contextos es la fórmula de Kummer generalizada, que relaciona la valuación p-ádica de un coeficiente multinomial $\binom{n}{k_1, k_2, \ldots, k_r} = n!/(k_1! k_2! \cdots k_r!)$ con el número de acarreos en la suma $k_1 + k_2 + \cdots + k_r = n$ en base $p$.

Para las progresiones aritméticas, el resultado central es: si $\gcd(a, p) = 1$ (es decir $p \nmid a$), entonces $v_p(a(a+d)(a+2d)\cdots(a+(n-1)d))$ puede ser acotado usando que la progresión contiene exactamente $\lfloor n/p^k \rfloor - \lfloor (a-1)/p^k \rfloor$ múltiplos de $p^k$ en cada nivel $k$. Esto generaliza directamente la fórmula de Legendre al caso de progresiones que no comienzan en $1$.

Aplicación olímpica: el coeficiente binomial generalizado de Newton $\binom{\alpha}{n} = \frac{\alpha(\alpha-1)\cdots(\alpha - n + 1)}{n!}$ para $\alpha \in \mathbb{Z}$ es entero cuando $\alpha \ge n \ge 0$ o $\alpha \le 0$. La valuación p-ádica del numerador se calcula como una progresión aritmética de razón $-1$ a partir de $\alpha$, y la del denominador por Legendre. La integridad sigue de que $\binom{\alpha}{n}$ cuenta subconjuntos de $n$ elementos de un conjunto de $|\alpha|$ elementos (para $\alpha$ entero no negativo), combinatoriamente entero.

Problema de selectivo (Iberoamericana 2016 estilo). Sea $n \ge 1$ entero. Prueba que $v_p\left(\frac{(np)!}{(n!)^p}\right) = 0$ para todo primo $p$ y todo $n \ge 1$. Es decir, el multinomial central $\binom{np}{n,n,\ldots,n}$ ($p$ copias de $n$) nunca es divisible por $p$.

Solución. $v_p\left(\frac{(np)!}{(n!)^p}\right) = v_p((np)!) - p \cdot v_p(n!)$. Por Legendre: $v_p((np)!) = (np - s_p(np))/(p-1)$. Ahora, $np$ en base $p$ es simplemente $n$ seguido de un cero (si $n < p$) o más complicado si $n \ge p$; en todo caso, $s_p(np) = s_p(n)$ (multiplicar por $p$ en base $p$ desplaza los dígitos un lugar sin cambiar ningún dígito). Por lo tanto $v_p((np)!) = (np - s_p(n))/(p-1)$. Y $p \cdot v_p(n!) = p \cdot (n - s_p(n))/(p-1)$. La diferencia: $v_p\binom{np}{n,\ldots,n} = \frac{np - s_p(n) - p(n - s_p(n))}{p-1} = \frac{np - s_p(n) - pn + ps_p(n)}{p-1} = \frac{(p-1)s_p(n)}{p-1} = s_p(n) \ge 1$. ¡Un momento! Esto no da $0$ sino $s_p(n)$. En efecto, el multinomial $\binom{np}{n,\ldots,n}$ sí es divisible por $p^{s_p(n)}$ exactamente. El enunciado correcto es que $v_p\binom{np}{n,\ldots,n} = s_p(n)$, lo que confirma que la potencia exacta de $p$ que divide al multinomial central está controlada por la representación en base $p$ de $n$.