Formule de Legendre

Adrien-Marie Legendre a publié et démontré cette formule dans son livre de théorie des nombres en 1830[2]. Elle porte aussi parfois le nom d'Alphonse de Polignac[3].

On a également la relation de récurrence[3] : ${\displaystyle v_{p}(n!)=\lfloor n/p\rfloor +v_{p}(\lfloor n/p\rfloor$ !)} permettant un calcul récursif très simple de ${\displaystyle v_{p}(n!)}$.

Par exemple, par combien de zéros se termine (en) le nombre ${\displaystyle 1000!}$ ? ${\displaystyle v_{10}(1000!)=\min(v_{2}(1000!),v_{5}(1000!))=v_{5}(1000!)=\lfloor 1000/5\rfloor +v_{5}(\lfloor 1000/5\rfloor$ !)=200+v_{5}(200!)=240+8+1=249} .

Le nombre ${\displaystyle 1000!}$ se termine donc par ${\displaystyle 249}$ zéros.

• 

  En rouge, courbe de ${\displaystyle v_{5}(n!)}$, nombre de zéros terminant ${\displaystyle n!}$ en fonction de ${\displaystyle n}$. En vert le majorant ${\displaystyle (n-1)/4}$, en bleu le minorant ${\displaystyle n/4-N_{5}(n)}$. Rouge=vert pour ${\displaystyle n=5,25,125,...}$ , rouge = bleu pour ${\displaystyle n=4,24,124,...}$.
  Pour ${\displaystyle n}$ fixé, cette formule montre que l'application ${\displaystyle p\mapsto v_{p}(n!)}$ est décroissante, c'est-à-dire que toute factorielle est un produit de primorielles.
• Comme ${\displaystyle s_{p}(n)=o(n)}$, ${\displaystyle v_{p}(n!)\sim {\frac {n}{p-1}}}$ ; par exemple, ${\displaystyle n!}$ se termine par environ ${\displaystyle n/4}$ zéros.
• Plus précisément, comme ${\displaystyle 1\leqslant s_{p}(n)\leqslant (p-1)N_{p}(n)}$ où ${\displaystyle N_{p}(n)=\lfloor \log _{p}(n)\rfloor +1}$ est le nombre de chiffres de n en base p, on a l'encadrement : ${\displaystyle {n \over {p-1}}-N_{p}(n)\leqslant v_{p}(n!)\leqslant {{n-1} \over {p-1}}}$, avec égalité à droite si et seulement si ${\displaystyle n}$ est une puissance de ${\displaystyle p}$ et égalité à gauche si et seulement si ${\displaystyle n}$ est une puissance de ${\displaystyle p}$ moins un.
• Un entier ${\displaystyle n>0}$ vérifie ${\displaystyle 2^{n-1}\mid n!}$ si et seulement si ${\displaystyle n}$ est une puissance de 2. En effet, ${\displaystyle 2^{n-1}\mid n!\Leftrightarrow v_{2}(n!)\geqslant n-1\Leftrightarrow n-s_{2}(n)\geqslant n-1\Leftrightarrow s_{2}(n)\leqslant 1\Leftrightarrow n}$ est une puissance de 2.
• Les coefficients binomiaux sont entiers par définition. Redémontrons-le à partir de l'expression ${\displaystyle {n \choose m}={\frac {n!}{m!(n-m)!}}}$ (pour ${\displaystyle 0\leqslant m\leqslant n}$). Pour cela, il suffit de vérifier que pour tout nombre premier ${\displaystyle p}$, ${\displaystyle v_{p}(m!)+v_{p}((n-m)!)\leqslant v_{p}(n!)}$. D'après la formule de Legendre et la propriété ${\displaystyle \lfloor x\rfloor +\lfloor y\rfloor \leqslant \lfloor x+y\rfloor }$, on a bien :

${\displaystyle v_{p}(m!)+v_{p}((n-m)!)=\sum _{k=1}^{\infty }\left(\lfloor m/p^{k}\rfloor +\lfloor (n-m)/p^{k}\rfloor \right)\leqslant \sum _{k=1}^{\infty }\lfloor m/p^{k}+(n-m)/p^{k}\rfloor =\sum _{k=1}^{\infty }\lfloor n/p^{k}\rfloor =v_{p}(n!)}$.

Cette propriété équivaut au fait que le produit de m entiers consécutifs est divisible par m!.

• Pour ${\displaystyle n\geqslant 1}$ l’exposant de 2 dans la décomposition en facteurs premiers du coefficient binomial central ${\displaystyle {\binom {2n}{n}}}$ est donné par le nombre de 1 dans l’écriture binaire de ${\displaystyle n}$.

En effet, d'après la deuxième forme de la formule, ${\displaystyle v_{2}\left({\binom {2n}{n}}\right)=v_{2}((2n)!)-2v_{2}(n!)=2n-s_{2}(2n)-2(n-s_{2}(n))=2s_{2}(n)-s_{2}(2n)=s_{2}(n)}$.

Pour le cas général d'un coefficient binomial quelconque, voir le théorème de Kummer sur les coefficients binomiaux.

Remarquons d'abord que pour k > log_p(n), ${\displaystyle \lfloor n/p^{k}\rfloor =0}$.

Parmi les entiers de ${\displaystyle 1}$ à ${\displaystyle n}$ (dont ${\displaystyle n!}$ est le produit), les multiples de ${\displaystyle p^{k}}$ sont au nombre de ${\displaystyle \lfloor n/p^{k}\rfloor }$, donc ceux dont la valuation p-adique est exactement ${\displaystyle k}$ sont au nombre de ${\displaystyle \lfloor n/p^{k}\rfloor -\lfloor n/p^{k+1}\rfloor }$. Par conséquent,

${\displaystyle v_{p}(n!)=\left(\lfloor n/p\rfloor -\lfloor n/p^{2}\rfloor \right)+2\left(\lfloor n/p^{2}\rfloor -\lfloor n/p^{3}\rfloor \right)+3\left(\lfloor n/p^{3}\rfloor -\lfloor n/p^{4}\rfloor \right)+\dots }$,

ce qui, après simplification, donne la première forme de la formule.

Pour obtenir la seconde forme, considérons la décomposition de ${\displaystyle n}$ en base ${\displaystyle p}$ : ${\displaystyle n=\sum _{j=0}^{\infty }n_{j}p^{j}}$ (avec ${\displaystyle n_{j}=0}$ pour j > log_p(n)). Alors,

${\displaystyle \sum _{k\geqslant 1}\lfloor n/p^{k}\rfloor =\sum _{k\geqslant 1}\sum _{j\geqslant k}n_{j}p^{j-k}=\sum _{j\geqslant 1}n_{j}\sum _{1\leqslant k\leqslant j}p^{j-k}=\sum _{j\geqslant 1}n_{j}{\frac {p^{j}-1}{p-1}}={\frac {1}{p-1}}\left(\sum _{j\geqslant 1}n_{j}p^{j}-\sum _{j\geqslant 1}n_{j}\right)={\frac {(n-n_{0})-(s_{p}(n)-n_{0})}{p-1}}={\frac {n-s_{p}(n)}{p-1}}}$.

La version récursive peut se démontrer directement ou se déduire de la première égalité en utilisant le fait que ${\displaystyle \left\lfloor {\frac {\lfloor x\rfloor }{p}}\right\rfloor =\left\lfloor {x \over {p}}\right\rfloor }$[3] - [1].