Proving that $n\mid(nCr)$ for all $r$ ($1 \leq r \leq n-1$), only if $n$ is prime I'm trying to prove  that $n\mid(nCr)$ for all $r$ ($1 \leq r \leq n-1$) if and only if $n$ is prime.
Now proving that if $n$ is prime then $n\mid(nCr)$ is pretty easy, but how would you go about proving that $n\mid(nCr)$ only if $n$ is prime?
Could you show that if $n$ is not prime, then there exists an $r$ such that $n$ does not divide $nCr$? If so how would you go about doing that? I thought it would be easy but then I realized that for some $r, n\mid(nCr)$ even if $n$ isn't prime which made things a little bit more complicated.
I've managed to show that $n\mid(n-1)!$ for non-primes greater than or equal to $6$, which means that despite $n$ always canceling out with a product of factors in $r!(n-r)!$ in some cases, there will be another pair of factors that cancel out with the $n$ in $(n-1)!$, and sometimes there won't be. Maybe there's some kind of pattern but I can't find it unfortunately.
(I'd prefer a method that doesn't use undergraduate and above level maths) 
 A: Assume first that $n$ is not a power of a prime. Let $p$ be a prime factor of $n$, and let $p^k$ be its highest power dividing $n$, i.e. $p^k\mid n$, $p^{k+1}\nmid n$. Then it follows from Lucas' theorem that 
$$
p\nmid{n\choose p^k},
$$
in other words $r=p^k$ is the example you asked for.
Assume then that $n=p^k$ for some prime $p$ and integer $k>1$. Then it is not hard to show that
$$
p^2\nmid{n\choose p^{k-1}}.
$$
This settles the prime power case.
A: Suppose n is not prime, and let $n=mp$ where $p$ is a prime. Then $n\not|\binom{n}{p}$, since
$$\binom{n}{p}=n \bigg[\frac{(n-1)!}{p!(n-p)!}\bigg]=n\bigg[\frac{(mp-1)!}{p!((m-1)p)!}\bigg]=n\bigg[\frac{(mp-1)(mp-2)(mp-3)\cdots((m-1)p+1)}{p!}\bigg],$$ where the expression in brackets is not an integer since 
$(mp-1)(mp-2)(mp-3)\cdots((m-1)p+1)$ is not divisible by $p$, while $p!$ is.
A: We have to prove that n|ncr.
now, $nCr=n \cdot(n-1)\cdot(n-2)\cdot(n-3)....\cfrac{n+r-1}{r!}$
Since n is prime and $n \gt r$ then no factors of $r!$ divide $n$. thus $n$ does not cancel.so n must divide ncr when n is prime.
A: I am surprised that people are posting complex proofs of a theorem which is easily provable by high school math. Here is an example.
"if n is prime then n∣(nCr) is pretty easy". right, so we will skip this one. We will just prove the second part, i.e. if n is composite, then $ n \nmid nCr $ for certain r's.
In fact, those r's are all the prime factors of n.
Let r = p where p is a prime factor of n. so n = mp where m is some int.
$ nCp = \frac {n(n-1)(n-2)..(n-p+1)}{p(p-1)(p-2)...1}
= (\frac {n}{p})  \frac{(n-1).(n-2)...(n-p+1)}{(p-1)(p-2)..1} = (\frac{n}{p}) (n-1)C(p-1)
$
since $ (n-1)C(p-1) $ is a binomial coefficient in its own right, it has to be an integer. Let's call it i.
so $ nCp = \frac{n.i}{p} $
Now here is most important observation of this proof. i is formed by dividing a certain numerator by a certain denominator. The numerator is a product of the terms from (n-1) to (n-p+1). None of these terms are divisible by p. Why? because since n is divisible by a prime p, the next smaller integer that can be divided by p can only be n-p. All the terms of the numerator fall between n and n-p excluding the bounds, so none of them is divisible by p, and neither is their product. So we will call i "p-free".
Since i cannot be divided by p, for $nCp$ to be an int, n has to be divided by p. Since n/p = m, $ nCp = \frac{n.i}{p} = m.i$
Now for n to divide $nCp$, $m.p$ has to divide $m.i$. This gives rise to two options.

*

*m of numerator is divided by m of denominator, and i of numerator is divided by p of denominator.

*m of numerator is divided by p of denominator, and i of numerator is divided by m of denominator.

Option 1 is an impossibilty, because it requires i to be divided by p, and we know that i is "p-free".
Option 2 gives rise to two sub-options. Either m contains a factor p, or it does not. If it does not have a factor p, then clearly $ p \nmid m$. And if it has a factor p, then $ m \nmid  i $. (remember, i is p-free). So option 2 is also an impossibility.
