Formule de Legendre

Soit $p$ un nombre premier et $n$ un entier naturel. La formule de Legendre donne la valuation $p$-adique de $n!$, c'est-à-dire la plus grande puissance $\nu$ telle que $p^{\nu}$ divise $n!$ : $$v_p(n!)=\sum_{k=1}^{+\infty}\Big\lfloor \frac{n}{p^k}\Big\rfloor.$$ Cette somme est en réalité finie, puisque $\Big\lfloor \frac{n}{p^k}\Big\rfloor=0$ dès que $p^k>n$.

Grâce à la formule de Legendre, on peut facilement calculer le nombre de zéros par lequel se termine $1000!$ par exemple. Pour cela, il suffit de calculer la plus grande puissance $N$ telle que $10^N|1000!$. Comme $10=2\times 5$, on obtient $N=\min(v_2(1000!),v_5(1000!))$. En utilisant la formule de Legendre, on trouve \begin{align*} v_5(1000!)&=\Big\lfloor\frac{1000}5\Big\rfloor+\Big\lfloor \frac{1000}{25}\Big\rfloor+\Big\lfloor \frac{1000}{125}\Big\rfloor+\Big\lfloor \frac{1000}{625}\Big\rfloor\\ &=249\\ v_2(1000!)&\geq \Big\lfloor\frac{1000}{2}\Big\rfloor=500. \end{align*} Ainsi, $1000!$ se termine par $249$ zéros.

La formule de Legendre a été prouvée par Adrien-Marie Legendre en 1830 dans son livre Théorie des nombres.