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

1. ## 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!

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

Originally Posted by VinceW
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)

3. ## 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].

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

Originally Posted by Also sprach Zarathustra
Look at k! (pCk)
remember that if p|ab and p∤a, then necessarily p|b.