How can we prove that a binomial coefficient $n\choose m$is divisible by the ratio of $n$ and $\gcd(n,m)$?

Write $nx+my=\gcd(n,m)$, with $x,y\in\mathbb{Z}$

Then:

$$\frac{\gcd(n,m)}{n}\binom{n}{m}=\frac{nx+my}{n}\binom{n}{m}=x\binom{n}{m}+y\,\frac{m}{n}\binom{n}{m}=x\binom{n}{m}+y\binom{n-1}{m-1}\in\mathbb{Z}$$

Here is a conceptual way to derive this. We will show that it is a special case of the well-known fact that if a fraction $q\,$ can be written with denominators $\,n\,$ and $\,m,\,$ then it can also be written with denominator $\,\gcd(n,m),\,$ i.e. $\, nq,\,mq\in\Bbb Z\,\Rightarrow\, (n,m)q\in\Bbb Z.\,$ Applied to $\ \color{#c00}q = \frac{1}{n}{n\choose m}\, $

$$n\color{#c00}q = {n\choose m}^{\vphantom{|^{|^|}}}\in\Bbb Z,\,\ m\color{#c00}q= {n\!-\!1\choose m\!-\!1}\in\Bbb Z\,\ \Rightarrow\ (n,m)q = \dfrac{(n,m)}n{{{n\choose m}}}\in \Bbb Z\quad\qquad$$

---

Remark $\ $ Below are a few proofs of the Lemma on fractions. Recall $\,(x,y):=\gcd(x,y)$

$(1)\ $ Recall that a fraction can be written with denominator $\,n\,$ iff its least denominator $\,d\mid n.\,$ Therefore $\,m,n\,$ are denoms $\iff d\mid m,n\iff d\mid (m,n)\iff (m,n)\:$ is a denom.

$(2)\ \ \dfrac{mc}d,\dfrac{nc}d\in\Bbb Z\iff d\mid mc,nc\iff d\mid (mc,nc)=(m,n)c\iff\! \dfrac{(m,n)c}d\in\Bbb Z$

$(3)\ \ \dfrac{mc}d, \dfrac{nc}d\in\Bbb Z\,\Rightarrow \dfrac{jmc}d,\, \dfrac{knc}d\in\Bbb Z\,\Rightarrow\,\dfrac{(jm\!+\!kn)c}d\,\overset{\large \color{#c00}{\exists\, j,k}_{\phantom{1^{1^{1}}\!\!\!\!\!}}} = \dfrac{(m,n)c}d\in\Bbb Z\ $ by $\rm\color{#c00}{Bezout}$