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 v {\displaystyle v} tel que p v {\displaystyle p^{v}} divise n !) :
v p ( n ! ) = ∑ k = 1 ∞ ⌊ n / p k ⌋ = ⌊ n / p ⌋ + ⌊ n / p 2 ⌋ + ⋯ {\displaystyle v_{p}(n!)=\sum _{k=1}^{\infty }\lfloor n/p^{k}\rfloor =\lfloor n/p\rfloor +\lfloor n/p^{2}\rfloor +\cdots } où ⌊ x ⌋ {\displaystyle \lfloor x\rfloor } désigne la partie entière de x {\displaystyle x} , également notée E ( x ) {\displaystyle E(x)} .
Cette formule peut se mettre sous la deuxième forme v p ( n ! ) = n − s p ( n ) p − 1 {\displaystyle v_{p}(n!)={\frac {n-s_{p}(n)}{p-1}}} où s p ( n ) {\displaystyle s_{p}(n)} désigne la somme des chiffres de n {\displaystyle n} en base p {\displaystyle p} [ 1] .
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] .
On a également la relation de récurrence[ 3] : v p ( n ! ) = ⌊ n / p ⌋ + v p ( ⌊ n / p ⌋ ! ) {\displaystyle v_{p}(n!)=\lfloor n/p\rfloor +v_{p}(\lfloor n/p\rfloor !)} permettant un calcul récursif très simple de v p ( n ! ) {\displaystyle v_{p}(n!)} .
Par exemple, par combien de zéros se termine (en) le nombre 1000 ! {\displaystyle 1000!} ?
v 10 ( 1000 ! ) = min ( v 2 ( 1000 ! ) , v 5 ( 1000 ! ) ) = v 5 ( 1000 ! ) {\displaystyle v_{10}(1000!)=\min(v_{2}(1000!),v_{5}(1000!))=v_{5}(1000!)} ,
or v 5 ( 1000 ! ) = ⌊ 1000 / 5 ⌋ + v 5 ( ⌊ 1000 / 5 ⌋ ! ) = 200 + v 5 ( 200 ! ) = 240 + 8 + 1 = 249 {\displaystyle v_{5}(1000!)=\lfloor 1000/5\rfloor +v_{5}(\lfloor 1000/5\rfloor !)=200+v_{5}(200!)=240+8+1=249} .
Le nombre 1000 ! {\displaystyle 1000!} se termine donc par 249 {\displaystyle 249} zéros.
En rouge, courbe de v 5 ( n ! ) {\displaystyle v_{5}(n!)} , nombre de zéros terminant n ! {\displaystyle n!} en fonction de n {\displaystyle n} . En vert le majorant ( n − 1 ) / 4 {\displaystyle (n-1)/4} , en bleu le minorant n / 4 − N 5 ( n ) {\displaystyle n/4-N_{5}(n)} . Rouge=vert pour n = 5 , 25 , 125 , . . . {\displaystyle n=5,25,125,...} , rouge = bleu pour n = 4 , 24 , 124 , . . . {\displaystyle n=4,24,124,...} . Pour n {\displaystyle n} fixé, cette formule montre que l'application p ↦ v p ( n ! ) {\displaystyle p\mapsto v_{p}(n!)} est décroissante, c'est-à-dire que toute factorielle est un produit de primorielles . Comme s p ( n ) = o ( n ) {\displaystyle s_{p}(n)=o(n)} , v p ( n ! ) ∼ n p − 1 {\displaystyle v_{p}(n!)\sim {\frac {n}{p-1}}} ; par exemple, n ! {\displaystyle n!} se termine par environ n / 4 {\displaystyle n/4} zéros. Plus précisément, comme 1 ⩽ s p ( n ) ⩽ ( p − 1 ) N p ( n ) {\displaystyle 1\leqslant s_{p}(n)\leqslant (p-1)N_{p}(n)} où N p ( n ) = ⌊ log p ( n ) ⌋ + 1 {\displaystyle N_{p}(n)=\lfloor \log _{p}(n)\rfloor +1} est le nombre de chiffres de n en base p , on a l'encadrement : n p − 1 − N p ( n ) ⩽ v p ( n ! ) ⩽ n − 1 p − 1 {\displaystyle {n \over {p-1}}-N_{p}(n)\leqslant v_{p}(n!)\leqslant {{n-1} \over {p-1}}} , avec égalité à droite si et seulement si n {\displaystyle n} est une puissance de p {\displaystyle p} et égalité à gauche si et seulement si n {\displaystyle n} est une puissance de p {\displaystyle p} moins un. Un entier n > 0 {\displaystyle n>0} vérifie 2 n − 1 ∣ n ! {\displaystyle 2^{n-1}\mid n!} si et seulement si n {\displaystyle n} est une puissance de 2 . En effet, 2 n − 1 ∣ n ! ⇔ v 2 ( n ! ) ⩾ n − 1 ⇔ n − s 2 ( n ) ⩾ n − 1 ⇔ s 2 ( n ) ⩽ 1 ⇔ n {\displaystyle 2^{n-1}\mid n!\Leftrightarrow v_{2}(n!)\geqslant n-1\Leftrightarrow n-s_{2}(n)\geqslant n-1\Leftrightarrow s_{2}(n)\leqslant 1\Leftrightarrow n} est une puissance de 2. Les coefficients binomiaux sont entiers par définition. Redémontrons-le à partir de l'expression ( n m ) = n ! m ! ( n − m ) ! {\displaystyle {n \choose m}={\frac {n!}{m!(n-m)!}}} (pour 0 ⩽ m ⩽ n {\displaystyle 0\leqslant m\leqslant n} ). Pour cela, il suffit de vérifier que pour tout nombre premier p {\displaystyle p} , v p ( m ! ) + v p ( ( n − m ) ! ) ⩽ v p ( n ! ) {\displaystyle v_{p}(m!)+v_{p}((n-m)!)\leqslant v_{p}(n!)} . D'après la formule de Legendre et la propriété ⌊ x ⌋ + ⌊ y ⌋ ⩽ ⌊ x + y ⌋ {\displaystyle \lfloor x\rfloor +\lfloor y\rfloor \leqslant \lfloor x+y\rfloor } , on a bien : v p ( m ! ) + v p ( ( n − m ) ! ) = ∑ k = 1 ∞ ( ⌊ m / p k ⌋ + ⌊ ( n − m ) / p k ⌋ ) ⩽ ∑ k = 1 ∞ ⌊ m / p k + ( n − m ) / p k ⌋ = ∑ k = 1 ∞ ⌊ n / p k ⌋ = v p ( n ! ) {\displaystyle v_{p}(m!)+v_{p}((n-m)!)=\sum _{k=1}^{\infty }\left(\lfloor m/p^{k}\rfloor +\lfloor (n-m)/p^{k}\rfloor \right)\leqslant \sum _{k=1}^{\infty }\lfloor m/p^{k}+(n-m)/p^{k}\rfloor =\sum _{k=1}^{\infty }\lfloor n/p^{k}\rfloor =v_{p}(n!)} . Cette propriété équivaut au fait que le produit de m entiers consécutifs est divisible par m !.
Pour n ⩾ 1 {\displaystyle n\geqslant 1} l’exposant de 2 dans la décomposition en facteurs premiers du coefficient binomial central ( 2 n n ) {\displaystyle {\binom {2n}{n}}} est donné par le nombre de 1 dans l’écriture binaire de n {\displaystyle n} . En effet, d'après la deuxième forme de la formule, v 2 ( ( 2 n n ) ) = v 2 ( ( 2 n ) ! ) − 2 v 2 ( n ! ) = 2 n − s 2 ( 2 n ) − 2 ( n − s 2 ( n ) ) = 2 s 2 ( n ) − s 2 ( 2 n ) = s 2 ( n ) {\displaystyle v_{2}\left({\binom {2n}{n}}\right)=v_{2}((2n)!)-2v_{2}(n!)=2n-s_{2}(2n)-2(n-s_{2}(n))=2s_{2}(n)-s_{2}(2n)=s_{2}(n)} .
Pour le cas général d'un coefficient binomial quelconque, voir le théorème de Kummer sur les coefficients binomiaux .
Remarquons d'abord que pour k > logp (n ) , ⌊ n / p k ⌋ = 0 {\displaystyle \lfloor n/p^{k}\rfloor =0} .
Parmi les entiers de 1 {\displaystyle 1} à n {\displaystyle n} (dont n ! {\displaystyle n!} est le produit), les multiples de p k {\displaystyle p^{k}} sont au nombre de ⌊ n / p k ⌋ {\displaystyle \lfloor n/p^{k}\rfloor } , donc ceux dont la valuation p -adique est exactement k {\displaystyle k} sont au nombre de ⌊ n / p k ⌋ − ⌊ n / p k + 1 ⌋ {\displaystyle \lfloor n/p^{k}\rfloor -\lfloor n/p^{k+1}\rfloor } . Par conséquent,
v p ( n ! ) = ( ⌊ n / p ⌋ − ⌊ n / p 2 ⌋ ) + 2 ( ⌊ n / p 2 ⌋ − ⌊ n / p 3 ⌋ ) + 3 ( ⌊ n / p 3 ⌋ − ⌊ n / p 4 ⌋ ) + … {\displaystyle v_{p}(n!)=\left(\lfloor n/p\rfloor -\lfloor n/p^{2}\rfloor \right)+2\left(\lfloor n/p^{2}\rfloor -\lfloor n/p^{3}\rfloor \right)+3\left(\lfloor n/p^{3}\rfloor -\lfloor n/p^{4}\rfloor \right)+\dots } , ce qui, après simplification, donne la première forme de la formule.
Pour obtenir la seconde forme, considérons la décomposition de n {\displaystyle n} en base p {\displaystyle p} : n = ∑ j = 0 ∞ n j p j {\displaystyle n=\sum _{j=0}^{\infty }n_{j}p^{j}} (avec n j = 0 {\displaystyle n_{j}=0} pour j > logp (n ) ). Alors,
∑ k ⩾ 1 ⌊ n / p k ⌋ = ∑ k ⩾ 1 ∑ j ⩾ k n j p j − k = ∑ j ⩾ 1 n j ∑ 1 ⩽ k ⩽ j p j − k = ∑ j ⩾ 1 n j p j − 1 p − 1 = 1 p − 1 ( ∑ j ⩾ 1 n j p j − ∑ j ⩾ 1 n j ) = ( n − n 0 ) − ( s p ( n ) − n 0 ) p − 1 = n − s p ( n ) p − 1 {\displaystyle \sum _{k\geqslant 1}\lfloor n/p^{k}\rfloor =\sum _{k\geqslant 1}\sum _{j\geqslant k}n_{j}p^{j-k}=\sum _{j\geqslant 1}n_{j}\sum _{1\leqslant k\leqslant j}p^{j-k}=\sum _{j\geqslant 1}n_{j}{\frac {p^{j}-1}{p-1}}={\frac {1}{p-1}}\left(\sum _{j\geqslant 1}n_{j}p^{j}-\sum _{j\geqslant 1}n_{j}\right)={\frac {(n-n_{0})-(s_{p}(n)-n_{0})}{p-1}}={\frac {n-s_{p}(n)}{p-1}}} . La version récursive peut se démontrer directement ou se déduire de la première égalité en utilisant le fait que ⌊ ⌊ x ⌋ p ⌋ = ⌊ x p ⌋ {\displaystyle \left\lfloor {\frac {\lfloor x\rfloor }{p}}\right\rfloor =\left\lfloor {x \over {p}}\right\rfloor } [ 3] , [ 1] .
↑ a et b Mohammed Aassila, 1000 challenges mathématiques, Algèbre , Ellipses, 2016 , p. 97 ↑ Adrien Marie LEGENDRE, Théorie des nombres , Paris, 1830 (lire en ligne ) , p. 10 ↑ a b et c 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 , 1905 , p. 5 et suivantes (lire en ligne )