Legendre's formula

For n = 6, one has ${\displaystyle 6!=720=2^{4}\cdot 3^{2}\cdot 5^{1}}$. The exponents ${\displaystyle \nu _{2}(6!)=4,\nu _{3}(6!)=2}$ and ${\displaystyle \nu _{5}(6!)=1}$ can be computed by Legendre's formula as follows:

${\displaystyle {\begin{aligned}\nu _{2}(6!)&=\sum _{i=1}^{\infty }\left\lfloor {\frac {6}{2^{i}}}\right\rfloor =\left\lfloor {\frac {6}{2}}\right\rfloor +\left\lfloor {\frac {6}{4}}\right\rfloor =3+1=4,\\[3pt]\nu _{3}(6!)&=\sum _{i=1}^{\infty }\left\lfloor {\frac {6}{3^{i}}}\right\rfloor =\left\lfloor {\frac {6}{3}}\right\rfloor =2,\\[3pt]\nu _{5}(6!)&=\sum _{i=1}^{\infty }\left\lfloor {\frac {6}{5^{i}}}\right\rfloor =\left\lfloor {\frac {6}{5}}\right\rfloor =1.\end{aligned}}}$

Since ${\displaystyle n!}$ is the product of the integers 1 through n, we obtain at least one factor of p in ${\displaystyle n!}$ for each multiple of p in ${\displaystyle \{1,2,\dots ,n\}}$, of which there are ${\displaystyle \textstyle \left\lfloor {\frac {n}{p}}\right\rfloor }$. Each multiple of ${\displaystyle p^{2}}$ contributes an additional factor of p, each multiple of ${\displaystyle p^{3}}$ contributes yet another factor of p, etc. Adding up the number of these factors gives the infinite sum for ${\displaystyle \nu _{p}(n!)}$.

Write ${\displaystyle n=n_{\ell }p^{\ell }+\cdots +n_{1}p+n_{0}}$ in base p. Then ${\displaystyle \textstyle \left\lfloor {\frac {n}{p^{i}}}\right\rfloor =n_{\ell }p^{\ell -i}+\cdots +n_{i+1}p+n_{i}}$, and therefore

${\displaystyle {\begin{aligned}\nu _{p}(n!)&=\sum _{i=1}^{\ell }\left\lfloor {\frac {n}{p^{i}}}\right\rfloor \\&=\sum _{i=1}^{\ell }\left(n_{\ell }p^{\ell -i}+\cdots +n_{i+1}p+n_{i}\right)\\&=\sum _{i=1}^{\ell }\sum _{j=i}^{\ell }n_{j}p^{j-i}\\&=\sum _{j=1}^{\ell }\sum _{i=1}^{j}n_{j}p^{j-i}\\&=\sum _{j=1}^{\ell }n_{j}\cdot {\frac {p^{j}-1}{p-1}}\\&=\sum _{j=0}^{\ell }n_{j}\cdot {\frac {p^{j}-1}{p-1}}\\&={\frac {1}{p-1}}\sum _{j=0}^{\ell }\left(n_{j}p^{j}-n_{j}\right)\\&={\frac {1}{p-1}}\left(n-s_{p}(n)\right).\end{aligned}}}$