Results 1 to 5 of 5

Math Help - Binomial Coefficients

  1. #1
    Member
    Joined
    Jun 2007
    Posts
    77

    Binomial Coefficients

    Show that if p is a prime and k is an integer such that  1 \leq  k \leq p-1, then p divides  \binom p k
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,212
    Thanks
    419
    Awards
    1
    Quote Originally Posted by EquinoX View Post
    Show that if p is a prime and k is an integer such that  1 \leq  k \leq p-1, then p divides  \binom p k
    Here's the basic idea. You can put this more exact language as you please.
    \binom p k = \frac{p!}{k!(p - k)!}

    Since p is prime, no number n \leq k nor any number n \leq p - k divides p. Thus no matter what cancellations we have in simplifying the factorials a p remains in the numerator. etc, etc.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jun 2007
    Posts
    77
    Okay I kind of get your idea here, because p here is prime in the numerator, but nothing in the denominator can divide p because p is a prime, therefore p still exists after the counting and because p still exists therefore it can be divided by p? right
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,212
    Thanks
    419
    Awards
    1
    Quote Originally Posted by EquinoX View Post
    Okay I kind of get your idea here, because p here is prime in the numerator, but nothing in the denominator can divide p because p is a prime, therefore p still exists after the counting and because p still exists therefore it can be divided by p? right
    That is correct.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by EquinoX View Post
    Show that if p is a prime and k is an integer such that  1 \leq  k \leq p-1, then p divides  \binom p k
    When I was much younger I found a proof of Fermat's Little Theorem using the following observation:

    "Every n-th number is divisible by n".

    Now, {p\choose k}=\frac{p(p-1)...(p-k+1)}{k!}

    We want to show that,
    \frac{p(p-1)...(p-k+1)}{pk!} = \frac{(p-1)...(p-k+1)}{k!}
    Is an integer.

    Now p is not a 2-th number, nor a 3-rd number , ... , nor a k-th number. Hence one of those numbers: (p-1),...,(p-k+1) and one of those is a k-1-th thus,
    \frac{(p-1)(p-2)...(p-k+1)}{k!} is an integer.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Binomial Coefficients
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 1st 2010, 07:24 PM
  2. Binomial coefficients?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 23rd 2009, 10:00 AM
  3. Binomial coefficients
    Posted in the Algebra Forum
    Replies: 1
    Last Post: February 25th 2009, 06:18 PM
  4. Binomial Coefficients
    Posted in the Algebra Forum
    Replies: 2
    Last Post: April 16th 2008, 08:04 AM
  5. Binomial coefficients
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: April 5th 2008, 12:21 PM

Search Tags


/mathhelpforum @mathhelpforum