# prime numbers in Pascal's triangle

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?

-
See this similar question: mathoverflow.net/questions/9181/… –  PEV Jan 31 '11 at 22:59

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.

-

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

-
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
@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
–  hardmath Feb 1 '11 at 3:10