Discrete math - binomial coefficients

Question

show that C(p,1), C(p,2),..., C(p,p-1) are all divisible by p if and only if p is a prime

Answer 1

(⇒)

First let us show that if p is prime, then p divides C(p, n) for 0 < n < p.

By definition

C(p, n) = p·(p-1)·(p-2)· ... ·(p-n+1)/n!

It suffices to show that p does not divide (n!), ie n! ≠ m·p, since that would be the only way to cancel out the p in the numerator of C(p, n). If the p in the numerator isn't canceled, then C(p, n) is a multiple of p.

Euclid's lemma states that if p divides ab, then p divides a or p divides b. The contrapositive to this says that if p does not divide a and p does not divide b, then p does not divide ab.

Clearly p does not divide any of n, n-1, n-2, ... therefore p does not divide (n!).

(⇐)

To show that if C(p, n) is divisible by p for all 0 < n < p, then p is prime, we will prove the contrapositive statement: if p is not prime, then there exists an n with 0 < n < p and such that p does not divide C(p, n).

If p is not prime, then p = ab with a, b > 1 and coprime (or we can just assume that b is prime). Let us look at C(p, a):

C(p, a) = ab·(ab-1)·(ab - 2)· ... ·(ab-a+1)/a!

if we cancel the a in the numerator and the denominator, we get

C(p, a) = b·(ab-1)·(ab - 2)· ... ·(ab-a+1)/(a - 1)!

We note that a does not divide any of the (ab - 1), (ab - 2), ..., (ab - a + 1) since we have

(ab - 1) = a(b-1) + (a -1), and so (ab - 1) divided by a gives remainder (a - 1)

(ab - 2) = a(b-1) + (a - 2), and so (ab - 2) divided by a gives remainder (a - 2)

...

(ab - a + 1) = a(b-1) + 1, and so (ab - a + 1) divided by a gives remainder 1.

Now it suffices to show that a does not divide the numerator. To see this we use the contrapositive of Euclid's lemma once again. Since a does not divide b (because they are coprime), and a does not divide any of the (ab - 1), (ab - 2), ..., (ab - a + 1), then a does not divide the numerator.