Formule de Legendre

En mathématiques et plus précisément en théorie des nombres, la formule de Legendre donne une expression, pour tout nombre premier p et tout entier naturel n, de la valuation p-adique de la factorielle de n (l'exposant de p dans la décomposition en facteurs premiers de nǃ, ou encore, le plus grand entier $v$ tel que $p^{v}$ divise n!) :

$v_{p}(n!)=\sum _{k=1}^{\infty }\lfloor n/p^{k}\rfloor =\lfloor n/p\rfloor +\lfloor n/p^{2}\rfloor +\cdots$ où $\lfloor x\rfloor$ désigne la partie entière de $x$, également notée $E(x)$.

Cette formule peut se mettre sous la deuxième forme $v_{p}(n!)={\frac {n-s_{p}(n)}{p-1}}$ où $s_{p}(n)$ désigne la somme des chiffres de $n$ en base $p$.

Historique

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

Version récursive

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

Par exemple, par combien de zéros se termine (en) le nombre $1000!$ ?

$v_{10}(1000!)=\min(v_{2}(1000!),v_{5}(1000!))=v_{5}(1000!)$,

or $v_{5}(1000!)=\lfloor 1000/5\rfloor +v_{5}(\lfloor 1000/5\rfloor !)=200+v_{5}(200!)=240+8+1=249$.

Le nombre $1000!$ se termine donc par $249$ zéros.

Exemples d'applications

• 

  En rouge, courbe de $v_{5}(n!)$, nombre de zéros terminant $n!$ en fonction de $n$. En vert le majorant $(n-1)/4$, en bleu le minorant $n/4-N_{5}(n)$. Rouge=vert pour $n=5,25,125,...$ , rouge = bleu pour $n=4,24,124,...$.

  Pour $n$ fixé, cette formule montre que l'application $p\mapsto v_{p}(n!)$ est décroissante, c'est-à-dire que toute factorielle est un produit de primorielles.
• Comme $s_{p}(n)=o(n)$, $v_{p}(n!)\sim {\frac {n}{p-1}}$ ; par exemple, $n!$ se termine par environ $n/4$ zéros.
• Plus précisément, comme $1\leqslant s_{p}(n)\leqslant (p-1)N_{p}(n)$ où $N_{p}(n)=\lfloor \log _{p}(n)\rfloor +1$ est le nombre de chiffres de n en base p, on a l'encadrement : ${n \over {p-1}}-N_{p}(n)\leqslant v_{p}(n!)\leqslant {{n-1} \over {p-1}}$, avec égalité à droite si et seulement si $n$ est une puissance de $p$ et égalité à gauche si et seulement si $n$ est une puissance de $p$ moins un.
• Un entier $n>0$ vérifie $2^{n-1}\mid n!$ si et seulement si $n$ est une puissance de 2. En effet, $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 ${n \choose m}={\frac {n!}{m!(n-m)!}}$ (pour $0\leqslant m\leqslant n$). Pour cela, il suffit de vérifier que pour tout nombre premier $p$, $v_{p}(m!)+v_{p}((n-m)!)\leqslant v_{p}(n!)$. D'après la formule de Legendre et la propriété $\lfloor x\rfloor +\lfloor y\rfloor \leqslant \lfloor x+y\rfloor$, on a bien :

$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 $n\geqslant 1$ l’exposant de 2 dans la décomposition en facteurs premiers du coefficient binomial central ${\binom {2n}{n}}$ est donné par le nombre de 1 dans l’écriture binaire de $n$.

En effet, d'après la deuxième forme de la formule, $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.

Démonstration de la formule de Legendre

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

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

$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 $n$ en base $p$ : $n=\sum _{j=0}^{\infty }n_{j}p^{j}$ (avec $n_{j}=0$ pour j > log_p(n)). Alors,

$\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 $\left\lfloor {\frac {\lfloor x\rfloor }{p}}\right\rfloor =\left\lfloor {x \over {p}}\right\rfloor$.

Voir aussi

Article connexe

• Fonction exponentielle p-adique (il résulte de la formule de Legendre que son rayon de convergence est $p^{-1/(p-1)}$)
• Lemme LTE donnant la valuation p-adique de $x^{n}\pm y^{n}$.

Lien externe

• Pierre Bornsztein et al., Cours d'arithmétique de préparation aux Olympiades internationales de mathématiques, p. 12-14, 25-26, 32 et 105