Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Possible Duplicate:
How come the number $N!$ can terminate in exactly $1,2,3,4,$ or $6$ zeroes but never $5$ zeroes?

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

share|improve this question
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... –  Mariano Suárez-Alvarez Feb 6 '11 at 21:44
Ah, I didn't know it was so common a problem. Thanks. –  AnonymousCoward Feb 6 '11 at 21:45
add comment

marked as duplicate by Marvis, Qiaochu Yuan May 5 '12 at 19:59

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

2 Answers

up vote 5 down vote accepted

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$

share|improve this answer
Ah, the corollary is much more useful for my actual problem that this was related to. –  AnonymousCoward Feb 6 '11 at 22:02
add comment

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

share|improve this answer
This is sometimes called the de Polignac's formula. –  Srivatsan Jul 30 '11 at 7:06
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.