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$ ^[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].

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 $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 ${\displaystyle v_{5}(1000!)=\lfloor 1000/5\rfloor +v_{5}(\lfloor 1000/5\rfloor$ .

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$ ^[3]^,^[1].

Voir aussi

Articles connexes

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}$ .

Liens externes

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