Prove that an integer n>1 is a prime if and only if all of the binomial coefficients C(n,k) (1<k<n) are divisible by n

Question

Prove that an integer n>1 is a prime if and only if all of the binomial coefficients C(n,k) (1<k<n) are divisible by n

Answer 1

I'll get you part way there. 

 

You need to prove 2 things:

 

(a) if n is prime then n divides all binomial coefficients C(n,k) with 1<k<n

 

(b) if n divides all C(n,k) (1<k<n) then n is prime

 

I'll do (a): we know C(n,k) = n! / (k!)(n-k!)       (1)

 

                since k<n  and n is prime n does not appear as a factor in the denominator in (1)

                therefore when C(n,k) is calculated the n in it's numerator is never cancelled (since it's prime it

                can only be cancelled by n) hence the resulting value is always divisible by n

 

          (b)  can you try some similar reasoning here; if you can't show it directly perhaps try the contrapositive 

 

Answer 2

Let n>1 and 0<k<n.

 

⇒

Clearly n divides into n!

 

If n is prime, then by Euclid's Lemma, n can't divide k! or (n-k)!

 

Thus since C(n,k) = n!/[k!(n-k)!] is an integer and so n must divide into it.

 

⇐

 

We prove the contrapositive here.

 

If n is composite, let p be a prime factor so that n=ap^m  and p does not divide into a.

 

Then by the Team-Captain identity, p·C(ap^m,p) = ap^m·C(ap^m-1,p-1).

 

This becomes C(n,p) = ap^m-1·C(ap^m-1,p-1).

 

p does not divide into (ap^m - 1)!/(ap^m - p)! by Euclid's Lemma, as this is aproduct of p-1 consecutive integers that are not divisible by p.

 

So it also doesn't divide into C(ap^m-1,p-1).

 

Thus p^m doesn't divide into C(n,p).

 

Thus C(n,p) is not divisible by n.