Legendre formula for the factorial

La factorielle de $n$ est $n!=1\times 2\times 3\times \ldots \times n$. Pour compter le nombre de fois que $p$ apparaît dans la factorielle, il faut déjà compter tous les multiples de $p$ entre $1$ et $n$. Mais parmi eux, les multiples de $p^{2}$ contribuent une fois de plus ; et parmi eux, les multiples de $p^{3}$ contribuent encore une fois de plus... Et ainsi de suite jusqu’à l’infini. (En réalité, ce processus s’arrête dès que $p^{i}>n$, puisqu’alors il n’y a plus aucun multiple de $p^{i}$ entre $1$ et $n$).

Ainsi, la valuation $p$-adique de $n!$ est :
$$v_{p}(n!)=\text{nombre de multiples de }p\;+\text{nombre de multiples de }p^{2}\;+\text{nombre de multiples de } p^{3}\;+\ldots$$entre $1$ et $n$.

Or, le nombre de multiples d’un entier $k$ entre $1$ et $n$ est donné par la partie entière de $\frac{n}{k}$.

Bref, on obtient :
$$v_{p}(n!)=\left\lfloor\frac{n}{p}\right\rfloor+\left\lfloor\frac{n}{p^{2}}\right\rfloor+\left\lfloor\frac{n}{p^{3}}\right\rfloor+\ldots$$ce qui est le résultat annoncé.