# Prime powers that divide a factorial [duplicate]

If we have some prime $p$ and a natural number $k$, is there a formula for the largest natural number $n_k$ such that $p^{n_k} | k!$.

This came up while doing an unrelated homework problem, but it is not itself homework. I haven't had any good ideas yet worth putting here.

The motivation came from trying to figure out what power of a prime you can factor out of a binomial coefficient. Like $\binom{p^m}{k}$.

• This is a standard result in most introductions to number theory. Have you tried googling? "prime power factorial", the obvious keywords to search for, will take you to where you want... Feb 6, 2011 at 21:44
• Ah, I didn't know it was so common a problem. Thanks. Feb 6, 2011 at 21:45

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$

• Ah, the corollary is much more useful for my actual problem that this was related to. Feb 6, 2011 at 22:02

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$$