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

$\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,

$\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$.