Formule de Legendre

Un article de Wikipédia, l'encyclopédie libre.

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}${\displaystyle v} tel que ${\displaystyle p^{v}}${\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 }${\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 }${\displaystyle \lfloor x\rfloor } désigne la partie entière de ${\displaystyle x}${\displaystyle x}, également notée ${\displaystyle E(x)}${\displaystyle E(x)}.

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

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 !)}${\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!)}${\displaystyle v_{p}(n!)}.

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

${\displaystyle v_{10}(1000!)=\min(v_{2}(1000!),v_{5}(1000!))=v_{5}(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}${\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!}${\displaystyle 1000!} se termine donc par ${\displaystyle 249}${\displaystyle 249} zéros.

• Pour ${\displaystyle n}${\displaystyle n} fixé, cette formule montre que l'application ${\displaystyle p\mapsto v_{p}(n!)}${\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 s_{p}(n)=o(n)}, ${\displaystyle v_{p}(n!)\sim {\frac {n}{p-1}}}${\displaystyle v_{p}(n!)\sim {\frac {n}{p-1}}} ; par exemple, ${\displaystyle n!}${\displaystyle n!} se termine par environ ${\displaystyle n/4}${\displaystyle n/4} zéros.
• Plus précisément, comme ${\displaystyle 1\leqslant s_{p}(n)\leqslant (p-1)N_{p}(n)}${\displaystyle 1\leqslant s_{p}(n)\leqslant (p-1)N_{p}(n)} où ${\displaystyle N_{p}(n)=\lfloor \log _{p}(n)\rfloor +1}${\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}}}${\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}${\displaystyle n} est une puissance de ${\displaystyle p}${\displaystyle p} et égalité à gauche si et seulement si ${\displaystyle n}${\displaystyle n} est une puissance de ${\displaystyle p}${\displaystyle p} moins un.
• Un entier ${\displaystyle n>0}${\displaystyle n>0} vérifie ${\displaystyle 2^{n-1}\mid n!}${\displaystyle 2^{n-1}\mid n!} si et seulement si ${\displaystyle n}${\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}${\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)!}}}${\displaystyle {n \choose m}={\frac {n!}{m!(n-m)!}}} (pour ${\displaystyle 0\leqslant m\leqslant n}${\displaystyle 0\leqslant m\leqslant n}). Pour cela, il suffit de vérifier que pour tout nombre premier ${\displaystyle p}${\displaystyle p}, ${\displaystyle v_{p}(m!)+v_{p}((n-m)!)\leqslant v_{p}(n!)}${\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 }${\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!)}${\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}${\displaystyle n\geqslant 1} l’exposant de 2 dans la décomposition en facteurs premiers du coefficient binomial central ${\displaystyle {\binom {2n}{n}}}${\displaystyle {\binom {2n}{n}}} est donné par le nombre de 1 dans l’écriture binaire de ${\displaystyle n}${\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)}${\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}${\displaystyle \lfloor n/p^{k}\rfloor =0}.

Parmi les entiers de ${\displaystyle 1}${\displaystyle 1} à ${\displaystyle n}${\displaystyle n} (dont ${\displaystyle n!}${\displaystyle n!} est le produit), les multiples de ${\displaystyle p^{k}}${\displaystyle p^{k}} sont au nombre de ${\displaystyle \lfloor n/p^{k}\rfloor }${\displaystyle \lfloor n/p^{k}\rfloor }, donc ceux dont la valuation p-adique est exactement ${\displaystyle k}${\displaystyle k} sont au nombre de ${\displaystyle \lfloor n/p^{k}\rfloor -\lfloor n/p^{k+1}\rfloor }${\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 }${\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}${\displaystyle n} en base ${\displaystyle p}${\displaystyle p} : ${\displaystyle n=\sum _{j=0}^{\infty }n_{j}p^{j}}${\displaystyle n=\sum _{j=0}^{\infty }n_{j}p^{j}} (avec ${\displaystyle n_{j}=0}${\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}}}${\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 }${\displaystyle \left\lfloor {\frac {\lfloor x\rfloor }{p}}\right\rfloor =\left\lfloor {x \over {p}}\right\rfloor }^{[3] ,[1]} .

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

• 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

• icône décorative Portail des mathématiques

Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Formule_de_Legendre&oldid=220173040 ».

Catégorie :

• Théorie des nombres

Catégories cachées :

• Article contenant un appel à traduction en anglais
• Portail:Mathématiques/Articles liés
• Portail:Sciences/Articles liés
• Projet:Mathématiques/Articles