Results 1 to 6 of 6

Math Help - divisibility of binominal coeffisients

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    5

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,616
    Thanks
    1579
    Awards
    1

    Re: divisibility of binominal coeffisients

    Quote Originally Posted by oeivinr View Post
    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<r<p-1 then because r\not | ~p. WHY?

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

    Finish?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2009
    Posts
    5

    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,616
    Thanks
    1579
    Awards
    1

    Re: divisibility of binominal coeffisients

    Quote Originally Posted by oeivinr View Post
    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 View Post
    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?
    Last edited by Plato; May 25th 2012 at 10:09 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Nov 2009
    Posts
    5

    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,616
    Thanks
    1579
    Awards
    1

    Re: divisibility of binominal coeffisients

    Quote Originally Posted by oeivinr View Post
    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<r<p where r\in\mathbb{Z}^+
    then it is true that p divides \binom{p}{r}.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. binominal coefficients
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 27th 2010, 05:54 PM
  2. binominal coefficients
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: April 24th 2010, 09:01 AM
  3. Binominal help
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: September 18th 2009, 02:04 AM
  4. binominal expansion
    Posted in the Algebra Forum
    Replies: 1
    Last Post: February 10th 2009, 03:34 AM
  5. binominal probability
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: October 10th 2008, 02:47 PM

Search Tags


/mathhelpforum @mathhelpforum