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.

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

share|improve this question
    
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

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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