Putnam 2000, Problem B-2

Prove that the expression
$$\frac{\gcd(m,n)}{n} \binom{n}{m}$$
is an integer for all pairs of integers $n \geq m \geq 1$.

Solution:
Since \(\gcd(m,n)\) is an integer linear combination of \(m\) and \(n\), it follows that  
\[
\frac{\gcd(m,n)}{n} \binom{n}{m}
\]  
is an integer linear combination of the integers  
\[
\frac{m}{n} \binom{n}{m} = \binom{n-1}{m-1} \quad \text{and} \quad \frac{n}{n} \binom{n}{m} = \binom{n}{m}
\]  
and hence is itself an integer.