# Prove or name this identity: the number of factors of $p$ in $\binom{n}{k}$ is $(s_p(k)+s_p(n-k)-s_p(n))/(p-1)$

you can count the number of factors of $p$ that are in $\binom{n}{k}$ for prime $p$. Let $s_p(n)$ be the sum of the digits of $n$ in base $p$. Then, the number of factors of $p$ in $\binom{n}{k}$ is $(s_p(k)+s_p(n-k)-s_p(n))/(p-1)$.

-
I have heard this result attributed to Kronecker. You can prove it by computing the power of $p$ dividing a factorial. –  Qiaochu Yuan Feb 20 '12 at 20:17

It's a corollary of Legendre's 1808 theorem that power of the prime $p$ that divides $n!$ is

$$[n/p] + [n/p^2] + [n/p^3] +\: \cdots\ =\ \frac{n-s_p(n)}{p-1}$$

For this and much more see Andrew Granville's very interesting survey The Arithmetic Properties of Binomial Coefficients.

-
Which chapter can i find my problem? –  Victor Feb 20 '12 at 20:43
Math Gems - How do you prove the theorem you stated? –  Victor Feb 20 '12 at 20:48
@Victor See also this prior question. Also googling "power of prime divid factorial" finds many proofs. But you'll learn better if you discover it yourself - it's not hard. –  Math Gems Feb 20 '12 at 20:52