Some Divisibility Properties of the Binomial Coefficients

Recently I read in Koshy’s book [1] on Catalan numbers some divisibility properties of the binomial coefficients I had not seen before.  Koshy credits them to Hermite.   They are particularly interesting to me because (as Koshy notes) some of the most famous divisibility properties of the binomial coefficients are immediate corollaries.  This post will give proofs of Hermite’s properties (following those in Koshy) and discuss the corollaries.

Divisibility properties.  Let m, n \geq 1.  Let (m,n) denote the greatest common divisor of m and n.  Then

(1) \displaystyle \binom{m}{n} is divisible by \displaystyle \frac{m}{(m,n)}, and

(2) \displaystyle \binom{m}{n} is divisible by \displaystyle \frac{m-n+1}{(m+1,n)}.

Proofs

(1)  Let d = (m,n).  By the Euclidean algorithm, there exist integers A and B such that d = Am + Bn.  Thus

\displaystyle d \binom{m}{n} = A m \binom{m}{n} + Bn \binom{m}{n} = A m \binom{m}{n} + B m \binom{m-1}{n-1}, by the absorption identity.  Then

\displaystyle d \binom{m}{n} = m \left[ A \binom{m}{n} + B \binom{m-1}{n-1} \right] = mC, where C is an integer.

Thus \displaystyle \frac{m}{d} divides \displaystyle \binom{m}{n}.  In other words, \displaystyle \frac{m}{(m,n)} divides \displaystyle \binom{m}{n}.

(2)  Let d = (m+1,n).  Then there exist integers P and Q such that d = P(m+1) + Qn = (m-n+1)P + n(P+Q).  Thus

\displaystyle d \frac{m!}{n! \, (m-n+1)!} = \binom{m}{n} P + \binom{m}{n-1} (P+Q).

Let \displaystyle R = \binom{m}{n} P + \binom{m}{n-1}(P+Q).  Clearly R is an integer.  Then we have

\displaystyle d \binom{m}{n} = (m-n+1) R.

Thus \displaystyle \frac{m-n+1}{d} divides \displaystyle \binom{m}{n}.  In other words, \displaystyle \frac{m-n+1}{(m+1,n)} divides \displaystyle \binom{m}{n}.

Corollaries

  1. The central binomial coefficient \displaystyle \binom{2n}{n} is even.
    1. Proof:  The greatest common divisor of 2n and n is n.  From Divisibility Property (1), \displaystyle \binom{2n}{n} is divisible by 2n/n = 2.
  2. The Catalan number C_n = \binom{2n}{n}/(n+1) is an integer.
    1. Proof:  The greatest common divisor of 2n+1 and n is 1.  By Divisibility Property (2), \displaystyle \binom{2n}{n} is divisible by n+1.
  3. For p prime and values of n with 1 \leq n \leq p-1\displaystyle \binom{p}{n} is divisible by p.
    1. Proof:  For values of n with 1 \leq n \leq p-1, the greatest common divisor of p and n is 1.  By Divisibility Property (1), \displaystyle \binom{p}{n} is divisible by p.

References

1. Thomas Koshy, Catalan Numbers with Applications, Oxford University Press, 2009.

Advertisements
This entry was posted in binomial coefficients, elementary number theory. Bookmark the permalink.

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