Proving Legendre's Formula

Where $v_p(n)$ is called the $p$-adic valuation of $n$.

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

so far i have that $v_p(n!) = v_p(n) + v_p(n-1) + \cdots + v_p(2) + v_p(1)$

and $$\sum_{t=1}^\infty \left\lfloor \frac{n}{p^t} \right\rfloor = \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \cdots +\left\lfloor \frac{n}{p^r} \right\rfloor = p^{r-1} + p^{r-2} + \cdots + p + 1$$

where $p^r||n$

I don't really know where to go from here. Any suggestions would be great.

Solution 1:

A formula like this can seem very mystifying without considering specific examples. Let's see what happens when $n=9$ and $p=2$.

Start by writing out the factors of $9!$:

$$9! = 1\cdot2\cdot3\cdot4\cdot5\cdot6\cdot7\cdot8\cdot9.$$

I'm going to make a table that counts the number of times $2$ divides each factor. Remember that $\lfloor n/p^t\rfloor$ is the number of multiples of $p^t$ between $1$ and $n$.

$$ \begin{array}{c|ccccccccc|c} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & \text{How many?} \\ \hline \text{multiple of }2 &&x&&x&&x&&x&& \lfloor9/2\rfloor=4 \\ \text{multiple of }4 &&&&x&&&&x&& \lfloor9/4\rfloor=2\\ \text{multiple of }8 &&&&&&&&x&& \lfloor9/8\rfloor=1 \end{array} $$

Calculating $v_2(9!)$ is the same as counting the number of $x$'s in the table. Your formula does this by first counting the number of $x$'s in each row, then adding up the total.

(Disclaimer: this answer draws freely from section 4.4 of the excellent book Concrete Mathematics.)