## 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.