Number Theory – Proving Binomial Coefficient Divisibility

Question

Prove that for every $n\geq m \geq1$ natural numbers, the following number is an integer:

$${\gcd(n,m)\over n}\cdot{n\choose m}$$

Where $\gcd$ is the greatest common divisor.

I tried to make it simpler by cancelling the $n$ from the left side, and making it $(n-1)!$ on the right: $\gcd(n, m) \cdot \frac{(n-1)!}{m!(n-m)!}$, but can't really go further.

This was problem B-2 on the 2000 Putnam exam.

Answer 1

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}$$