9
$\begingroup$

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?

  • 1
    See this similar question: http://mathoverflow.net/questions/9181/pascal-triangle-and-prime-numbers2011-01-31

2 Answers 2

14

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.

6

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

  • 1
    @Moron: http://schreinerpatrick.wordpress.com/2010/06/21/a-good-edit/2011-02-01