6
$\begingroup$

In the following link the proof states:
P = $p_1p_2 \cdot\cdot\cdot p_n + 1$ and continues to state P is prime "as long as $P \not=1$."
However this link states that P might not be prime and gives the counter example $2\cdot3\cdot5\cdot7\cdot13 + 1 = 30031 = 59 \cdot 509$

In the previous proof is the assumption that P is prime correct because they assume
there is a finite number of primes and only divide P by $p_i$ where i = 1,2,...,n?

$\endgroup$
3
  • 1
    $\begingroup$ The first link is just plain wrong. The core of the correct proof is that $P$ has a prime divisor other than $p_i$. $\endgroup$
    – user58697
    Jun 16, 2017 at 18:15
  • 4
    $\begingroup$ @user58697 Wrong, the first proof is correct. $\endgroup$ Jun 16, 2017 at 22:18
  • 1
    $\begingroup$ Somehow they merged together Euler and Euclid to create the monstrous creature "Eulclid". $\endgroup$
    – Jam
    Jun 22, 2017 at 14:08

3 Answers 3

10
$\begingroup$

The first link assumes that $p_1,p_2,\cdots,p_n$ are all the primes and then arrives at a contradiction.

If you notice in your example, the prime divisors of $30031$ are different from $2,3,5,7,13$. If these were all the primes then $30031$ would have been a prime number.

$\endgroup$
4
  • $\begingroup$ +1, although the sentence "If these [$2, 3, 5, 7, 13$] were all the primes then $30031$ would have been a prime number" makes me uncomfortable. $\endgroup$
    – Stahl
    Jun 16, 2017 at 23:15
  • 3
    $\begingroup$ @Stahl, It makes me too. Good thing they're not all the primes. $\endgroup$ Jun 16, 2017 at 23:18
  • $\begingroup$ You should probably add a "the" after the first "all". Otherwise it sounds like you're just saying that $p_1, \ldots, p_n$ are prime. $\endgroup$
    – Erick Wong
    Jun 17, 2017 at 6:00
  • $\begingroup$ @ErickWong Thank you. $\endgroup$ Jun 17, 2017 at 11:34
6
+50
$\begingroup$

The proof as presented by L. Shorser is technically correct but you have to read the whole thing and resist the urge to jump to conclusions. It could certainly be explained better, and with a more natural flow.

Let us assume that there are finitely many primes and label them $p_1, \ldots, p_n$.

For the sake of argument, we're assuming there are only $n$ primes. So far so good. This number $n$ may be 0, but it's definitely not a negative number. Let's say it's a positive integer. Then $$P = 1 + \prod_{i = 1}^n p_i.$$ Clearly $P \equiv 1 \pmod{p_i}$ for any $0 < i \leq n$. That's an obvious consequence of how we defined $P$. At this point, we're still operating under the assumption that there are finitely many primes.

At this point it doesn't seem terribly important to me whether $P$ is prime or not. If $P$ is prime then our value of $n$ was wrong, but a list of $n + 1$ primes is still a finite list of primes. We have more work to do in order to disprove finiteness.

But I got a little ahead of Shorser when I said $n$ ought to be a positive integer.

Since $2$ is a prime number, the list of $p_i$'s is non-empty.

That is, $n > 0$, which confirms $P \neq 1$. Furthermore, if all the $p_i$ are positive, we can also assert that $P > p_i$ for any applicable $i$.

The paragraph with the halmos seems elegant, and is definitely concise, but lots of people get confused by elegant and concise. The assumption that there are finitely many primes is refuted and dismissed in that last paragraph, which means it was still in effect when $P$ was said to be prime.

For what it's worth, I prefer to explain Euclid's proof in a more verbose, less elegant way. Hopefully what my explanation lacks in concise elegance is offset by clarity.

If the $p_i$ really are all the primes that exist, then $P$ must be composite and it must be divisible by at least one of the $p_i$. So either $P$ must be a prime we were previously unaware of, or it must be the product of two or more primes we were unaware of.

Then what we can do with that prime or those primes is append them to our finite list of primes, increment $n$ accordingly and start the process all over again. That will lead us to find at least one more prime that we were unaware of.

Which means that no matter how many primes we know, we can always find primes we didn't know. Therefore the full list of primes is infinite.

I choose to see Euclid's proof as providing a dynamic method by which we can always find more primes, rather than a static object that just sits there.

Let's say you know 2 and 7 are prime but you don't know any other primes. Then $P = 2 \times 7 + 1 = 15 = 3 \times 5$. Neither 3 nor 5 is divisible by 2, and they're both smaller than 7. And clearly 5 is not divisible by 4. So 3 and 5 must be prime. Now we know four primes: 2, 3, 5, 7.

It also works with negative primes, provided $n$ is positive. Suppose $n = 1$ and $p_1 = -29$. Then $P = -28 = -2 \times 2 \times 7 = 2^2 \times -7$. This is no way whatsoever contradicts the fundamental theorem of arithmetic, since both 1 and $-1$ are units, but it does show why it's more convenient to stick to positive primes.

And what if you don't know any primes at all? Then $n = 0$ and $P = 1$. But 1 is not a prime number. There are many reasons for that, some much better than others, and some just plain dumb.

But up until just a couple of centuries ago, 1 was erroneously considered a prime number. What if we use $n = 1$ and $p_1 = 1$? Then $P = 2$, which is indisputably prime. Since now we know that 2 is prime, we can safely remove 1 from the list of primes. Or we can keep in there, the performance penalty is so small as to be of no concern to us.

Then, by continuing the process, we get $2\times3\times7\times43+1 = 1807 = 13 \times 139$, etc.

$\endgroup$
2
  • $\begingroup$ Thanks for giving such a comprehensive response. When you say "Then what we can do with that prime or those primes is append them to our finite list of primes, increment n accordingly and start the process all over again." Is this "kind" of like a proof by induction way of proving the theorem? Also what do you mean by "The paragraph with the halmos seems elegant?" $\endgroup$
    – user414441
    Jun 19, 2017 at 16:12
  • 1
    $\begingroup$ The halmos is the end of proof mark. I'm not sure if continually amending the list of primes to add newly discovered primes counts as induction. As I understand induction on integers, we'd prove something is true for $n + 1$ if it is true for $n$, then it's enough to prove it is true for $n = 0$ or 1. The larger $n$ then fall like dominoes. $\endgroup$ Jun 19, 2017 at 19:32
5
$\begingroup$

Yes, the first proof is correct. It applies the following theorem: $P > 1$ is prime if it has no smaller prime divisor. By hypothesis, $\,p_1,\ldots,p_n\,$ are all the primes, and none divide $\,P = 1+p_1\cdots p_n\,$ so the theorem implies that $P$ is prime, contra hypothesis, since $P > p_i \,\Rightarrow\, P\neq p_i$

Note carefully that the deduction that $P$ is prime depends on the hypothesis that there are only finitely many primes. So while it is true that $P$ is prime in the hypothetical theory of the "naturals with finitely many primes", $P$ need not be prime in the real naturals (as your example confirms).

In contradictory theories (such as the naturals with finitely many primes) there are many paths to contradictions. Some may look strange at first glance, esp. in intimately familiar theories like integer arithmetic, where the intermediary inferences are often contrary to well-honed intuition.

$\endgroup$

You must log in to answer this question.