Formule de Legendre

Enmathématiqueset plus précisément enthéorie des nombres,laformule de Legendredonne une expression, pour toutnombre premierpet toutentier natureln,de lavaluationp-adiquede lafactorielleden(l'exposant depdans ladécomposition en facteurs premiersdenǃ, ou encore, le plus grand entier$v$tel que$p^{v}$divisen!):

$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 lapartie entièrede$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 lasomme des chiffresde$n$enbase$p$.

Historique

Adrien-Marie Legendrea 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 dezé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 deprimorielles.
• 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 denen basep,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 unepuissance 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.
• Lescoefficients binomiauxsont 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 laproprié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 dementiers consécutifs est divisible parm!.

• Pour$n\geqslant 1$l’exposant de 2 dans la décomposition en facteurs premiers ducoefficient 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 lethéorème de Kummer sur les coefficients binomiaux.

Démonstration de la formule de Legendre

Remarquons d'abord que pourk>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 valuationp-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$pourj> 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 utilisantle fait que$\left\lfloor {\frac {\lfloor x\rfloor }{p}}\right\rfloor =\left\lfloor {x \over {p}}\right\rfloor$.

Voir aussi

Article connexe

• Fonction exponentiellep-adique(il résulte de la formule de Legendre que sonrayon de convergenceest$p^{-1/(p-1)}$)
• Lemme LTEdonnant la valuationp-adique de$x^{n}\pm y^{n}$.

Lien externe

• Pierre Bornszteinet al.,Cours d'arithmétiquede préparation auxOlympiades internationales de mathématiques,p. 12-14, 25-26, 32 et 105