25
$\begingroup$

In Euclid's proof, if $p_1, p_2, \dots, p_n$ are the only primes then $p_1 \times p_2 \times \dots \times p_n + 1$ is not divisible by any of $p_1, p_2, \dots, p_n$ (because of some algebraic facts), which makes another prime and is a contradiction.

The proof makes sense logically, and I tried some numerical examples to "feel" the proof better but...

$2 \times 3 \times 5\times 7\times 11\times 13+1$ is not a prime! $2 \times 3 \times 5\times 7\times 11\times 13 \times 17+1$ is also not prime! Why is the general case proof is not working for these examples?

$\endgroup$
9
  • 45
    $\begingroup$ It is a common mistake to think that $p_1p_2...p_n+1$ is prime, it is simply divisible by a prime that is not one of those used in the product. $\endgroup$
    – user208649
    Apr 7, 2016 at 2:09
  • 3
    $\begingroup$ @TokenToucan, you should make that an answer. $\endgroup$ Apr 7, 2016 at 2:10
  • 8
    $\begingroup$ Here we have the usual historical mistake, dating back at least to Dirichelt, which holds that Euclid's proof was by contradiction. Euclid's actual proof was simpler and better than that. See my answer below. $\qquad$ $\endgroup$ Apr 7, 2016 at 2:21
  • 7
    $\begingroup$ Sure, $2\cdot 3\cdot 5\cdot 7 \cdot 11 \cdot 13 +1$ is prime under the assumption that there are no other primes besides $2,3,5,7,11,13$. After all, under that assumption, $59$ and $509$ aren't primes, right? When proving something by contradiction, the exact path to the contradiction can be left up to taste: all that matters is that a contradiction exists. $\endgroup$
    – Erick Wong
    Apr 7, 2016 at 2:26
  • 4
    $\begingroup$ Duplicate: Why is Euclid's proof on the infinitude of primes considered a proof? $\endgroup$
    – Workaholic
    Apr 8, 2016 at 11:27

6 Answers 6

69
$\begingroup$

Suppose there are finitely many primes. Then we can enumerate them as a set $$P = \{p_1, p_2, \ldots, p_n\}.$$ The number $m = p_1 p_2 \ldots p_n + 1$ is either prime or composite. If it is prime, then we have found a prime that is not among the finite set $\{p_1, \ldots, p_n\}$ of primes we assumed to comprise the collection of all primes. If it is composite, then it is divisible by a prime. But it cannot be divisible by any of $p_1, p_2, \ldots, p_n$, for upon dividing $m$ by any of these primes, it leaves a remainder of $1$. Therefore, $m$ is divisible by a prime that again is not in the presumed set of all primes. In either case, a contradiction is obtained in which the assumption that there are finitely many primes is violated.

$\endgroup$
7
  • 1
    $\begingroup$ This is a perfect answer. Thanks a lot :)) $\endgroup$
    – user231343
    Apr 7, 2016 at 2:18
  • 4
    $\begingroup$ @Edi : This is an erroneous answer if taken to be about the actual history of the proof. It is also not as good a proof as the one Euclid actually wrote. See my posted answer. $\qquad$ $\endgroup$ Apr 7, 2016 at 2:22
  • 3
    $\begingroup$ @MichaelHardy (math.stackexchange.com/questions/631977/…) I understand this is a pet peeve for you, but maybe it's time to let this one go. This proof is perfectly valid - maybe not as nice as yours, and maybe not what Euclid wrote, but that's by the by. Note that the OP was asking specifically for a proof that the number of primes is infinite, not for a proof that if $S$ is any finite set of primes, then there's a prime not contained in $S$. $\endgroup$ Apr 8, 2016 at 18:00
  • 1
    $\begingroup$ @Donkey_2009 : How do I "let it go" when people keep posting forms of this question? Stop them, somehow? If this question were closed as a duplicate and directed to that earlier question, that would make sense. This poster thought someone claimed Euclid had proved that $1+p_1\cdots p_n$ is always prime. Should I have (1) left that unanswered, or (2) voted to close as a duplicate, or (3) something else? The confusion arises precisely from the rearrangement of the proof into a proof by contradiction. $\qquad$ $\endgroup$ Apr 8, 2016 at 18:56
  • 1
    $\begingroup$ @MichaelHardy An answer to this question does not require a diatribe into the historical background of Euclid's proof or whether or not it requires contradiction. There are two ways to answer the question: 1) Point out that even if $1+p_1\dots p_n$ is not prime, it must have some prime divisor that is not one of the $p_n$ or 2) Claim that the entire proof is by contradiction, so there's no sense trying to derive anything from it. I agree with you that (1) is far better, but it is sufficient to give the argument without claiming that approach (2) is erroneous. $\endgroup$ Apr 8, 2016 at 19:22
62
$\begingroup$

Euclid's proof was not by contradiction. Many respectable authors say it was, and they're wrong. Dirichlet may have been the originator of the error.

Euclid said that if you take any finite set $S$ of primes (which need not be the first $n$ primes) then the prime factors of $1+\prod S$ are not members of $S$; hence there is at least one more prime than those in any finite set $S$.

Say the finite set you start with is $S=\{5,7\}$. Then $1+\prod S = 36 = 2\times2\times3\times3$, so the additional prime numbers are $2$ and $3$.

There's nothing in that that says $1+\prod S$ (which in the example above is $36$) is prime. That comes up only when the proof is rearranged into a proof by contradiction, and then $1+\prod S$ is shown to be prime, not in the actual sequence of natural numbers, but in the hypothetical set of all natural numbers that contains only finitely many primes. Since that hypothetical set is ultimately shown not to exist, there's no problem.

