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.

Factorielle Trailing zeros

Factorielle n + 1 et n – 1

(n + 1)! = (n + 1) n!

(n + 1)! = (n + 1) n (n – 1)!

(n + 1)! = (n² + n) (n – 1)!

10! secondes = 6 semaines=3! semaines

10!=3!*5!*7!

(n + 1)! – 1 = 1.1! + 2.2! + 3.3! +…+ n.n!

1 semaine = 7 jours !!!

La quantité de zéros finaux (trailing zeros) dans n! est donnée par cette formule, avec 5^k  n:

(on ne conserve que les parties entières des divisions)

Factorielle Trailing zeros

La quantité de zéros finaux (trailing zeros) dans n! est donnée par cette formule, avec 5^k  n:

Exemples (on ne conserve que les parties entières des divisions)

Du même ordre: quantité de puissances d'un premier dans un nombre factoriel

Exemples

Etc.

Or 10! = 2⁸ x 3⁴ x 5² x 7

x

http://www.purplemath.com/modules/factzero.htm