How to find the exponent of a prime in $n!$ Let the positive integer $n$ be written as powers of prime $p$ so that we have $n=a_kp^k+....+a_2p^2+a_1p+a_0,$ where $0\leq a_i<p.$ Show that the exponent of the highest power of $p$ appearing in the prime factorization of $n!$ is
$\frac{n-(a_k+....+a_1+a_0)}{p-1}$.
I know that the exponent of $p$ in $n!$ is $\sum_{k=1}^{\infty}\left\lfloor\frac{n}{p^k}\right\rfloor$. But I got stuck on how to use the given expression of $n$. Any suggestions?
 A: $$
\begin{align}
\sum_{i=1}^{\infty} \left\lfloor \frac{n}{p^i} \right\rfloor
&= \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \dotsb + \left\lfloor \frac{n}{p^k} \right\rfloor + \sum_{i=k+1}^{\infty} \left\lfloor \frac{n}{p^i} \right\rfloor \\
&= \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \dotsb + \left\lfloor \frac{n}{p^k} \right\rfloor \\
&= \left\lfloor \frac{a_kp^k+\dotsb+a_2p^2+a_1p+a_0}{p} \right\rfloor + \left\lfloor \frac{a_kp^k+\dotsb+a_2p^2+a_1p+a_0}{p^2} \right\rfloor + \dotsb \\
&\phantom{= \lfloor} + \left\lfloor \frac{a_kp^k+\dotsb+a_2p^2+a_1p+a_0}{p^k} \right\rfloor \\
&= \left\lfloor \frac{n - a_0}{p} + \frac{a_0}{p} \right\rfloor + \left\lfloor \frac{n - (a_1p + a_0)}{p^2} + \frac{a_1p + a_0}{p^2} \right\rfloor + \dotsb \\
&\phantom{= \lfloor} + \left\lfloor \frac{n - (a_{k-1}p^{k-1}+\dotsb+a_2p^2+a_1p+a_0)}{p^k} + \frac{a_{k-1}p^{k-1}+\dotsb+a_2p^2+a_1p+a_0}{p^k} \right\rfloor \\
&= (a_kp^{k-1} + \dotsb + a_2p + a_1) + (a_kp^{k-2} + \dotsb + a_3p + a_2) + \dotsb + (a_k) \\
&\phantom{= \lfloor} + \left\lfloor \frac{a_0}{p} \right\rfloor + \left\lfloor \frac{a_1p + a_0}{p^2} \right\rfloor + \dotsb \left\lfloor \frac{a_{k-1}p^{k-1}+\dotsb+a_2p^2+a_1p+a_0}{p^k} \right\rfloor \\
&= (a_kp^{k-1} + \dotsb + a_2p + a_1) + (a_kp^{k-2} + \dotsb + a_3p + a_2) + \dotsb + (a_k) \\
&= p^{k-1}a_k + p^{k-2}(a_{k-1} + a_k) + \dotsb + p(a_2 + a_3 + \dotsb + a_k) + (a_1 + a_2 + \dotsb + a_k) \\
&= \frac{(p - 1)(p^{k-1}a_k + p^{k-2}(a_{k-1} + a_k) + \dotsb + p(a_2 + a_3 + \dotsb + a_k) + (a_1 + a_2 + \dotsb + a_k))}{p - 1} \\
&= \frac{a_kp^k - a_kp^{k-1} + a_{k-1}p^{k-1} + a_kp^{k-1} - \dotsb + p(a_1 + a_2 + \dotsb + a_k) - (a_1 + a_2 + \dotsb + a_k))}{p - 1} \\
&= \frac{a_kp^k + a_{k-1}p^{k-1} + \dotsb + a_0 - (a_1 + a_2 + \dotsb + a_k)}{p - 1} \\
&= \frac{n - (a_1 + a_2 + \dotsb + a_k)}{p - 1}
\end{align}
$$


*

*Line 2: The remainder of the sum is zero.

*Line 5: The first part in each floor bracket is an integer, and hence comes outside the brackets.

*Line 6: The fractions inside the brackets are less than one due to the way $n$ and $a_0, a_1, \dotsc, a_k$ are defined.

*Line 10: The cancellation works somewhat like a telescopic sum, cancelling all terms except those on the next line. (This can be verified.)

A: Appying Legendre's formula, the first division yields 
$$a_kp^{k-1}+a_{k-1}p^{k-2}+\cdots a_2p+a_1,$$
the next
$$a_kp^{k-2}+a_{k-1}p^{k-3}+\cdots a_2,$$
and so on until
$$a_k.$$
Summing those terms vertically, we get with the geometric series formula
$$a_k\frac{p^k-1}{p-1}+a_{k-1}\frac{p^{k-1}-1}{p-1}+\cdots a_2\frac{p^2-1}{p-1}+a_1=\frac{a_kp^k+a_{k-1}p^{k-1}+\cdots a_2p^2+a_1p+a_0-a_k-a_{k-1}-\cdots a_1-a_0}{p-1}.$$
