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

Historique[modifier | modifier le code]

Adrien-Marie Legendre a publié et démontré cette formule dans son livre de théorie des nombres en 18301. Elle porte aussi parfois le nom d'Alphonse de Polignac2.

Version récursive[modifier | modifier le code]

On a également la relation de récurrence2 :${\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!)=\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.