It is an integer

Prove that the expression

$$\frac{\gcd(m,n)}{n} \binom{n}{m}$$

is an integer, where $m, n \in \mathbb{N}$.

Solution

First of all from theory it holds that:

$$\gcd(m,n)= xm +n y , \;\; x, y \in \mathbb{Z}$$

thus:

$$\frac{\gcd(m,n)}{n}\binom{n}{m}= y\binom{n}{m}+ x \frac{m}{n} \binom{n}{m}$$

However,

\begin{align*}
\frac{m}{n}\binom{n}{m} &=\frac{m}{n} \frac{n!}{m! \left ( n-m \right )!} \\
 &=\frac{(n-1)!}{(m-1)!\left ( n-m \right )!} \\
 &= \binom{n-1}{m}
\end{align*}

and the result follows.