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 Modèle:Mvar et tout entier naturel Modèle:Mvar, de la valuation p-adique de la factorielle de Modèle:Mvar (l'exposant de Modèle:Mvar dans la décomposition en facteurs premiers de Modèle:Mvarǃ, ou encore, le plus grand entier $v$ tel que $p^v$ divise Modèle:Mvar!) :

Modèle:Retrait 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 Modèle:Retrait 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 : Modèle:Retrait permettant un calcul récursif très simple de $v_p(n!)$.

Par exemple, par combien de Modèle:Lien 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⩽s_p(n)⩽(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 : $\frac{n}{p-1}-N_p(n)⩽v_p(n!)⩽\frac{n-1}{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!\iff v_2(n!)⩾n-1\iff n-s_2(n)⩾n-1\iff s_2(n)⩽1\iff n$ est une puissance de 2.
• Les coefficients binomiaux sont entiers par définition. Redémontrons-le à partir de l'expression $(\genfrac{}{}{0ex}{}{n}{m})=\frac{n!}{m!(n-m)!}$ (pour $0⩽m⩽n$). Pour cela, il suffit de vérifier que pour tout nombre premier $p$, $v_p(m!)+v_p((n-m)!)⩽v_p(n!)$. D'après la formule de Legendre et la propriété $\lfloor x\rfloor +\lfloor y\rfloor ⩽\lfloor x+y\rfloor$, on a bien :

$v_p(m!)+v_p((n-m)!)=\sum _{k=1}^{\mathrm{\infty }}(\lfloor m/p^k\rfloor +\lfloor (n-m)/p^k\rfloor )⩽\sum _{k=1}^{\mathrm{\infty }}\lfloor m/p^k+(n-m)/p^k\rfloor =\sum _{k=1}^{\mathrm{\infty }}\lfloor n/p^k\rfloor =v_p(n!)$.

Cette propriété équivaut au fait que le produit de Modèle:Mvar entiers consécutifs est divisible par Modèle:Mvar!.

• Pour $n⩾1$ l’exposant de 2 dans la décomposition en facteurs premiers du coefficient binomial central $(\genfrac{}{}{0ex}{}{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((\genfrac{}{}{0ex}{}{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 Modèle:Math, $\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!)=(\lfloor n/p\rfloor -\lfloor n/p^2\rfloor )+2(\lfloor n/p^2\rfloor -\lfloor n/p^3\rfloor )+3(\lfloor n/p^3\rfloor -\lfloor n/p^4\rfloor )+\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}^{\mathrm{\infty }}{n}_j{p}^j$ (avec $n_j=0$ pour Modèle:Math). Alors,

$\sum _{k⩾1}\lfloor n/p^k\rfloor =\sum _{k⩾1}\sum _{j⩾k}{n}_j{p}^{j-k}=\sum _{j⩾1}{n}_j\sum _{1⩽k⩽j}{p}^{j-k}=\sum _{j⩾1}{n}_j\frac{p^j-1}{p-1}=\frac{1}{p-1}(\sum _{j⩾1}{n}_j{p}^j-\sum _{j⩾1}{n}_j)=\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 $\lfloor \frac{\lfloor x\rfloor }{p}\rfloor =\lfloor \frac{x}{p}\rfloor$Modèle:,.

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 Modèle:Et al., Cours d'arithmétique de préparation aux Olympiades internationales de mathématiques, p. 12-14, 25-26, 32 et 105