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"
- 1 decade agoFavorite 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.
- SCLv 41 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
- brunkhorstLv 44 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).
- Anonymous6 years ago
I hope this will help