How to find the exponent of a prime in $n!$

Question

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?

Answer 1

$$ \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.)