## A formula for the largest power of a prime dividing a factorial

Let $p$ be a prime and $n \in \mathbb{Z}^+$. Find a formula for the largest power of $p$ which divides $n!$.

Before attacking this problem, we prove the following lemma.

Lemma: Let $a,b \in \mathbb{Z}^+$. The number of multiples of $a$ which are less than or equal to $b$ is $\lfloor \frac{b}{a} \rfloor$.

Proof: Note first that $\lfloor \frac{b}{a} \rfloor$ is precisely the quotient part returned by the Euclidean algorithm on $b$ and $a$, since if $b = qa + r$ where $0 \leq r < a$, then $\frac{b}{a} = q + \frac{r}{a}$, so $q = \lfloor \frac{b}{a} \rfloor$. Then we have $ka \leq b$ for precisely $1 \leq k \leq q$. $\square$

Now for the main problem. Our goal is to find a formula that gives the largest power of $p$ which divides $n!$; equivalently, to find the number of times $p$ appears in the factorization of $n!$. Note that there will be one $p$ factor for each multiple of $p$ less than $n$ – that is, $\lfloor \frac{n}{p} \rfloor$. This does not account for all of the factors, though; multiples of $p^2$ contribute one more each, for a total of $\lfloor \frac{n}{p^2} \rfloor$. We can continue for higher powers of $p$; for each $k \in \mathbb{Z}^+$ we count an additional $\lfloor \frac{n}{p^k} \rfloor$ factors. Note that every $p$ factor is counted. Moreover, no factor is counted more than once. Thus, the highest power of $p$ which divides $n$ is $p^M$, where $M = \sum_{k \in \mathbb{Z}^+} \lfloor \frac{n}{p^k} \rfloor$. Note that for sufficiently large $k$, $\lfloor \frac{n}{p^k} \rfloor = 0$, so that the summation indeed converges. $\blacksquare$