Prime powers that divide a factorial [duplicate]

Solution 1:

This follows from a famous result of Kummer:

Theorem. (Kummer, 1854) The highest power of $p$ that divides the binomial coefficient $\binom{m+n}{n}$ is equal to the number of "carries" when adding $m$ and $n$ in base $p$.

Equivalently, the highest power of $p$ that divides $\binom{m}{n}$, with $0\leq n\leq m$ is the number of carries when you add $m-n$ and $n$ in base $p$.

As a corollary, you get

Corollary. For a positivie integer $r$ and a prime $p$, let $[r]_p$ denote the exact $p$-divisor of $r$; that is, we say $[r]_p=a$ if $p^a|r$ but $p^{a+1}$ does not divide $r$. If $0\lt k\leq p^n$, then $$\left[\binom{p^n}{k}\right]_p = n - [k]_p.$$

Proof. To get a proof, assuming Kummer's Theorem: when you add $p^n - k$ and $k$ in base $p$, you get a $1$ followed by $n$ zeros. You start getting a carry as soon as you don't have both numbers in the column equal to $0$, which is as soon as you hit the first nonzero digit of $k$ in base $p$ (counting from right to left). So you really just need to figure out what is the first nonzero digit of $k$ in base $p$, from right to left. This is exactly the $([k]_p+1)$th digit. So the number of carries will be $(n+1)-([k]_p+1) = n-[k]_p$, hence this is the highest power of $p$ that divides $\binom{p^n}{k}$, as claimed. $\Box$

Solution 2:

It should be fairly obvious that the answer is $$n_k = \biggl\lfloor{\frac{k}{p}\biggr\rfloor} + \biggl\lfloor{\frac{k}{p^2}\biggr\rfloor} +\biggl\lfloor{\frac{k}{p^3}\biggr\rfloor} + \cdots$$