Accéder à mon compte > Accéder à ma feuille d'exercices >

Formule de Legendre - Bibm@th.net

Exercice 1 - Formule de Legendre ♡ [Signaler une erreur] [Ajouter à ma feuille d'exos] [Copier le lien]

Enoncé

Soit $n\geq 1$ un entier et $p\geq 2$ un nombre premier. Soit aussi $N$ tel que $p^N\geq n$.

Soit $u\geq 1$ un entier. Combien-y-a-t-il de multiples de $u$ dans $\{1,\dots,n\}$?
Soit $k\geq 1$ et $A_k=\big \{l\in\{1,\dots,n\}:\ \nu_p(l)=k\big\}$. Calculer le cardinal de $A_k$.
En déduire la formule de Legendre : $$\nu_p(n!)=\sum_{k=1}^N \left\lfloor \frac n{p^k}\right\rfloor.$$
Par combien de zéros se termine le nombre $1000!\ $?

Indication

Corrigé

Un multiple de $u$ s'écrit $ku$. Soit $mu$ le plus grand multiple dans $\{1,\dots,n\}$. Alors $um\leq n<u(m+1)$ et donc $$m\leq \frac nu <m+1.$$ Puisque $m$ est un entier, on reconnait $m=\left\lfloor \frac nu\right\rfloor$. Les multiples de $u$ dans $\{1,\dots,n\}$ étant les entiers $ku$, avec $1\leq k\leq m$, on déduit que leur nombre est égal à $\lfloor \frac nu\rfloor.$
Soit $l\in\{1,\dots,n\}$. Alors $\nu_p(l)=k$ si et seulement si $p^k$ divise $l$ mais $p^{k+1}$ ne divise pas $l$. D'après la question précédente, on déduit que $$\card(A_k)=\left\lfloor \frac n{p^k}\right\rfloor-\left\lfloor \frac n{p^{k+1}}\right\rfloor.$$
On commence par écrire \begin{align*} \nu_p(n!)&=\sum_{l=1}^n \nu_p(l)\\ &=\sum_{k=1}^N k \card\left(\{l\in\{1,\dots,n\}:\ \nu_p(l)=k\}\right) \end{align*} où on a regroupé les éléments de $\{1,\dots,n\}$ suivant leur valuation $p$-adique. En utilisant le résultat de la question précédente, \begin{align*} \nu_p(n!)&=\sum_{k=1}^N k \left(\left\lfloor \frac n{p^k}\right\rfloor-\left\lfloor \frac n{p^{k+1}}\right\rfloor\right)\\ &=\sum_{k=1}^N k \left\lfloor \frac n{p^k}\right\rfloor-\sum_{k=1}^N k \left\lfloor \frac n{p^{k+1}}\right\rfloor\\ &=\sum_{k=1}^N k \left\lfloor \frac n{p^k}\right\rfloor-\sum_{k=2}^{N+1} (k-1) \left\lfloor \frac n{p^{k}}\right\rfloor\\ &=\sum_{k=1}^N \left\lfloor \frac n{p^k}\right\rfloor-N \left\lfloor\frac{n}{p^{N+1}}\right\rfloor\\ &=\sum_{k=1}^N \left\lfloor \frac n{p^k}\right\rfloor \end{align*} où la dernière ligne vient du fait que $p^{N+1}>n$.
Il suffit de calculer la plus grande puissance $N$ telle que $10^N|1000!$. Comme $10=2\times 5$, on obtient $N=\min(v_2(1000!),v_5(1000!))$. En utilisant la formule de Legendre, on trouve \begin{align*} v_5(1000!)&=\Big\lfloor\frac{1000}5\Big\rfloor+\Big\lfloor \frac{1000}{25}\Big\rfloor+\Big\lfloor \frac{1000}{125}\Big\rfloor+\Big\lfloor \frac{1000}{625}\Big\rfloor\\ &=249\\ v_2(1000!)&\geq \Big\lfloor\frac{1000}{2}\Big\rfloor=500. \end{align*} Ainsi, $1000!$ se termine par $249$ zéros.