Easy proof: $\binom{n}{k}$ is divisible by $n$ for $\gcd(n,k)=1$ 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.
 A: $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}$
A: 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
