Fórmula de Legendre

Teoría

La Fórmula de Legendre (también conocida como la Fórmula de de Polignac) es un resultado fundamental en teoría de números que determina el exponente de la mayor potencia de un primo $p$ que divide a $n!$ ($n$ factorial). A este exponente le decimos la valuación $p$-ádica de $n!$ y lo escribimos como $v_p(n!)$. Como los factoriales crecen increíblemente rápido, calcular $n!$ y luego factorizarlo es imposible computacionalmente para una $n$ grande. La Fórmula de Legendre te da un método directo y eficiente para calcular esta valuación usando solo divisiones simples y la función piso.

Esta técnica es esencial en las matemáticas de olimpiada para problemas que involucran divisibilidad, ceros al final y aritmética modular. La vas a usar seguido para determinar si un coeficiente binomial $\binom{n}{k}$ es divisible por un primo específico, o para encontrar cuántos ceros tiene un factorial al final (calculando $v_5(n!)$). La fórmula transforma un problema multiplicativo (factorizar un producto) en uno aditivo que involucra sumas de partes enteras.

La intuición detrás de la fórmula se basa en contar factores de forma sistemática. Para encontrar el número total de factores de $p$ en $n! = 1 \times 2 \times \dots \times n$, primero cuentas los múltiplos de $p$ en la secuencia (que aportan al menos un factor). Sin embargo, los múltiplos de $p^2$ aportan un factor adicional de $p$, los múltiplos de $p^3$ aportan otro más, y así sucesivamente. La Fórmula de Legendre suma estos conteos para llegar a la valuación total.

Fórmulas Clave

La Fórmula Principal Para cualquier entero positivo $n$ y primo $p$, el exponente de la mayor potencia de $p$ que divide a $n!$ está dado por: $$v_p(n!) = \sum_{k=1}^{\infty} \left\lfloor \frac{n}{p^k} \right\rfloor = \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \left\lfloor \frac{n}{p^3} \right\rfloor + \dots$$ Nota: La suma es finita porque $\lfloor n/p^k \rfloor = 0$ en cuanto $p^k > n$.

Forma Alternativa (Suma de Dígitos) Una variación muy poderosa, que suele ser útil en problemas de olimpiada, relaciona la valuación con la suma de los dígitos de $n$ cuando lo escribes en base $p$. Si $s_p(n)$ es la suma de los dígitos de $n$ en base $p$, entonces: $$v_p(n!) = \frac{n - s_p(n)}{p - 1}$$

Aplicación a Coeficientes Binomiales Usando la propiedad de que $v_p(\binom{n}{k}) = v_p(n!) - v_p(k!) - v_p((n-k)!)$, la fórmula de Legendre implica el Teorema de Kummer: $$v_p\left(\binom{n}{k}\right) = \text{número de acarreos al sumar } k \text{ y } n-k \text{ en base } p.$$

Demostración

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

Demostración: La idea es contar el número total de factores de $p$ en el producto $n! = 1 \times 2 \times 3 \times \dots \times n$.

Considera la contribución de cada entero $m \in {1, 2, \dots, n}$ al exponente total. Si la factorización en primos de $m$ contiene $p^j$ (donde $p^j \mid m$ pero $p^{j+1} \nmid m$), entonces $m$ aporta exactamente $j$ a la suma total $v_p(n!)$.

En lugar de sumar la contribución de cada número $m$ por separado, cuentas cuántos números aportan al menos 1 factor, cuántos aportan al menos 2 factores, y así sucesivamente.

1. Múltiplos de $p$: Los números en el conjunto ${1, \dots, n}$ que son divisibles entre $p$ son $p, 2p, 3p, \dots, \lfloor \frac{n}{p} \rfloor p$. Hay exactamente $\lfloor \frac{n}{p} \rfloor$ de estos números. Cada uno de ellos aporta al menos un factor de $p$ al producto.

2. Múltiplos de $p^2$: Los números divisibles entre $p^2$ son $p^2, 2p^2, \dots, \lfloor \frac{n}{p^2} \rfloor p^2$. Hay exactamente $\lfloor \frac{n}{p^2} \rfloor$ de estos números. Cada uno de ellos aporta un segundo factor de $p$. Nota que el primer factor de $p$ de estos números ya lo habías contado en el paso 1.

3. Múltiplos de $p^k$: En general, hay $\lfloor \frac{n}{p^k} \rfloor$ múltiplos de $p^k$ en la secuencia. Cada uno de ellos aporta un $k$-ésimo factor de $p$.

Ahora, considera un número específico $m$ tal que $v_p(m) = j$. Esto significa que $p^j \mid m$ y $p^{j+1} \nmid m$.

• Este número $m$ es un múltiplo de $p$, así que lo cuentas una vez en el término $\lfloor \frac{n}{p} \rfloor$.
• Este número $m$ es un múltiplo de $p^2$, así que lo cuentas una vez en el término $\lfloor \frac{n}{p^2} \rfloor$.
• ...
• Este número $m$ es un múltiplo de $p^j$, así que lo cuentas una vez en el término $\lfloor \frac{n}{p^j} \rfloor$.
• Este número $m$ NO es un múltiplo de $p^{j+1}$, así que no lo cuentas en $\lfloor \frac{n}{p^{j+1}} \rfloor$ ni en ningún término posterior.

Por lo tanto, cuentas el número $m$ exactamente $j$ veces en la suma $\sum_{k=1}^{\infty} \lfloor \frac{n}{p^k} \rfloor$. Esto coincide exactamente con el número de factores de $p$ que $m$ aporta a $n!$.

Al sumar sobre todas las $k$, obtienes el exponente total: $$v_p(n!) = \sum_{k=1}^{\infty} \left\lfloor \frac{n}{p^k} \right\rfloor$$ $\square$