(Formule de Legendre) Soit $n$ un entier naturel supérieur ou égal à $2$ .

Si $p$ est un nombre premier qui divise $n!=1.2...n$ , alors $p$ est un facteur premier de l’un des entiers $2$ ,..., $n$ et en particulier, $p\leq n$ . Réciproquement, il est clair que si $p$ est un nombre premier tel que $p\leq n$ , $p$ divise $n!$ . Les facteurs premiers de $n!$ sont donc les nombres premiers inférieurs ou égaux à $n$ .

Soit donc $p$ un nombre premier tel que $p\leq n$ . Pour trouver l’exposant de $p$ dans la décomposition primaire de $n!$ , on compte $1$ pour chaque multiple de $p$ inférieur ou égal à $n$ , on rajoute $1$ pour chaque multiple de $p^2$ inférieur ou égal à $n$ , on rajoute encore $1$ pour chaque multiple de $p^3$ inférieur ou égal à $n$ ... et on s’arrête quand l’exposant $k$ vérifie $p^k>n$ .

$n\geq p^k\Leftrightarrow\ln n\geq k\ln p\Leftrightarrow k\leq\frac{\ln n}{\ln p},$

(car $\ln p>0$ ). Donc, si $k\geq E(\frac{\ln n}{\ln p})+1$ , alors $p^k>n$ .

Dit autrement, l’exposant de $p$ est la somme du nombre de multiples de $p$ inférieurs ou égaux à $n$ , du nombre de multiples de $p^2$ inférieurs ou égaux à $n$ , du nombre de multiple de $p^3$ inférieurs ou égaux à $n$ ... et du nombre de multiples de $p^{E(\ln n/\ln p)}$ .

Soit $k$ un entier tel que $1\leq k\leq E(\frac{\ln n}{\ln p})$ et $K$ un entier naturel.

$1\leq K.p^k\leq n\Leftrightarrow \frac{1}{p^k}\leq K\leq\frac{n}{p^k}\Leftrightarrow 1\leq K\leq E(\frac{n}{p^k}).$

Il y a donc $E(\frac{n}{p^k})$ multiples de $p^k$ compris au sens large entre $1$ et $n$ . On a montré que l’exposant de $p$ dans la décomposition de $n!$ en facteurs premiers est

$E(\frac{n}{p})+E(\frac{n}{p^2})+E(\frac{n}{p^3})+...$

exo7 5310