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\}$?

| cite | improve this answer | |
  • 3
    $\begingroup$ 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. $\endgroup$ – pjs36 Jun 19 '16 at 4:26
  • 2
    $\begingroup$ 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. $\endgroup$ – nayel Jun 19 '16 at 8:17
  • $\begingroup$ @nayel, I suppose that is what I was trying to prove, then. This is an old post, maybe I should go dig up whatever I claim comes next... $\endgroup$ – theREALyumdub Jun 19 '16 at 20:27
  • $\begingroup$ @pjs36, yes I think you are right, I must have assumed that but not explained it. Obviously we can look at the other side of the triangle too. $\endgroup$ – theREALyumdub Jun 19 '16 at 20:28
  • $\begingroup$ @nayel My apologies -- many answers this short to older questions tend not to be the best, and a few of them felt a bit like exploiting an unstated assumption. But you clearly know a bit about the subject. $\endgroup$ – pjs36 Jun 20 '16 at 0:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.