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