A nice divisibility result on binomial coefficients

I just came across this cute little result on Quora and generalised it to the following.

Proposition. For any integers 0<k\le n,

\displaystyle\frac{n}{(n,k)} divides \displaystyle\binom{n}{k}.

First proof. Note that

\displaystyle \frac{k}{(n,k)}\binom nk=\frac{n}{(n,k)}\binom{n-1}{k-1}.

Since \displaystyle\left(\frac{n}{(n,k)},\frac{k}{(n,k)}\right)=1, the result follows. \square

Second proof. Let n=p_1^{a_1}\cdots p_r^{a_r} and k=p_1^{b_1}\cdots p_r^{b_r} where p_1,\dots,p_r are the prime factors of nk. For each i, the base p_i representations of n and k have a_i and b_i trailing zeros respectively. Hence by Kummer’s theorem p_i^{\max\{a_i-b_i,0\}} divides \displaystyle\binom nk. Hence

\displaystyle k\prod_{i=1}^rp_i^{\max\{a_i-b_i,0\}}=\prod_{i=1}^rp_i^{\max\{a_i,b_i\}}=[n,k]

divides \displaystyle k\binom nk. Now the result follows using [n,k]/k=n/(n,k). \square

A nice corollary is the following property of Pascal’s triangle.

Corollary. For any integers 0<k<n,

\displaystyle\gcd\left(n,\binom nk\right)>1.


Using the identity

\displaystyle\binom nk\binom kr=\binom nr\binom{n-r}{k-r}

the argument in the first proof above can be adapted to prove the following generalisation:

Proposition. For any integers 0\le r\le k\le n,

\displaystyle\frac{\binom nr}{\left(\binom nr,\binom kr\right)} divides \displaystyle\binom{n}{k}.

Corollary. Any two entries \neq 1 in a given row of Pascal’s triangle have a common factor >1.

Advertisements

Leave a comment

Filed under Number theory

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s