POTW Submission POTW Suggestion Math Guides and Tutorials Latest reviews Search resources
University Math
Other University Math Topics
Be a part of something great, join today!
Number Theory Divisibility of Binomial Coefficients
Thread starter riemann75024
riemann75024
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
chisigma
Re: ??Divisibility of Binomial Coefficients??
riemann75024 said:
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...
$\chi$ $\sigma$
chisigma said:
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$...
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...
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
MHB Math Scholar
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.
MHB Math Helper
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}\)
Facebook Twitter Email Link
Advanced Forum Stats, Awards System by AddonFlare - Premium XF2 Addons