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!) :
Cette formule peut se mettre sous la deuxième forme où désigne la somme des chiffres de en base [1].
Historique
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] : permettant un calcul récursif très simple de .
Par exemple, par combien de zéros se termine (en) le nombre ?
,
or .
Le nombre se termine donc par zéros.
Exemples d'applications
Pour fixé, cette formule montre que l'application est décroissante, c'est-à-dire que toute factorielle est un produit de primorielles.
Comme , ; par exemple, se termine par environ zéros.
Plus précisément, comme où est le nombre de chiffres de n en base p, on a l'encadrement : , avec égalité à droite si et seulement si est une puissance de et égalité à gauche si et seulement si est une puissance de moins un.
Un entier vérifie si et seulement si est une puissance de 2. En effet, est une puissance de 2.
Les coefficients binomiaux sont entiers par définition. Redémontrons-le à partir de l'expression (pour ). Pour cela, il suffit de vérifier que pour tout nombre premier , . D'après la formule de Legendre et la propriété , on a bien :
.
Cette propriété équivaut au fait que le produit de m entiers consécutifs est divisible par m!.
Pour l’exposant de 2 dans la décomposition en facteurs premiers du coefficient binomial central est donné par le nombre de 1 dans l’écriture binaire de .
En effet, d'après la deuxième forme de la formule, .
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 > logp(n), .
Parmi les entiers de à (dont est le produit), les multiples de sont au nombre de , donc ceux dont la valuation p-adique est exactement sont au nombre de . Par conséquent,
,
ce qui, après simplification, donne la première forme de la formule.
Pour obtenir la seconde forme, considérons la décomposition de en base : (avec pour j > logp(n)). Alors,
.
La version récursive peut se démontrer directement ou se déduire de la première égalité en utilisant le fait que[3],[1].
Voir aussi
Article connexe
Fonction exponentielle p-adique (il résulte de la formule de Legendre que son rayon de convergence est )
↑ a et bMohammed Aassila, 1000 challenges mathématiques, Algèbre, Ellipses, , p. 97
↑Adrien Marie LEGENDRE, Théorie des nombres, Paris, (lire en ligne), p. 10
↑ ab et cAlphonse de POLIGNAC, « Recherches sur la divisibilité du nombre 1.2...nx (1.2...x)^n par les puissances de la factorielle 1.2 ...n », Bulletin de la S. M. F., tome 32, , p. 5 et suivantes (lire en ligne)