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!) :

désigne la partie entière de , également notée .

Cette formule peut se mettre sous la deuxième forme désigne la somme des chiffres de en base .

Historique

Adrien-Marie Legendre a publié et démontré cette formule dans son livre de théorie des nombres en 1830[1]. Elle porte aussi parfois le nom d'Alphonse de Polignac[2].

Version récursive

On a également la relation de récurrence[2] : permettant un calcul récursif très simple de .

Par exemple, par combien de zéros se termine (en) le nombre  ? .

Le nombre se termine donc par zéros.

Exemples d'applications

  • En rouge, courbe de , nombre de zéros terminant en fonction de . En vert le majorant , en bleu le minorant . Rouge=vert pour , rouge = bleu pour .
    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 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 [2].

Voir aussi

Article connexe

Lien externe

Notes et références

  1. Adrien Marie LEGENDRE, Théorie des nombres, Paris, (lire en ligne), p. 10
  2. Alphonse 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)
  • Mohammed Aassila, 400 exercices corrigés d'algèbre avec rappels de cours, Paris, Ellipses, 2013
  • Portail des mathématiques
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.