« Formule de Legendre » : différence entre les versions
Balises : Révoqué Éditeur visuel |
Balises : Éditeur visuel Vérification de modification (références) activé Vérification de modification (références) refusée (savoir commun) |
||
Ligne 17 : | Ligne 17 : | ||
permettant un calcul récursif très simple de <math>v_p(n!)</math>. |
permettant un calcul récursif très simple de <math>v_p(n!)</math>. |
||
Par exemple, par combien de {{Lien|trad=Trailing zeros|Zéros à droite|texte=zéros se termine}} le nombre <math>1000!</math> ? |
Par exemple, par combien de {{Lien|trad=Trailing zeros|Zéros à droite|texte=zéros se termine}} le nombre <math>1000!</math> ?<math>v_{10}(1000!)=\min(v_2(1000!),v_5(1000!))=v_5(1000!)= |
||
\lfloor1000/5\rfloor+v_5(\lfloor1000/5\rfloor!)=200+v_5(200!)=240+8+1=249</math>. |
\lfloor1000/5\rfloor+v_5(\lfloor1000/5\rfloor!)=200+v_5(200!)=240+8+1=249</math>. |
||
Le nombre <math>1000!</math> se termine donc par <math>249</math> zéros. |
Le nombre <math>1000!</math> se termine donc par <math>249</math> zéros. |
||
(voir démonstration simplifiée du [[Factorielle#Nombre de z%C3%A9ros finaux de n![7]|nombre de zéros finaux de n!]]) |
|||
== Exemples d'applications == |
== Exemples d'applications == |
Version du 16 mars 2024 à 20:05
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!) :
où désigne la partie entière de , également notée .
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 ?.
Le nombre se termine donc par zéros.
(voir démonstration simplifiée du [[Factorielle#Nombre de z%C3%A9ros finaux de n![7]|nombre de zéros finaux de n!]])
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 )
- Lemme LTE donnant la valuation p-adique de .
- Factorielle Section : Nombre de zéros finaux de
Lien externe
- Pierre Bornsztein et al., Cours d'arithmétique de préparation aux Olympiades internationales de mathématiques, p. 12-14, 25-26, 32 et 105
Notes et références
- Mohammed Aassila, 1000 challenges mathématiques, Algèbre, Ellipses, , p. 97
- Adrien Marie LEGENDRE, Théorie des nombres, Paris, (lire en ligne), p. 10
- 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)