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 !