# Prime Factors in Pascal's Triangle

The question about reversing n choose k made me look a little further into Pascal's triangle, but my curiosity is not satiated.

I am now curious of the following:

Given $n > k > 1$, show that $\binom{n}{k}$ is divisible by a prime $p|\binom{n}{k}$, such that $p > k$ OR $k| \binom{n}{k}$ .

I would like to point out the following:

For any prime n, p = n satisfies the criterion (A well known proof, every non-1 element in the triangle is divisible by p).

For k = 2, consider the formula for this diagonal of the triangle

$$f_2(n) = \dfrac{n(n+1)}{2},$$

Assuming a proof by exclusion (is that a thing), this can only fail the criterion if there exists a number n such that $$f_2(n) = 2^t$$ for some t. But that is impossible, because one of n, (n+1) is odd, so it must have some prime factor not equal to 2. Additionally, the diagonal is ascending, so the value of $f_2(n)$ must increase, and the odd number must contain another prime factor other than 2 for all n. This shows that the case k = 2 is true also.

Can this idea be extended to later cases of k to show that it works for all the diagonals, thus completing the proof? As you may have guessed I tried induction, but I was unsure how to proceed.

In the event this proves unfruitful, is there another already known theorem or identity to prove this question? I bring up Wilson's Theorem, and Lucas' Theorem.

This proof is a lemma for a larger one that follows almost directly. It would be helpful for my own research if someone could point me in the right direction with this, and I will give more credit than necessary to the person who can help me prove this, although it may be a rather arbitrary result at the end of the day.

What if $n=4$ and $k=3$? Or $n=6$ and $k=5$? Or $n=10$ and $k\in\{7,8,9\}$?
• I find it hard to believe this could be a good answer to a question that's nearly a year old. Your counter examples when $k = n - 1$ were not explicitly excluded by the OP, but by the symmetry of binomial coefficients, were clearly excluded in spirit. The ${10 \choose 7}$ counterexample (although clearly ${10 \choose 7} = {10 \choose 3} = 120$ where $5 \mid 120$ and $5 > 3$) is definitely something the OP should consider. – pjs36 Jun 19 '16 at 4:26
• A theorem of Sylvester and Schur (renyi.hu/~p_erdos/1934-01.pdf) says that $\binom nk$ always contains a prime factor $>k$ if $n\ge 2k$, so I'm not sure what your comment in brackets was intended for. – nayel Jun 19 '16 at 8:17