Formule de Legendre

Définition intuitive

Combien de fois le nombre premier $p$ divise-t-il $n!$ ?

Énoncé formel

Soient $n\in\mathbb{N}^{*}$ et $p$ un nombre premier. La formule de Legendre donne la valuation $p$-adique de $n!$, laquelle vaut
$$v_p(n!)=\sum_{i=1}^{+\infty}\left\lfloor\frac{n}{p^{i}}\right\rfloor,$$la somme n’ayant qu’un nombre fini de termes non nuls, ceux d’indice $i\leqslant\log_p n$.

Preuve par double comptage. L’additivité de $v_p$ donne $v_p(n!)=\sum_{k=1}^{n}v_p(k)$, et l’on écrit chaque valuation comme un décompte : $v_p(k)=\#\{i\geqslant 1: p^{i}\mid k\}$. En échangeant l’ordre de sommation dans l’ensemble fini $S=\{(k,i): 1\leqslant k\leqslant n,\ p^{i}\mid k\}$,
$$v_p(n!)=|S|=\sum_{i\geqslant 1}\#\{k\leqslant n: p^{i}\mid k\}=\sum_{i\geqslant 1}\left\lfloor\frac{n}{p^{i}}\right\rfloor,$$les multiples de $p^{i}$ dans $\llbracket 1,n\rrbracket$ étant au nombre de $\lfloor n/p^{i}\rfloor$. $\square$

Forme condensée. En notant $s_p(n)$ la somme des chiffres de $n$ en base $p$,
$$v_p(n!)=\frac{n-s_p(n)}{p-1}.$$Elle s’obtient en écrivant $n=\sum_{j\geqslant 0}a_jp^{j}$, d’où $\lfloor n/p^{i}\rfloor=\sum_{j\geqslant i}a_jp^{j-i}$, puis en sommant sur $i$ et en reconnaissant $\sum_j a_j\frac{p^{j}-1}{p-1}$.