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 ${\displaystyle v}$ tel que ${\displaystyle p^{v}}$ divise n!) :

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

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

Historique

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].

Version récursive

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!)}$,

or ${\displaystyle 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.

Exemples d'applications

• 

  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.

Démonstration de la formule de Legendre

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].

Voir aussi

Article connexe

• Fonction exponentielle p-adique (il résulte de la formule de Legendre que son rayon de convergence est ${\displaystyle p^{-1/(p-1)}}$)
• Lemme LTE donnant la valuation p-adique de ${\displaystyle 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

Notes et références

• Portail des mathématiques