MathDB
GCD and Binomial Divisibility

Source: 2018 VTRMC P4

January 8, 2023
number theorygreatest common divisorbinomial coefficientsVTRMCcollege contests

Problem Statement

Let m,nm, n be integers such that n≥m≥1n \geq m \geq 1. Prove that gcd(m,n)n(nm)\frac{\text{gcd} (m,n)}{n} \binom{n}{m} is an integer. Here gcd\text{gcd} denotes greatest common divisor and (nm)=n!m!(n−m)!\binom{n}{m} = \frac{n!}{m!(n-m)!} denotes the binomial coefficient.
Back to ProblemsView on AoPS