Moral of the story: Rearranging this into a proof by contradiction makes the matter confusing and more complicated --- hence in those ways inferior to Euclid's original proof.

PS: By popular demand (expressed in comments below), here is a proof that $1+\prod S$ is not divisible by any of the members of $S.$ Suppose $p$ is one of the members of $S.$ If you divide $\prod S$ by $p,$ the quotient is the product of all the other members of $S$ and the remainder is $0$, so if you divide $1+\prod S$ by $p,$ the quotient is the product of those other members and the remainder is $1$. Since the remainder is $1,$ the number $1+\prod S$ is not divisible by $p.$

For example: Suppose $S=\{5,7,13\}.$ Then $N= 1+\prod S$ is $1 + (5\times7\times 13) = 456.$

If you divide $N$ by $5$, the quotient is $7\times 13$ and the remainder is $1.$

If you divide $N$ by $7$, the quotient is $5\times 13$ and the remainder is $1.$

If you divide $N$ by $13$, the quotient is $5\times 7$ and the remainder is $1.$

Dividing $N$ by any of the members of $S$ leaves a remainder of $1$, so $N$ is not divisible by any of those members.

$\endgroup$
23
  • 4
    $\begingroup$ @Ian : True, but Euclid probably knew a straightforward if laborious algorithm for finding the smallest prime factor of any given number. $\qquad$ $\endgroup$ Apr 7, 2016 at 2:38
  • 2
    $\begingroup$ +1 This is definitely more clever than the usual contradiction formulation... $\endgroup$
    – user541686
    Apr 7, 2016 at 6:56
  • 2
    $\begingroup$ I don't know how literally Euclid's proof should be taken. Strictly speaking, he considers only the case that $|S|=3$ (though this is understood to mean any finite set of more than two elements) $\endgroup$ Apr 7, 2016 at 11:53
  • 2
    $\begingroup$ To his credit,he did not even say that. He said there was no largest prime because for any finite set of primes, there is a prime not in that set, It is logically quite different than asserting that there is such a thing as the set of all primes, or that there is an infinite set. $\endgroup$ Apr 7, 2016 at 14:01
  • 2
    $\begingroup$ This answer would be better if it spent more time explaining the details of Euclid's proof (why does $\Pi S_n + 1$ have a prime factor not in $S$?) and less time ranting about proof by contradiction. $\endgroup$ Apr 7, 2016 at 15:21
15
$\begingroup$

It is a common mistake to think that $p_1p_2...p_n+1$ is prime, it is simply divisible by a prime that is not one of those used in the product.

And to address your comment - if you do get a prime from $p_1...p_n + 1$, it is divisible by a prime not in the list, which just happens to be itself.

$\endgroup$
11
$\begingroup$

The reason that your numerical examples do not work is because the conclusion that "$p_1 p_2 \ldots p_n + 1$ is prime" was based on a false assumption ($p_1, p_2, \ldots, p_n$ are all the primes) made for the purposes of obtaining a contradiction. Once you obtain the contradiction, you've proven the original statement (there are infinitely many primes) but there is no reason to believe any of the intermediate statements will hold, because they are all based on an assumption which you now know to be false.

$\endgroup$
1
  • $\begingroup$ +1 because it is crucial that the working assumption has turned out to be false and thus produces anything. $\endgroup$ Apr 7, 2016 at 15:44
5
$\begingroup$

It depends on how you start. You can start with "assume that $p_1$ to $p_n$ are primes, and I will demonstrate that there is another prime". You take the product of $p_1$ to $p_n$, add 1, and get a number not divisible by any prime $p$ within $p_1$ to $p_n$, so that number is either a prime itself, or divisible by a prime other than those in the set $p_1$ to $p_n$, and in either case we have another prime.

Or you can try a proof by contradiction. You start with "assume that $p_1$ to $p_n$ are all the primes. Then the product plus 1 is not divisible by any prime (because it is divisible by $p_1$ to $p_n$, which are all the primes) and therefore it is a prime. On the other hand, since $p_1$ to $p_n$ are all the primes it's even more obviously not a prime :-) So we get a contradiction. So the assumption "$p_1$ to $p_n$ are all the primes" is false.

$\endgroup$
4
$\begingroup$

$2\times3\times5\times7\times11\times13+1$ does not need to be prime, all it says in the proof is that this number is not divisible by any of the primes used to create it, namely 2,3,5,7,11 and 13. The fact that this number needs to be divisible by some prime then yields the result that the list of primes is not complete

$\endgroup$
5
  • 2
    $\begingroup$ The first counterexample of this form is in fact the one you mention: $$ \Big(2\times3\times5\times7\times11\times13\Big)+1 = 59\times 509. $$ $\endgroup$ Apr 7, 2016 at 2:25
  • $\begingroup$ @MichaelHardy Using Euclid's construction itself starting with 2, you get 3, then 7, then 43, then 1807, and 1807 is divisible by 13. So that's a somewhat smaller "counterexample" (but of course it skips a bunch of primes). $\endgroup$
    – Ian
    Apr 7, 2016 at 2:31
  • 1
    $\begingroup$ @Ian : I did say "of this form", and that can be construed as meaning it comes from the first $n$ primes. $\qquad$ $\endgroup$ Apr 7, 2016 at 2:37
  • 2
    $\begingroup$ @Ian You construct the interesting sequence 2, 3, 7, 43, 13, .... $\endgroup$ Apr 7, 2016 at 10:15
  • 1
    $\begingroup$ @Ian : A still smaller counterexample even smaller than the one you mention is $(3\times7)+1$, which is divisible by $2$. $\qquad$ $\endgroup$ Apr 7, 2016 at 16:06