Results 1 to 5 of 5

Thread: 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 $\displaystyle 1 \leq k \leq p-1$, then p divides $\displaystyle \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
    11,130
    Thanks
    723
    Awards
    1
    Quote Originally Posted by EquinoX View Post
    Show that if p is a prime and k is an integer such that $\displaystyle 1 \leq k \leq p-1$, then p divides $\displaystyle \binom p k $
    Here's the basic idea. You can put this more exact language as you please.
    $\displaystyle \binom p k = \frac{p!}{k!(p - k)!}$

    Since p is prime, no number $\displaystyle n \leq k$ nor any number $\displaystyle 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
    11,130
    Thanks
    723
    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 $\displaystyle 1 \leq k \leq p-1$, then p divides $\displaystyle \binom p k $
    When I was much younger I found a proof of Fermat's Little Theorem using the following observation:

    "Every $\displaystyle n$-th number is divisible by $\displaystyle n$".

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

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

    Now $\displaystyle p$ is not a $\displaystyle 2$-th number, nor a $\displaystyle 3$-rd number , ... , nor a $\displaystyle k$-th number. Hence one of those numbers: $\displaystyle (p-1),...,(p-k+1)$ and one of those is a $\displaystyle k-1$-th thus,
    $\displaystyle \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: Feb 1st 2010, 06:24 PM
  2. Binomial coefficients?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Apr 23rd 2009, 09:00 AM
  3. Binomial coefficients
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Feb 25th 2009, 05:18 PM
  4. Binomial Coefficients
    Posted in the Algebra Forum
    Replies: 2
    Last Post: Apr 16th 2008, 07:04 AM
  5. Binomial coefficients
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: Apr 5th 2008, 11:21 AM

Search Tags


/mathhelpforum @mathhelpforum