Let p be prime and 1 <= k < p. Prove that p divides the binomial coefficient C(p, k)?

The hint for this problem is that C(p, k) = p!/(k!(p-k)!).

Also, I think I'm using the right form for C(p, k) but if not I mean "p choose k"

4 Answers

  • Favorite Answer

    C(p,k) = p! / k! (p-k)!. So C(p,k) k! (p-k)! = p!. Consider the unique factorization in prime numbers of C(p,k) k! (p-k)! = p!. The prime factors of C(p,k) k! (p-k)! are the prime factors of C(p,k) together with the prime factors of k! and the prime factors of (p-k)! The prime factor p must belong to C(p,k) because it does not belong to k! or (p-k)!

    Edit: I used the well known fact that C(p,k) is an integer and the fact that the prime factors of k! (p-k)! are smaller than p. However, the key ingredient is unique factorization.

    Edit 2: The proof of SC (answerer #2) is not clear because it does not use unique factorization. Without unique factorization, we don't know why the product of p with other factors in the numerator cannot be canceled by a product of factors in the denominator.

  • SC
    Lv 4
    1 decade ago

    Theorem: For all x,y C(x,y) is an integer

    p! = p*(p-1)*(p-2) --> larges factor of p! is p

    and similar for k! and (p-k)!

    if p is prime, then the only numbers that can divide p is p and 1. Dividing by 1 is trivial, and dividing by p is impossible because the maximum divisors are k and (p-k) which can never reach p

    1 <= k < p

    0 < p-k <= p-1 < p

  • 4 years ago

    properly, permit ok = a million. Then we get (p-a million)Ck = (p-a million)C1 = p-a million ? -a million (mod p). Assuming this is actual for some ok < (p-a million)... (p-a million)C(ok+a million) ? (p-a million)! / ( (p-a million-ok-a million)! (ok+a million)! ) ? (p-a million)! / ( (p-a million - ok)! ok! ) * (p-a million-ok)/(ok+a million) ? (p-a million)Ck * (p-(ok+a million)) / (ok+a million) ? (-a million)^ok * -(ok+a million)/(ok+a million) ? (-a million)^(ok+a million) the place the final congruence is valid considering the fact that dividing via (ok+a million) is wise whilst p is a chief. via induction, this shows that we've (p-a million)Ck ? (-a million)^ok (mod p) for each ok such that a million<=ok<=(p-a million).

  • Anonymous
    6 years ago

    I hope this will help

    Attachment image
Still have questions? Get your answers by asking now.