# divisibility of binominal coeffisients

• May 25th 2012, 06:01 AM
oeivinr
divisibility of binominal coeffisients
Hi,

If p is a prime number and r = 1,2,3 ...p -1, how can I prove that the binominal coeffisients nCr(p,r) are divisible by p? By divisible I mean nCr(p,r)/p leaves remainder 0.

oivind
• May 25th 2012, 07:02 AM
Plato
Re: divisibility of binominal coeffisients
Quote:

Originally Posted by oeivinr
If p is a prime number and r = 1,2,3 ...p -1, how can I prove that the binominal coeffisients nCr(p,r) are divisible by p? By divisible I mean nCr(p,r)/p leaves remainder 0.

If $p$ is a prime and $1 then because $r\not | ~p$. WHY?

Moreover, $p$ is always a factor of $p!$. So you are almost done.

Finish?
• May 25th 2012, 09:26 AM
oeivinr
Re: divisibility of binominal coeffisients
Thanx for answering. Of course p is a factor of p!, but not necessarily of nCr(p,r). To be a factor of nCr(p,r) it has to devide nCr(p,r) exactly, that is division by p will give an integer as an answer. e.g. nCr(11,3) =165 and 11 devides 165 exactly 165/11 = 15. This holds only for primes in the formulae nCr(p,r) not for composites e.g. nCr(6,2) = 15 but 6 does not divide 15 exactly 15/6 =2.5

I understand that r does not devide p. A prime is only divisible (exactly) by 1 and itself, but I don't quite see the relevance of this fact to my question.
• May 25th 2012, 09:45 AM
Plato
Re: divisibility of binominal coeffisients
Quote:

Originally Posted by oeivinr
If p is a prime number and r = 1,2,3 ...p -1, how can I prove that the binominal coeffisients nCr(p,r) are divisible by p? By divisible I mean nCr(p,r)/p leaves remainder 0

Look at what you posted.
nCr(p,r) [/SIZE]are divisible by p. Where does n come from? You said nothing about it anywhere. Now you need to learn to post what you mean.

Quote:

Originally Posted by oeivinr
Thanx for answering. Of course p is a factor of p!, but not necessarily of nCr(p,r). To be a factor of nCr(p,r) it has to devide nCr(p,r) exactly, that is division by p will give an integer as an answer. e.g. nCr(11,3) =165 and 11 devides 165 exactly 165/11 = 15. This holds only for primes in the formulae nCr(p,r) not for composites e.g. nCr(6,2) = 15 but 6 does not divide 15 exactly 15/6 =2.5 I understand that r does not devide p. A prime is only divisible (exactly) by 1 and itself, but I don't quite see the relevance of this fact to my question.

If $r=2,~3,~\dots~10$ then $11~|~\binom{11}{r}$. That is what you put in your OP.

If that is not the question then why did you post it that way?
• May 25th 2012, 10:41 AM
oeivinr
Re: divisibility of binominal coeffisients
Sorry, my notation was a bit sloppy. What I meant by nCr was "n choose r" from combinatorics. Perhaps I should have used the alternative notation , C(p,r), instead. The number of combinations of selecting several things, r, out of a larger group. p.
• May 25th 2012, 11:15 AM
Plato
Re: divisibility of binominal coeffisients
Quote:

Originally Posted by oeivinr
Sorry, my notation was a bit sloppy. What I meant by nCr was "n choose r" from combinatorics. Perhaps I should have used the alternative notation , C(p,r), instead. The number of combinations of selecting several things, r, out of a larger group. p.

$C(n,r)=\binom{n}{r}=\frac{n!}{r! (n-r)!}$ is the mathematical way to do that.

From that notation you can see that if $p$ is prime and $1 where $r\in\mathbb{Z}^+$
then it is true that $p$ divides $\binom{p}{r}$.