Formule de Legendre pour la factorielle

Soient $n$ un entier strictement positif et $p$ un nombre premier. Montrer que

$v_p(n!)=\sum_{i=1}^{+\infty}\left\lfloor\frac{n}{p^i}\right\rfloor,$

où $v_p$ désigne la valuation $p$ -adique et $\lfloor x\rfloor$ la partie entière de $x$ .

I solved itMark it done Add to my listKeep it in your list

I like this problem3 likes

Liked by

Solutions

Reveal solutionsAre you sure? Give it a try first.

Solution by Ancient Tree

Discussions0 useful votes

La factorielle de $n$ est $n!=1\times 2\times 3\times \ldots \times n$ . Pour compter le nombre de fois que $p$ apparaît dans la factorielle, il faut déjà compter tous les multiples de $p$ entre $1$ et $n$ . Mais parmi eux, les multiples de $p^{2}$ contribuent une fois de plus ; et parmi eux, les multiples de $p^{3}$ contribuent encore une fois de plus... Et ainsi de suite jusqu’à l’infini. (En réalité, ce processus s’arrête dès que $p^{i}>n$ , puisqu’alors il n’y a plus aucun multiple de $p^{i}$ entre $1$ et $n$ ).

Ainsi, la valuation $p$ -adique de $n!$ est :
$v_{p}(n!)=\text{nombre de multiples de }p\;+\text{nombre de multiples de }p^{2}\;+\text{nombre de multiples de } p^{3}\;+\ldots$ entre $1$ et $n$ .

Or, le nombre de multiples d’un entier $k$ entre $1$ et $n$ est donné par la partie entière de $\frac{n}{k}$ .

Bref, on obtient :
$v_{p}(n!)=\left\lfloor\frac{n}{p}\right\rfloor+\left\lfloor\frac{n}{p^{2}}\right\rfloor+\left\lfloor\frac{n}{p^{3}}\right\rfloor+\ldots$ ce qui est le résultat annoncé.

Report