Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Just wondering about this:

Is it true that there are no prime numbers in Pascal's triangle, with the exception of $\binom{n}{1}$ and $\binom{n}{n-1}$?

From the first 18 lines it appears that this is true, but I haven't looked beyond that. Is this a coincidence or is there a reason for it?

share|improve this question
1  
See this similar question: mathoverflow.net/questions/9181/… –  PEV Jan 31 '11 at 22:59
add comment

2 Answers

up vote 11 down vote accepted

Yes, it's true. The identity ${m \choose n} = \frac{m}{n} {m-1 \choose n-1}$ can be rearranged as $n {m \choose n} = m {m-1 \choose n-1}$. If ${m \choose n}$ is prime it follows that it must divide either $m$ or ${m-1 \choose n-1}$. In the first case we can only have $n = 1, n = m-1$, as you have already observed, and in the second case, the quotient $\frac{n}{m}$ cannot be an integer unless $n = m$ or $n = 0$, and neither of these cases gives a prime.

share|improve this answer
add comment

I believe it is true.

If $\displaystyle \binom{n}{r} = p$ for some prime $\displaystyle p$ and $\displaystyle 1 \lt r \lt n-1$, then,

If $\displaystyle n \ge p$, then $\displaystyle \binom{n}{r} \gt n \ge p$, as the binomial coefficients increase and then decrease as $\displaystyle r$ varies from $\displaystyle 0$ to $\displaystyle n$.

If $\displaystyle n \lt p$ then $\displaystyle \binom{n}{r}$ can never be divisible by $\displaystyle p$, as $\displaystyle n!$ is not divisible by $\displaystyle p$.

OR as hardmath succintly put it:

$p \mid \binom{n}{r} \Rightarrow p \le n \lt \binom{n}{r}$

share|improve this answer
    
Nice argument. (You can combine the first and third cases.) To be totally explicit, Moron is relying on the fact that binomial coefficients are unimodal (they increase and then decrease in a given row). –  Qiaochu Yuan Jan 31 '11 at 23:54
    
@Qia: Yes, they can be. I will edit the answer. Thanks! –  Aryabhata Feb 1 '11 at 0:05
    
Yes, very neat. Perhaps one more tweak: the last case can be recast as a direct argument, that $p \le n$ since $p$ divides $n!$. –  hardmath Feb 1 '11 at 2:11
1  
@Moron: It's starting to remind me of Benjamin Franklin's story about an advertisement that got redacted, word by word until only a picture of the product remained! $p | \binom{n}{r} \Rightarrow p \le n \lt \binom{n}{r}$ –  hardmath Feb 1 '11 at 2:49
1  
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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