Let $n$,$k$ be positive integers so that $1<k<n-1$. Prove that the binomial coefficient $\binom{n}{k}$ is divisible by two distinct primes.
My approach was to look at Pascal's triangle and try to notice some patterns. I noticed that $(1)$all numbers(excluding $1$'s) in a $m$-th row are divisible by atleast one prime divisor of $m$ and $(2)$two consecutive binomial coefficients have a common factor of some prime divisor of $m$. Also we have an identity $(3)$ $$\binom{n}{k}+\binom{n}{k+1}=\binom{n+1}{k+1}$$ It would be that $\binom{n}{k}$ and $\binom{n}{k+1}$ have a common factor of some prime divisor of $m$ and $\binom{n+1}{k+1}$ is divisible by some prime factor of $m+1$, also we keep in mind $m$ and $m+1$ are prime, hence there are no common divisors between those and that is how I want to prove it.
To prove $(1)$ we can use $p$-adic valuation. If $n$ is a power of a prime it is well known that it works. Also if we take some $k$, $1 \le k \le n-1$ that some divisor of $n$, $p$ doesn't divide $k$ we have that $p|\binom{n}{k}$. It remains to prove that if set of prime divisors of $n$ and $k$ is the same $(1)$ is satisfied. I would like to solve the problem this way. How do I proceed? Any help appreciated.
Best Answer
HINT:
For $1\le k < l< n$ the binomial coefficients $\binom{n}{k}$, and $\binom{n}{l}$ are Not relatively prime.
$\bf{Added:}$
We use the fact above, the proof is at the very end.
Assume now that $\binom{n}{k}$ is a prime power $p^{t}$. Then all of the binomial coefficients $\binom{n}{l}$, $1\le l \le n-1$ are divisible by $p$. With Lucas's theorem we conclude that $n$ is a power of $p$, $n= p^{\alpha}$ ( use the fact that $\binom{p^{\gamma} u}{p^{\gamma} v} \equiv \binom{u}{v} \pmod p$. )
Now, let $k = p^{\beta} m$, $(p,m) = 1$. Then the exponent of $p$ in $\binom{p^{\alpha}}{p^{\beta}m}$ equals $\alpha- \beta$. If $\binom{p^{\alpha}}{p^{\beta}m}$ were a power of $p$, it would equal $p^{\alpha- \beta}$. But it is not hard to check that $$\binom{p^{\alpha}}{p^{\beta}m} \ge \binom{p^{\alpha- \beta}}{m}\ge p^{\alpha- \beta}$$ and we cannot have equality.
Proof of the fact: note that we have the equality $$\binom{n}{k} \binom{n-k}{n-l} = \binom{n}{l} \binom {l}{l}$$ both numbers equal the numbers of sets $A\subset B \subset \{1, \ldots, n\}$, $|A|=k$, $|B|=l$. Now if $\binom{n}{k}$, $\binom{n}{l}$ were relatively prime, we would get $\binom{n}{k}$ divides $\binom{l}{k}$, not possible (proof of this fact by Michele D'Adderio ).