Why is ${n\choose k}$ is always a product of the primes of $n$ for all $n>k$?

Question

Let $n, k$ be two positive integers such that $n>k$. Why is ${n\choose k}$ always divisible by a prime dividing $n$ (or even a product of such primes)? Please help me understand why. I cannot seem to wrap my mind around it. For instance, $ 30 \choose k $ is divisible by either $2,3,5$ or a product of those numbers: $$2\cdot3=6$$ $$2\cdot5=10$$ $$3\cdot5=15$$ etc.

Answer 1

If $p$ is a prime, then \begin{align*} \binom{pr}{ps} &\equiv \binom rs \pmod p \\ \text{and}\qquad \binom{pr}{s} &\equiv 0 \pmod p \qquad\text{if $p\nmid s$.} \end{align*} Applying this to your situation: since $n>k>0$, there is a prime $p$ that divides $n$ with higher exponent than it divides $k$; applying the first fact iteratively we can reduce to the case where $p$ doesn't divide $k$ at all, and in that case the second fact shows that $p$ divides the binomial coefficient too. For example, for $\binom{120}{60}$: $$ \binom{120}{60} = \binom{2\cdot2\cdot2\cdot15}{2\cdot2\cdot 15} \equiv \binom{2\cdot2\cdot15}{2\cdot15} \equiv \binom{2\cdot 15}{15} \equiv 0 \pmod 2 $$

As Jyrki pointed out in comments, the two facts above are consequences of Lucas' theorem; see this answer for a proof. (And here's a combinatorial proof (pdf, 3 pages) I wrote up a few years ago.)

Answer 2

Let $X$ denote the set of all size-$k$ subsets of $\{1, ..., n\}$, where $0 < k < n$. Then $C_n$, the cyclic group of order $n$, acts on $X$ via its action on $\{1, ..., n\}$. Consider the stabiliser $G$ of an element $A$ of $X$. This is a subgroup of $C_n$, so $|G|$ is a factor of $n$. But $G$ also acts on $A$, so $|G|$ is also a factor of $k$; thus, $|G|$ is a factor of $\gcd\{n, k\}$. So by orbit-stabiliser, $|Orb_{C_n}(A)| = |C_n|/|G|$ is divisible by $n/\gcd\{n, k\}$. But this is true for any $A$, and since $X$ is the disjoint union of the orbits of the action by $C_n$, $|X|$ is divisible by $n/\gcd\{n, k\}$.

Finally, since $k < n$, $\gcd\{n, k\} < n$, and so $n/\gcd\{n, k\}$ is a factor of $n$ greater than $1$ which divides $|X| = {n\choose k}$.