Results 1 to 5 of 5

Math Help - Prime number and bonmial coefficient

  1. #1
    Junior Member
    Joined
    Apr 2008
    From
    Gainesville
    Posts
    68

    Prime number and bonmial coefficient

    Let p>0 be a prime number. prove that p divides the binomial coefficient

    (p i)= p!/i!(p-i)! for each integer 0<i<p.

    ( p over i ) = P factorial over i factorial times (p minus i) factorial.

    and use that to show that (a + b)^p= a^p+ b^p mod p
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,705
    Thanks
    1637
    Awards
    1
    For the first part note that (p!)=p[(p-1)!] and \left( {p - 1} \right)! = \prod\limits_{i = 1}^{p - 1} i .
    The result follows from those two observations.

    Then note that \left( {a + b} \right)^p  = \sum\limits_{k = 0}^p {\binom{p}{k}}  a^k b^{p - k}  = a^p  + b^p  + \sum\limits_{k = 1}^{p - 1} {\binom{p}{k}} a^k b^{p - k}
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Apr 2008
    From
    Gainesville
    Posts
    68

    prime numer and binomail coefficient

    I am really thankful for the hints but i still cant go further with
    shown observations. I would appreciate a little more elaboration. Thanks.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello,

    To continue what Plato said, you should also know that a prime number has only 2 divisors : 1 and himself. Hence every integer in \{2, 3, \dots, p-1 \} won't divide p.

    So within the factors of i!=2 \times 3 \times 4 \times \dots \times i, knowing that i<p, is there any divisor of p ?
    Within the factors of (p-i)!, knowing that p-i<p, is there any divisor of p ?


    You can imagine that "p remains as a unique element and won't be divided/separated by anything in the denominator".


    And I think that a bit of Gauss's lemma can help for the formal demonstration...
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by JCIR View Post
    I am really thankful for the hints but i still cant go further with
    shown observations. I would appreciate a little more elaboration. Thanks.
    You have to prove that p|{p \choose k}(like Moo did), then you can continue in Plato's argument:
    \left(\sum\limits_{k = 1}^{p - 1} {\binom{p}{k}} a^k b^{p - k}\right) \,\, mod \, p = 0 ---------------------since p|{\binom{p}{k}}
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: September 24th 2011, 11:23 AM
  2. Replies: 2
    Last Post: July 14th 2010, 02:16 PM
  3. Replies: 6
    Last Post: September 28th 2009, 04:16 PM
  4. Replies: 1
    Last Post: September 2nd 2009, 08:31 AM
  5. Number theory, prime number
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 17th 2006, 08:11 PM

Search Tags


/mathhelpforum @mathhelpforum