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

$\endgroup$
1

2 Answers 2

15
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ 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). $\endgroup$ Jan 31, 2011 at 23:54
  • $\begingroup$ @Qia: Yes, they can be. I will edit the answer. Thanks! $\endgroup$
    – Aryabhata
    Feb 1, 2011 at 0:05
  • $\begingroup$ 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!$. $\endgroup$
    – hardmath
    Feb 1, 2011 at 2:11
  • 1
    $\begingroup$ @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}$ $\endgroup$
    – hardmath
    Feb 1, 2011 at 2:49
  • 1
    $\begingroup$ @Moron: schreinerpatrick.wordpress.com/2010/06/21/a-good-edit $\endgroup$
    – hardmath
    Feb 1, 2011 at 3:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .