Results 1 to 4 of 4

Math Help - When p is a prime prove that p | {p \choose k}

  1. #1
    Junior Member
    Joined
    Jun 2010
    Posts
    59

    When p is a prime prove that p | {p \choose k}

    If p is a prime where 1 \le k < p, then prove that

    p | {p \choose k}

    This is a standard problem (I googled it and I find other homework assignments), but I'm stuck getting started. Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1

    Re: When p is a prime prove that p | {p \choose k}

    Quote Originally Posted by VinceW View Post
    If p is a prime where 1 \le k < p, then prove that

    p | {p \choose k}

    This is a standard problem (I googled it and I find other homework assignments), but I'm stuck getting started. Thanks!

    Look at k! (pCk)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jun 2011
    Posts
    2

    Re: When p is a prime prove that p | {p \choose k}

    Lucas' Theorem: If p is a prime number, and N has base p representation (aj,...,a1,a0) and k has base p representation (bj,...,b1,b0), then (N CHOOSE k) is congruent [mod p] to


    (aj CHOOSE bj)...(a1 CHOOSE b1)(a0 CHOOSE b0).
    Example: Let N = 588, k = 277, p = 5.
    N = 588 has base 5 representation (4323).
    k = 277 has base 5 representation (2102).
    Thus by Lucas' Theorem, (588 CHOOSE 277) is congruent [mod 5] to

    (4 CHOOSE 2) (3 CHOOSE 1) (2 CHOOSE 0) (3 CHOOSE 2)
    which is 54 = 4 [mod 5].

    Last edited by topsquark; June 16th 2011 at 05:12 AM. Reason: Removed link
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,154
    Thanks
    593

    Re: When p is a prime prove that p | {p \choose k}

    Quote Originally Posted by Also sprach Zarathustra View Post
    Look at k! (pCk)
    remember that if p|ab and p∤a, then necessarily p|b.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: October 22nd 2011, 12:37 PM
  2. Replies: 1
    Last Post: June 19th 2011, 12:56 PM
  3. Replies: 6
    Last Post: August 27th 2010, 11:44 PM
  4. Replies: 3
    Last Post: October 3rd 2009, 05:18 AM
  5. if ((2^n) -1 ) is prime, prove n is prime ?! >.<
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 18th 2009, 01:47 PM

/mathhelpforum @mathhelpforum