Easy proof: $\binom{n}{k}$ is divisible by $n$ for $\gcd(n,k)=1$

Question

Can someone give me an easy (two or three line) proof for the fact that $\dbinom{n}{k}$ is divisible by $n$ for $k\not=0, n$ and $\gcd(n,k)=1.$
Here $\dbinom{n}{k}$ denotes usual binomial coefficients.

Answer 1

$k>0$, thus $\dbinom{n}{k}=\frac n k\dbinom{n-1}{k-1} $ Thus if $\gcd(n,k)=1$, n divides $\frac n k\dbinom{n-1}{k-1} $

Bonus : Combinatorial proof that $\dbinom{n}{k}=\frac n k\dbinom{n-1}{k-1} $ :

If you want to choose a team of k people amongst n with one team leader, you can :

• choose a leader first (n possibilities) then choose the remaining k-1 members amongst the n-1 remaining possiblities

• choose the k people first, then choose a leader amongst the k people team.

Thus $k\dbinom{n}{k}=n \dbinom{n-1}{k-1}$

Answer 2

The slightly more general result that $\frac{n}{\gcd (n,k)}$ divides $\binom{n}{k}$ (with $n\geq 1$ and $1\leq k \leq n$) can be proven quite easily using a couple results from group theory, as well as the identity $$k\binom{n}{k}=n\binom{n-1}{k-1}$$ Consider the (additive) group $\mathbb{Z}/n\mathbb{Z}$ of integers modulo $n$. The element $\bar{1}_n$ has order $n$, and for $k\in \lbrace 1,...,n \rbrace$, we have that $\binom{n}{k}(k{\bar 1}_{n})=\binom{n}{k}k{\bar 1}_{n}=\binom{n-1}{k-1}n{\bar 1}_{n}\underset{n \textrm{ divides } \binom{n-1}{k-1}n}{=} {\bar 0}_{n}$. Thus $\binom{n}{k}$ is divisible by the order of $k{\bar 1}_{n}$, which is equal to $\frac{n}{\gcd (n,k)}$. QED