Fórmula de Legendre

Teoría

La Fórmula de Legendre (que también conoces como la Fórmula de de Polignac) es un resultado fundamental en la teoría de números que sirve para determinar la mayor potencia de un primo $p$ que divide a $n!$ ($n$ factorial). En notación matemática, a este exponente lo escribes como $v_p(n!)$, que representa la valuación $p$-ádica de $n!$. Como los factoriales crecen rapidísimo, calcular $n!$ y luego factorizarlo es imposible para una $n$ grande. La Fórmula de Legendre te da un método directo y eficiente para calcular esta valuación sin tener que calcular el factorial.

Esta herramienta aparece por todos lados en las olimpiadas de matemáticas, sobre todo en problemas de divisibilidad, ceros al final de un número y aritmética modular. Por ejemplo, si quieres saber cuántos ceros tiene $n!$ al final, solo tienes que calcular $v_5(n!)$. Además, la Fórmula de Legendre es la pieza clave para analizar la factorización en primos de los coeficientes binomiales $\binom{n}{k}$, lo que te lleva directo al Teorema de Kummer, que relaciona la valuación de los coeficientes binomiales con los "acarreados" (lo que llevas) al sumar en base $p$.

La idea detrás de la fórmula es simplemente contar de forma organizada. Para encontrar el total de factores de $p$ en el producto $1 \times 2 \times \dots \times n$, primero cuentas