Divisibility of Binomial Coefficients

[riemann75024]

Hi all,

I am trying to figure out if there is a pre-existing theorem and proof of whether or not each of the binomial coefficients in a binomial expansion of (a +b)^n are divisible by n, particularly in the case where n is a prime number.

Has this already been asked and answered somewhere in the mathematics world? I am hoping this is already out there and if someone could point me to the theorem and its proof. If not, then perhaps it is something that can be easily proven? Any thoughts appreciated, thanks! My last university mathematics class was 20 years ago so needless to say I am kind of rusty :D

 

[chisigma]

Re: ??Divisibility of Binomial Coefficients??

Hi all,

I am trying to figure out if there is a pre-existing theorem and proof of whether or not each of the binomial coefficients in a binomial expansion of (a +b)^n are divisible by n, particularly in the case where n is a prime number.

Has this already been asked and answered somewhere in the mathematics world? I am hoping this is already out there and if someone could point me to the theorem and its proof. If not, then perhaps it is something that can be easily proven? Any thoughts appreciated, thanks! My last university mathematics class was 20 years ago so needless to say I am kind of rusty :D

Is $\displaystyle \binom {n}{k} = \frac{n\ (n-1)... (n-k+1)}{k!}$ so that $\displaystyle \binom{n}{k}$ is divisible by n with only two exceptions: k=0 and k=n...

Kind regards

$\chi$ $\sigma$

 

[riemann75024]

Re: ??Divisibility of Binomial Coefficients??

Is $\displaystyle \binom {n}{k} = \frac{n\ (n-1)... (n-k+1)}{k!}$ so that $\displaystyle \binom{n}{k}$ is divisible by n with only two exceptions: k=0 and k=n...

Kind regards

$\chi$ $\sigma$

I see the k=0 case, but the k=n case is not immediately clear to me. Do you mean that when k=n one of the terms in the numerator is 0, and thus we have something like 0/k!? Sorry if I am missing something painfully obvious or basic…

 

[chisigma]

Re: ??Divisibility of Binomial Coefficients??

I see the k=0 case, but the k=n case is not immediately clear to me. Do you mean that when k=n one of the terms in the numerator is 0, and thus we have something like 0/k!? Sorry if I am missing something painfully obvious or basic…

For k=n is $\displaystyle \binom{n}{k}= \frac{n!}{n!}= 1$...

Kind regards

$\chi$ $\sigma$

 

[riemann75024]

Re: ??Divisibility of Binomial Coefficients??

For k=n is $\displaystyle \binom{n}{k}= \frac{n!}{n!}= 1$...

Kind regards

$\chi$ $\sigma$

Ok I see that now, thank you!

But one more question then, when the "n" in my original example is a prime number does that make a difference, ignoring the first and last coefficients? In other words, if you take an example of n being non-prime, such as n=6, then the coefficients are 1,6,15,20,25,6,1, and so only two of the coefficients are divisible by the "n". But if you look at a prime n such as n=7, then you have coefficients of 1,7,21,35,35,21,7,1 - ALL of which are divisible by the prime "n" - except for the very first and last coefficients which are the cases you pointed out in your original reply. So, a follow up question then is for all such prime n's greater than 1, would all the coefficients between the first and last be divisible by that "n"? Thanks!

 

[chisigma]

Re: ??Divisibility of Binomial Coefficients??

Ok I see that now, thank you!

But one more question then, when the "n" in my original example is a prime number does that make a difference, ignoring the first and last coefficients? In other words, if you take an example of n being non-prime, such as n=6, then the coefficients are 1,6,15,20,25,6,1, and so only two of the coefficients are divisible by the "n". But if you look at a prime n such as n=7, then you have coefficients of 1,7,21,35,35,21,7,1 - ALL of which are divisible by the prime "n" - except for the very first and last coefficients which are the cases you pointed out in your original reply. So, a follow up question then is for all such prime n's greater than 1, would all the coefficients between the first and last be divisible by that "n"? Thanks!

The fact that $\displaystyle n| \binom{n}{k}$ for all k with the exceptions of k=0 and k=n holds for all n, primes or non primes...

Kind regards

$\chi$ $\sigma$

 

[riemann75024]

Re: ??Divisibility of Binomial Coefficients??

The fact that $\displaystyle n| \binom{n}{k}$ for all k with the exceptions of k=0 and k=n holds for all n, primes or non primes...

Kind regards

$\chi$ $\sigma$

But I'm not looking to see if n is divisible by $\displaystyle\binom{n}{k}$, but rather if $\displaystyle\binom{n}{k}$ is divisible by n when n is prime for each k, because $\displaystyle\binom{n}{k}$ is not divisible by n for each k when n is not prime as my example of n=6 indicates.

 

[Evgeny.Makarov]

Re: ??Divisibility of Binomial Coefficients??

The fact that $\displaystyle n| \binom{n}{k}$ for all k with the exceptions of k=0 and k=n holds for all n, primes or non primes...

But I'm not looking to see if n is divisible by $\displaystyle\binom{n}{k}$, but rather if $\displaystyle\binom{n}{k}$ is divisible by n when n is prime for each k

The notation m | n means that m divides n, not that m is divisible by n (the latter is sometimes denoted by m ⋮ n).

$\displaystyle\binom{n}{k}$ is not divisible by n for each k when n is not prime as my example of n=6 indicates.

You are absolutely right. See Wikipedia for the proof of the following fact.

An integer $n\ge 2$ is prime if and only if all the intermediate binomial coefficients

\[\binom n 1,\binom n 2, \ldots, \binom n{n-1}\]

are divisible by $n$.

Look for the phrase "Another fact:", though what comes before is also relevant.

 

[johng1]

Hi,
I looked at the Wikipedia article, but I like my "proof" better.

Let p be a prime and $$1\leq k<p$$. Then $$k!\binom {p}{k}=p(p-1)\cdots (p-k+1)$$. So p divides $$k!\binom {p}{k}$$. Since p does not divide k!, p does divide $$\binom {p}{k}$$