3
$\begingroup$

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

  • 0
    I have heard this result attributed to Kronecker. You can prove it by computing the power of $p$ dividing a factorial.2012-02-20

1 Answers 1

2

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.

A full answer is here.

  • 0
    @Victor See also [this prior question.](http://math.stackexchange.com/questions/20737/prime-powers-that-divide-a-factorial) Also googling "power of prime divid factorial" finds many proofs. But you'll learn better if you discover it yourself - it's not hard.2012-02-20