(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