Exercice corrigé : La formule de Legendre

Dans cet article, nous allons vous démontrer la formule de Legendre une formule qui concerne les factorielles.

La valuation p-adique

Soit p un nombre premier. On définit la valuation p-adique de n, notée v_p(n) comme le plus grand entier k tel que p^k divise n . Voici quelques propriétés en passant :

• On pose v_p(0) = -\infty (c’est cohérent avec la définition)

• v_p(ab) = v_p(a) + v_p(b)
• v_p(a+b) \geq \min(v_p(a),v_p(b))

La formule de Legendre

Enoncé de la formule de Legendre

La formule de Legendre est la suivante :

v_p(n!) = \sum_{k=1}^{+\infty} \left\lfloor \dfrac{n}{p^k} \right\rfloor

Démonstration de la formule de Legendre

Rappelons que n! est le produit des entiers de 1 à n. Faisons un peu de dénombrement et remarquons qu’il y a \left\lfloor \dfrac{n}{p^k} \right\rfloor multiples de p^k . En calculant ceci, on a le nombre d’élément dont la valuation vuat au moins k.

Pour avoir ceux dont la valuation vaut exactement k, il faut retrancher ceux dont la valuation vaut au moins k+1. On en a donc \left\lfloor \dfrac{n}{p^k} \right\rfloor-\left\lfloor \dfrac{n}{p^{k+1}} \right\rfloor. Cette quantité là a une valuation p-adique qui vaut k.

Ainsi,

\begin{array}{ll}
v_p(n!) &=1 \left(\left\lfloor \dfrac{n}{p^1} \right\rfloor-\left\lfloor \dfrac{n}{p^{2}}\right\rfloor \right)+2 \left(\left\lfloor \dfrac{n}{p^2} \right\rfloor-\left\lfloor \dfrac{n}{p^{3}}\right\rfloor \right)+3 \left(\left\lfloor \dfrac{n}{p^3} \right\rfloor-\left\lfloor \dfrac{n}{p^{4}}\right\rfloor \right) + \ldots\\
&= \displaystyle \sum_{k=1}^{\infty}k \left(\left\lfloor \dfrac{n}{p^k} \right\rfloor-\left\lfloor \dfrac{n}{p^{k+1}}\right\rfloor \right)\\
&= \displaystyle \sum_{k=1}^{\infty}k \left\lfloor \dfrac{n}{p^k} \right\rfloor- \sum_{k=1}^{\infty}k\left\lfloor \dfrac{n}{p^{k+1}}\right\rfloor \\
&= \displaystyle \sum_{k=1}^{\infty}k \left\lfloor \dfrac{n}{p^k} \right\rfloor- \sum_{k=2}^{\infty}(k-1)\left\lfloor \dfrac{n}{p^{k}}\right\rfloor \\
&= \displaystyle \sum_{k=1}^{\infty}k \left\lfloor \dfrac{n}{p^k} \right\rfloor- \sum_{k=1}^{\infty}(k-1)\left\lfloor \dfrac{n}{p^{k}}\right\rfloor \\
&= \displaystyle \sum_{k=1}^{\infty} \left\lfloor \dfrac{n}{p^k} \right\rfloor
\end{array}

On n’est pas trop posés de question sur la convergence de ces séries car ce sont en fait des sommes finis !

Application : Le nombre de zéros de 1000!

L’exercice est le suivant : Quel est le nombre de zéros à la fin de l’écriture décimale de 1000! ?. Pour répondre à cela, on utilise la formule de Legendre. En effet, pour avoir un 0 à la fin, il faut avoir un 2 et un 5 en diviseur. On va donc déterminer la valuation 5-adique et 2-adique de 1000!. Le plus petit nombre sera le nombre de zéros à la fin de 1000!

• v_5(1000!) = \left\lfloor \dfrac{1000}{5} \right\rfloor+\left\lfloor \dfrac{1000}{25} \right\rfloor+\left\lfloor \dfrac{1000}{125} \right\rfloor+\left\lfloor \dfrac{1000}{625} \right\rfloor = 200 + 40 + 8 + 1 = 249
• v_2(1000!) \geq \left\lfloor \dfrac{1000}{2}\right\rfloor =500 > 249

1000! a donc 249 zéros à la fin de son écriture décimale !