We have gcd$ (m,n)=Am+Bn$ for some integers $ A,B$. Then note that $ \frac{Am+Bn}{n} {n \choose m}=A{n-1\choose m-1}+B{n\choose m}$.

Fedor Petrov wrote: We have gcd$ (m,n) = Am + Bn$ for some integers $ A,B$. Then note that $ \frac {Am + Bn}{n} {n \choose m} = A{n - 1\choose m - 1} + B{n\choose m}$. Very nice your one-line proof! However, this problem (due to L. Panaitopol) was intended to be solved in this way: Consider some prime $ p$ with its exponent in $ N = \frac{(m, n)}{n} \binom{n}{m}$ equal to $ v_p(N)$. We are to show that $ v_p(N) \ge 0$. By the fact that $ v_p$ is totally additive, $ v_p(N) = v_p((m, n)) - v_p(n) + v_p(n!) - v_p(m!) - v_p((n-m)!)$. Now, by definition $ v_p((m, n)) = \min \{ v_p(m), v_p(n) \}$. Since $ \binom{n}{m}$ is an integer, the case $ v_p(m) \ge v_p(n)$ is trivial. Now assume that $ v_p(n) = v_p(m) + k$, where $ k$ is some positive integer, and denote $ t = v_p(m)$. Thus, $ v_p((m, n)) = v_p(m)$, and by Legendre's theorem, we need to check that $ S = \sum_{j \ge 1} \left( \left\lfloor \frac{n}{p^j} \right\rfloor - \left\lfloor \frac{m}{p^j} \right\rfloor - \left\lfloor \frac{n - m}{p^j} \right\rfloor \right) \ge k$. Now write $ m = q_j \cdot p^j + r_j$ and $ n - m = s_j \cdot p^j + t_j$ with $ q_j, s_j \in \mathbb{Z}$ and $ r_j, t_j \in \overline{0, p^j - 1}$, for all $ j \ge 1$. By the properties of floor function, each term of this sum is non-negative. Hence, $ S = \sum_{j \ge 1} \left\lfloor \frac{r_j + t_j}{p^j} \right\rfloor \ge \sum_{j = t + 1}^{t + k} \left\lfloor \frac{r_j + t_j}{p^j} \right\rfloor$. The problem is finished if we succeed to prove that $ \left\lfloor \frac{r_j + t_j}{p^j} \right\rfloor \ge 1 \Leftrightarrow r_j + t_j \ge p^j$, for any $ j \in \overline{t + 1, t + k}$. Now notice that $ v_p(n) = v_p(m) + k = t + k$ implies $ p^{t + l} | n$, for any $ l \in \overline{1, k}$. So $ n - m = u_j \cdot p^j - q_j \cdot p^j - r_j = (u_j - q_j - 1) \cdot p^j + (p^j - r_j)$, for all $ j \in \overline{t + 1, t + k}$. However, $ r_j = 0$ leads to $ p^{t + l} = p^j | m = p^t \cdot s$, $ (s, p) = 1$, false, so $ r_j \in \overline{1, p^j - 1}$ and thus $ p^j - r_j \in \overline{1, p^j - 1}$. This shows that $ s_j = u_j - q_j - 1$ and $ t_j = p^j - r_j$, so $ r_j + t_j = p^j$, which was to be proved.

Fact: Let x be a rational number, a and b integers with (a,b)=1. Then if ax and bx are integers, then x is an integer. let x=m/n with (m,n)=1, m and n are integers. Then, since ax and bx are integers, n divides both a and b and hence divides (a,b)=1 ,implying that n = plus or minus 1, implying that x is an integer. taking the given expression to be x, and taking a=m/(m,n) , b=n/(m,n) ,we are done .

we rewrite the problem as: let $m,n$ be two co-prime natural numbers that $n>m$ and an arbitrary natural number $d$ then prove $n \mid {dn \choose dm}$. take a prime factor of $n$ like $p$ such as that $||n||_p=\alpha$ then we prove $\alpha \le \sum_{i=0}^{\infty} ([\frac{dn}{p^i}]-[\frac{dm}{p^i}]-[\frac{dn-dm}{p^i}])$ let $\beta=||d||_p$, and we know $\sum_{i=0}^{\infty} ([\frac{dn}{p^i}]-[\frac{dm}{p^i}]-[\frac{dn-dm}{p^i}]) \ge \sum_{i=\beta+1}^{\alpha+\beta} ([\frac{dn}{p^i}]-[\frac{dm}{p^i}]-[\frac{dn-dm}{p^i}])$ it's easy to see that $\forall i \in \{\beta+1,\beta+2,...,\alpha+\beta\} : [\frac{dn}{p^i}]-[\frac{dm}{p^i}]-[\frac{dn-dm}{p^i}]=1$ because $p^i \mid dn$ $,$ $p^i \nmid dm$ and $p^i \nmid dn-dm$ so we can conclude that $\sum_{i=\beta+1}^{\alpha+\beta} ([\frac{dn}{p^i}]-[\frac{dm}{p^i}]-[\frac{dn-dm}{p^i}])=\alpha \le \sum_{i=0}^{\infty} ([\frac{dn}{p^i}]-[\frac{dm}{p^i}]-[\frac{dn-dm}{p^i}]) $ as we wished