# divisibility of binomial coefficients by primes

If $p$ is a prime number and $r = 1,2,3 \dots ,p -1$, how can I prove that the binomial coefficients $_nC_r(p,r)$ are divisible by $p$? By divisible I mean $_nC_r(p,r)/p$ leaves remainder $0$.

oivind

-
Look for Lucas's theorem –  Dilip Sarwate May 25 '12 at 16:42

Let $p$ be prime. I assume that you are asking why $\binom{p}{r}$ is divisible by $p$ for $r=1,2,\dots,p-1$. Instead of ${}_pC_r$, I will use the notation $\binom{p}{r}$.

Let $N=\binom{p}{r}$. Then $$N=\frac{p!}{r!(p-r)!},\quad \text{or equivalently}\quad p!=Nr!(p-r)!.$$

Clearly $p$ divides $p!$. Thus $p$ divides $Nr!(p-r)!$. But if a prime divides a product, then it divides at least one of the terms. Since $p$ cannot divide $r!$ or $(p-r)!$, it must divide $N$.

-

Another way: there is an action of $\mathbb{Z}_p$ on the sets of size r. It's easy to see that if r is as you required then there are no fixed points of this action,and,being an action of a p-group on a finite set,you have that mod p the size of the set and number of fixed points are equal. So you have your divisibility relation. Note that using this congruence you can also prove Fermat little theorem,but by the way you can also prove it in the same way as this:you can see that $\mathbb{Z}_p$ acts on the set of function from a set of p elements to a set of a elements,whose size is $a^p$, and it's easy to see that only the constants are the fixed points of this action,and there are a of them. Then using the above result againg you have that $a^p=a mod p$

Edit:Ok i will explain in more detail it. Take a set A in $\mathbb{Z}_p$. Take j in $\mathbb{Z}_p$,then consider the set j+A. This defines an action of $\mathbb{Z}_p$ on the subsets of $\mathbb{Z}_p$. Of course sets of size r are sent in sets of size r. Then this defines an action of $\mathbb{Z}_p$ on the sets of size r. This gives you a decomposition of them in orbits. By orbit stabilizer lemma each orbit has a lenght that divides p. Then it has to be 1 or p. If is p modp is as 0, then you can count mod p just the fixed points(orbit of size 1). But it's clear that a set of size r, with $1<r<p$ cannot be fixed by all translations,then there are no fixed points,so the orbits are all long p,then their sum(that gives you the binomial)is 0 mod p. In a very similar way you argue about the following action on functions,given j in $\mathbb{Z}_p$ f from $\mathbb{Z}_p$ to a set of size a you send in f(x+j). You can check that a function is fixed by such an action just if it is constant,so for the same reason i've explained above, you have number of functions=constant function(mod p) that translated numerically gives you Fermat theorem(that can be anyway catched from the above binomial congruence by induction)

-
Could you explain your answer in a little more detail? –  Dilip Sarwate May 25 '12 at 20:30
Tell me if now is clearer –  Piton May 25 '12 at 21:48