Welcome to our community

Be a part of something great, join today!

Number Theory Divisibility of Binomial Coefficients

riemann75024

New member
Oct 25, 2013
4
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

Well-known member
Feb 13, 2012
1,704
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

New member
Oct 25, 2013
4
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

Well-known member
Feb 13, 2012
1,704
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

New member
Oct 25, 2013
4
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

Well-known member
Feb 13, 2012
1,704
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

New member
Oct 25, 2013
4
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

Well-known member
MHB Math Scholar
Jan 30, 2012
2,502
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.
 

johng

Well-known member
MHB Math Helper
Jan 25, 2013
236
Hi,
I looked at the Wikipedia article, but I like my "proof" better.

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