Legendre's Formula

Legendre's Formula states that

$e_p(n!)=\sum_{i=1}^{\infty} \left\lfloor \dfrac{n}{p^i}\right\rfloor =\frac{n-S_{p}(n)}{p-1}$

where $p$ is a prime and $e_p(n)$ is the exponent of $p$ in the prime factorization of $n$ and $S_p(n)$ is the sum of the digits of $n$ when written in base $p$ .

Proof

Part 1

We could say that $e_p(n!)$ is equal to the number of multiples of $p$ less than $n$ , or $\lfloor \frac{n}{p}\rfloor$ . But the multiples of $p^2$ are only counted once, when they should be counted twice. So we need to add $\lfloor \frac{n}{p^2}\rfloor$ on. But this only counts the multiples of $p^3$ twice, when we need to count them thrice. Therefore we must add a $\lfloor \frac{n}{p^3}\rfloor$ on. We continue like this to get $e_p(n!)=\sum_{i=1}^{\infty} \left\lfloor \dfrac{n}{p^i}\right\rfloor$ . This makes sense, because the terms of this series tend to 0.

Part 2

Let the base $p$ representation of $n$ be $e_xe_{x-1}e_{x-2}\dots e_0$ , where $e_i$ is a digit for all $0\leq i\leq x$ . Therefore the base $p$ representation of $\lfloor \frac{n}{p^i}\rfloor$ is $e_xe_{x-1}\dots e_{x-i}$ . Note that the infinite sum of these numbers (which is $e_p(n!)$ ) is