if $n>0$ and $r>0$ ($n$ and $r$ and positive integers) and $r$ divides $n$ , then $n/r$ divides $nCr$ . Is this statement true?

Question

if $n>0$ and $r>0$ ($n$ and $r$ and positive integers), and $r$ divides $n$, does $n/r$ divides $\binom{n}{r}$ ?

Here $\binom{n}{r}$ means $n$ choose $r$.(selecting $r$ things from total of $n$ things). I have many examples which make this statement true.

• Consider $n = 2$ and $r = 2$ . $r$ divides $2$ and $2/2$ divides $\binom{2}{2}$. ($1$ divides $1$)
• More example $n = 4$ and $r = 2$ . $r$ divides $4$ and $4/2$ divides $\binom{4}{2}$ ($2$ divides $6$)
• More example $n = 6$ and $r = 2$ . $r$ divides $6$ and $6/2$ divides $\binom{6}{2}$ ($3$ divides $15$)
• More example $n = 12$ and $r = 4$ . $r$ divides $12$ and $12/4$ divides $\binom{12}{4}$ ($3$ divides $495$)

Now my question is - is this always the case? I tried proving it myself by expanding the factorials and cancelling the terms but failed to prove.

Then I tried proving it by a combinatorial proof. Then I proved it for one case. That one case was where $n$ is even and $r = n/2$. Then we can say $\binom{n}{n/2}$ counts the number of ways of selecting any $n/2$ things and not selecting the other $n/2$ automatically.

So consider any one such case where $A$ is set of $n/2$ selected things and $B$ is set of $n/2$ not selected things.

Then we can say there will be another case corresponding to this one where we select the $n/2$ elements in $B$ and not select the $n/2$ elements in $A$.

So these cases will be in pairs and so they will be even this proves only one case where $n$ is even and $r=n/2$.

I need help in proving this statement for all cases. How can I prove it?

Answer 1

Using factorial form, it is rather easy to prove (I let you prove this part) that $$\binom{n}{r}=\frac{n}{r}\binom{n-1}{r-1}$$

Therefore if $r$ divides $n$, then yes, $\frac{n}{r}$ divides $\binom{n}{r}$.

Answer 2

First we need a lemma. Denote $\nu_p(n)$ to be the greatest power in which a prime number $p$ divides $n$.

Lemma: If $\nu_p(n) = u$, then $\nu_p(n!) = \sum_{i=1}^u \frac{n}{p^i}$. This is quite trivial because you first count multiples of $p$, then multiples of $p^2$, etc.

Let $n=mr$. Let $p$ be any prime factor of $m$. We need to prove that if $\nu_p (m)=s, \nu_p(r)=t$ (note that $s\ge 1$ but $t$ can be zero), then $p^s | {n\choose r}$, or equivalently $\nu_p({n \choose r}) \ge \nu_p(m)$ . If that's the case then $m \mid $ $n \choose r$.

It's easy to see that $\nu_p(n)=s+t, \nu_p(n-r)=t$, therefore

$n \choose r$ = $\frac{n!}{r!(n-r)!} \Rightarrow \nu_p({n \choose r}) \\ = \nu_p(n!) - \nu_p(r!) - \nu_p((n-r)!) \\ = \sum_{i=1}^{s+t} \frac{n}{p^i} - \sum_{i=1}^t \frac{r}{p^i} - \sum_{i=1}^t \frac{n-r}{p^i} \\ =\sum_{i=1}^{s+t} \frac{n}{p^i} - \sum_{i=1}^t \frac{n}{p^i} = \sum_{i=t+1}^{s+t} \frac{n}{p^i} \ge \sum_{i=t+1}^{s+t} 1 = s. \blacksquare$