# Why is Euclid's proof on the infinitude of primes considered a proof?

I've expressed Euclid's proof on the infinitude of primes on Mathematica:

f[x_] := Product[Prime[n], {n, 1, x}] + 1
TableForm[Table[{f[x], PrimeQ[f[x]]}, {x, 1, 20}]]


Which results in:

$\begin{array}{ll} 3 & \text{True} \\ 7 & \text{True} \\ 31 & \text{True} \\ 211 & \text{True} \\ 2311 & \text{True} \\ 30031 & \text{False} \\ 510511 & \text{False} \\ 9699691 & \text{False} \\ 223092871 & \text{False} \\ 6469693231 & \text{False} \\ 200560490131 & \text{True} \\ 7420738134811 & \text{False} \\ 304250263527211 & \text{False} \\ 13082761331670031 & \text{False} \\ 614889782588491411 & \text{False} \\ 32589158477190044731 & \text{False} \\ 1922760350154212639071 & \text{False} \\ 117288381359406970983271 & \text{False} \\ 7858321551080267055879091 & \text{False} \\ 557940830126698960967415391 & \text{False} \\ \end{array}$

The proof flaws for all those values, how is it considered a proof then? I guess that there might be infinite prime numbers according to the proof, but what is the guarantee that at some point it won't fail indefinitely?

-
I think you're misunderstanding Euclid's argument. $p_1p_2\ldots p_n+1$ is divisible by some prime not equal to $p_1, \ldots, p_n$. It's not necessarily itself a prime. –  user7530 Jan 8 at 23:58
The statement is not that $p_1p_2\dots p_n+1$ is prime. –  egreg Jan 8 at 23:58
I don't see any reason to downvote this question; it is based on a misunderstanding, which, between the comments above and the answer below, is now hopefully corrected. –  Matt E Jan 9 at 0:02
Euclid wasn't stupid, you know. –  MJD Jan 9 at 0:14
@GustavoBandeira This is a classic question. Don't beat yourself up! –  Potato Jan 9 at 0:29

Euclid’s proof differs from what many mathematicians tell you it is. He said this:

Take any finite set of primes. (Don’t assume it’s the set of all primes; don’t make it a proof by contradiction; don’t assume it’s the first $n$ primes; for example it could be $\{2,7,31\}$.)

Multiply them and add $1$. Then show (and this part was done by contradiction) that the prime factors of the resulting number are not in the finite set you started with.

Thus every finite set of primes can be extended to a larger finite set of primes.

Nothing in that argument gives you any reason to think that if you multiply the first $n$ primes and add $1$, the result is prime. That’s a confusion resulting from inattentiveness to what Euclid actually wrote.

An excerpt from our paper:

Only the premise that a set contains all prime numbers could make anyone conclude that if a number is not divisible by any primes in that set, then it is not divisible by any primes.

Only the statement that $p_1\dots p_n+1$ is not divisible by any primes makes anyone conclude that that number "is therefore itself prime", to quote no less a number theorist than G. H. Hardy [who] actually attributed that conclusion to Euclid! (Euclid's statement "Certainly [that number] is prime, or not" [...] clearly shows that Euclid's reasoning did not follow that path.)

The mistake of thinking that $p_1\dots p_n+1$ has been proved to be prime is made all the more tempting by the very obvious fact that that would entail the result to be proved.

[ . . . ]

In any proof by contradiction, once the contradiction is reached, one can wonder which of the statements asserted to have been proved along the way can really be proved in just the manner given (since the argument supporting them does not rely on the initial assumption later proved false), which ones are correct but must be proved in some other way (since the argument supporting them does rely on the initial assumption) and which ones are false. It is easy to neglect that task. One's consequent ignorance of the answers to those questions can lead to confusion: after all, when one remembers reading a proof of a proposition, might one not think the proposition has been proved and is therefore known to be true? G. H. Hardy probably was aware that because the conclusion that $p_1\dots p_n+1$ "is therefore itself prime" was contingent on a hypothesis later proved false, it could not be taken to be proved. But he did not say that explicitly. It seems hard to justify a similar confidence that all of his readers avoided the error into which he inadvertently invited them.

-
I don't think Euclid ever wrote "finite". Nor did he write "infinite" for that matter, so saying he proved the set of primes is infinite is a misrepresentation. He said that for any given amount of primes, new primes (not yet given) can be found. By our standards (allowing infinite sets) his argument fails (take the infinite set of all primes as given; one cannot form their product), but I think he would have considered giving an infinite set of primes absurd (like we would consider taking their product absurd). –  Marc van Leeuwen Jan 9 at 17:59
@alexis : I don't think Euclid's proof (the one he actually wrote) fails by any reasonable standards. And where he writes "Let A, B, C be the proposed prime numbers", I think we should take that to be merely a notational device that should not be construed literally, as meaning he's considering only three primes. –  Michael Hardy Jan 10 at 4:06
@MarcvanLeeuwen FWIW, Euclid used the word ἄπειρον, unbounded or infinite, sometimes in geometry (e.g. Post. 5), but not in this proposition. He used the word πλῆθος, multitude, which incidentally is the word used to define number. A number is a multitude of units. In IX.20, Euclid stated, "The prime numbers are more than any proposed multitude of prime numbers" -- he is just that close to saying a "number of prime numbers." –  Michael E2 Jan 11 at 0:27
@alexis: What I meant by "Euclid's proof fails..." is only that (1) saying that Euclid proves the set of all primes to infinite is a misrepresentation, because notion of "set", "all primes" and "infinite" are anachronisms with respect to Euclid (2) if you must interpret what Euclid does write into set theory, then it is closest to "there are more primes than in any given set of primes", and this statement (and therefore its proof) becomes false in our modern eyes, but (3) this interpretation assumes Euclid conceives the totality of all primes, whereas he would probably reject any such idea. –  Marc van Leeuwen Jan 11 at 9:52
While I'm abusing comments, I might as well resume my thoughts on the issue raised by this answer. (1) It is definitely wrong to say the Euclid reasoned for the (hypothetic) set of all primes, which is the only context in which "$p_1...p_n+1$ is prime since not divisible by any prime" would make sense (and even then only as an intrinsic absurdity). But (2) Neither is it right to suggest that Euclid chose to avoid that kind of argument: the whole idea of such a proof (using the set of all primes) is fundamentally modern and would not be conceivable for Euclid; his proof shows it to be absurd. –  Marc van Leeuwen Jan 11 at 10:20

It is not claimed the $p_1 \cdots p_n + 1$ is prime; indeed, as your table shows, it is often not a prime. I think it is safe to assume that Euclid could also compute that it is not always prime.

The point is that it does have at least one prime factor, since it is $> 1$, and this prime factor cannot be any of $p_1, \ldots,p_n$.

-
Euclid's proof never explicitly mentions the product of the first $n$ primes. Euclid proved that if $A$ is any finite set of primes (which might or might not be the first $n$, the primes factors of $\displaystyle\left(\prod A\right)+1$ are not in $A$. ${}\qquad{}$ –  Michael Hardy Jan 9 at 3:41
Yes, it is claimed that if A is finite p1p2..pn+1 is prime. With the false premise that p1,p2,..,pn are the only prime numbers. –  JulienFr Jan 9 at 17:07
@JulienFr : It was not Euclid who claimed that; it was later writers. –  Michael Hardy Jan 9 at 17:15

The key idea is not that Euclid's sequence $\ f_1 = 2,\,\ \color{#0a0}{f_{n}} = \,\color{#c00}{\bf 1} + f_1\cdots f_{n-1}$ is an infinite sequence of primes but, rather, that it is an infinite sequence of coprimes, i.e. $\,{\rm gcd}(f_k,f_n) = 1\,$ if $\,k<n,$ since any common divisor of $\,\color{orange}{f_k},\,\color{#0a0}{f_n}$ must divide $\ \color{#c00}{\bf 1} = \color{#0a0}{f_n} - f_1\cdots \color{orange}{f_k}\cdots f_{n-1}.$

Any infinite sequence $\,f_n > 1 \,$ of coprimes yields an infinite sequence of distinct primes $\, p_n$ obtained by choosing $\,p_n$ to be any prime factor of $\,f_n,\,$ e.g. the least prime factor.

Remark $\$ A shorter way to present Euclid's proof is to note that iterating the map $\, n\mapsto n^2\!+n$ generates integers with an unbounded number of prime factors, because $\,n(n+1)\,$ includes all prime factors $\,n\,$ plus some (new!) prime factor of $\,n+1.$

-
Oh my god, Bill! I am so happy that you are back! I admire you a lot! –  Vÿska Jan 9 at 5:50
Super cool way to present the proof in that Remark. Thanks! –  limp_chimp Jan 9 at 16:38
Honestly, while the remark proves that there are infinitely many primes, I don't see how it can be construed to present Euclid's proof. Euclid did not construct the sequence $(f_i)_{i=1,2,\ldots}$ either. –  Marc van Leeuwen Jan 9 at 17:54
@Marc My intent was not to give a precise historical presentation but, rather, to show the idea behind Euclid's proof - interpreted from a more modern viewpoint. –  Bill Dubuque Jan 9 at 17:58
This is a clear and concise answer for the mathematics of the situation. I am going to write something about the logic of the proof as another answer. –  Carl Mummert Mar 17 at 11:51

If you read Euclid's proof itself -- it's Proposition 20 in Book IX -- you'll see that he explicitly says that the posited product of primes plus $1$ "is either prime or not" [emphasis added].

-
AND "the posited product of primes" was not generally the smallest $n$ primes; it was an arbitrary finite set "$\pi\lambda\overset{'}{\eta}\vartheta\omicron\upsilon\varsigma$" of primes. –  Michael Hardy Feb 2 at 18:55

If $p_k$ were the largest prime, then $p_1 p_2 \ldots p_k + 1$ would be prime. Since none of the values you have used for $p_k$ is the largest prime, the constructed number need not be prime.

-
Dammit. Isn't the question about how there is no largest prime??? –  Anonymous Pi Jan 9 at 15:23
It is a proof by contradiction. This fact is not needed to understand the OP's question. –  jwg Jan 9 at 16:30
It's in fact a good answer: if p_k is the largest prime, then m=p1p2....p_k+1 is prime too, because it is not divisible by any other prime number (m mod p_i = 1 for all i ) . but if m is prime, m>p_k, then p_k is not the largest prime. Contradiction. There is no largest prime, there is an infinity of prime numbers. –  JulienFr Jan 9 at 16:59
Right, @JulienFr. If you don't know that p1p2...pk + 1 is bigger than pk, then the above remains true and is a complete answer, even though you can't carry out Euclid's proof. –  jwg Jan 9 at 17:39
@AnonymousPi No need to be mean. –  Vÿska Jan 9 at 19:55

We suppose that there are only finitely many prime numbers, make a list of them, multiply them all together, and add 1. The resulting number, say $N$, is not divisible by any prime number, since by assumption all prime numbers are on the list, and $N$ is not divisible by any number on the list. That's enough for a contradiction right there—we don't need to conclude that $N$ is prime.

-
Dear crf, As Michael Hardy has pointed out on various occassions, Euclid apparently did not argue by contradiction in this way (although his argument is often presented as an argument by contradiction); rather, he simply took $n$ primes and then used his product $+ 1$ construction to prove an $n+1$st prime not in the set. Regards, –  Matt E Jan 9 at 0:23
@MattE: In a proof by contradiction we could assume that $p_1,...,p_n$ were all the existent primes, and then$b=p_1...p_n+1$ cannot be a prime, so it must be divisible by some of the primes $p_1,...,p_n$, which it isn't, thus contradiction. In a direct proof, however, we want to show that $b$ is another prime. But to do so, we had to show that it is not divisible by any prime which could be between $p_n$ and $\sqrt b$. –  Stefan Hamcke Jan 9 at 0:38
@MattE: Or I am wrong and we consider cases: 1) $b$ is prime. 2) If $b$ is not prime, then since it is not divisible by $p_1,...,p_n$ it must be divisible by some prime $p$ between $p_n$ and $\sqrt b$. So in any case there is another prime. –  Stefan Hamcke Jan 9 at 0:39
@StefanHamcke: Dear Stefan, Every number $> 1$ is divisible by some prime $p$. Obviously $p_i$ ($i = 1,\ldots, n$) can't divide $p_1\cdots p_n + 1$ (otherwise it would also divide $1$ !), and so $p \neq p_1, \ldots, p_n$. I don't see why you need to worry about sizes of things. Regards, –  Matt E Jan 9 at 0:43
@MattE: My question was whether in Euclids proof it is proven directly that $b=p_1...p_n+1$ is prime, or whether we consider the cases "1) $b$ is prime 2) $b$ is not prime", and conclude the existince of another prime, be it $b$ or some smaller number between $p_n$ and $b$. But I just learned about the Euclid numbers where they say that not every Euclid number is a prime, so it's clear now. I was wrong in my understanding of how the direct proof by Euclid works. Regards, –  Stefan Hamcke Jan 9 at 0:48

I want to write an answer about the logic of the proof. This is a common source of confusion because the proof is often presented as a proof by contradiction, although it can be written as a direct proof using the same ideas.

I will present two proofs of the result, one by contradiction and one by direct reasoning. For the first part of this answer, I will use the ordinary, informal, mathematical understanding of "proof by contradiction" and "direct proof". In the last section, I will comment further on that understanding among logicians.

I will also assume we already know that every natural number larger than 1 has some prime factor.

Here is one telling of Euclid's proof by contradiction, which can be seen in other answers here:

Proof 1 Working by contradiction, assume the result is false. Then there are only finitely many prime numbers. Write them as $p_1, p_2, \ldots, p_n$ and form the number $q = p_1p_2\cdots p_n +1$. Then $q > 1$, and so $q$ is divisible by a prime. But the remainder of dividing $q$ by $p_i$, for any $i\leq n$, is 1. So $q$ has no prime factors, which is a contradiction.

To write a direct proof, in the sense of ordinary mathematics, we need to clarify what it means to prove directly that a set is infinite. Although the naive definition of "infinite" is "not finite", the way to create the direct proof in ordinary mathematics is to move to a different characterization of "infinite" which is phrased in "positive" rather than "negative" terms. One such characterization says that there are infinitely many primes if and only if there is an unending sequence $p_1, p_2, \ldots$ of distinct primes. We don't care whether the sequence includes all primes, it just has to contain some of them, but it can't repeat or end.

Using that characterization of infinite sets, we can recast the proof above as a direct proof:

Proof 2 We inductively construct a sequence $p_1, p_2, \ldots$ of distinct primes. To start, let $p_1 = 2$. Now, for the "inductive step", assume we have constructed distinct primes $p_1, \ldots, p_n$. Form the number $q=p_1p_2\cdots p_n+1$. This number $q$ is greater than 1, so it must be divisible by some prime $p$. But the remainder of dividing $q$ by $p_i$ for any $i\leq n$ is 1, so $p$ cannot equal $p_i$ for any $i \leq n$. Thus we can take $p_{n+1} = p$. Continuing in this way, we can construct an infinite sequence $p_1, p_2, \ldots$ of distinct primes. In particular, this shows that there are infinitely many primes.

### Advantages of the direct proof

There are several advantages of the direct proof (proof 2) over the proof by contradiction (proof 1).

First, the direct proof gives an algorithm that can be used to enumerate a sequence of primes. Not every direct proof gives an algorithm, but many do. So the direct proof here gives us more than the statement of the theorem requires. This is often the case with direct proofs and is one reason to favor them.

Second, because the direct proof never makes any false assumptions, every statement in the direct proof is true. This is not the case for the proof by contradiction, as Michael Hardy has mentioned in a separate answer. In a proof by contradiction, some statements may be proved using the false assumption that starts the proof. So if we pull a statement haphazardly from the middle of the proof, we have no way to tell whether it is true or not without further analysis.

This leads to a common confusion about Euclid's proof, which underlies the original question here. The confused idea is that if $p_1, \ldots, p_n$ are primes then $p_1p_2\cdots p_n + 1$ is also prime. As the question statement shows, that is false. But it can be deduced from the statements in the proof, in some way, by haphazardly pulling statements from the middle of the proof by contradiction and then proceeding as if those statements were true. Some ways of writing the proof by contradiction suggest this misinterpretation more strongly than mine.

As soon as you make the false assumption in a proof by contradiction, everything else in the proof is overshadowed by that assumption, in the sense that you cannot rely on any later statement of the theorem being true unless you can prove that statement separately. This is another practical reason to prefer direct proofs.

### An aside on formal logic

So far I have been using the informal, "naive" understanding of direct proof and proof by contradiction. This is how mathematicians use these terms outside of formal mathematical logic. For most mathematical purposes, you want to use this informal terminology, because that is how other mathematicians will interpret it.

In mathematical logic, where mathematical reasoning itself is our area of study, we have a more formal understanding of "proof by contradiction". This is particularly important in constructive mathematics (also called intuitionistic mathematics in common usage) where they have to be particularly careful about negation and proof by contradiction.

In that setting, the proof "by contradiction" above is actually viewed as a direct proof that "the set of primes is not finite", assuming appropriate axioms including "every number greater than 1 is divisible by a prime". This is because a statement of the form "not $P$" is taken to be an abbreviation for "$P$ implies $\bot$", where $\bot$ is an identically false proposition like $0=1$. Proof 1 above can be turned into such a proof as follows.

Proof 3 We want to prove that the set of primes is not finite. So we assume that there are only finitely many prime numbers. Write them as $p_1, p_2, \ldots, p_n$ and form the number $q = p_1p_2\cdots p_n +1$. Then $q > 1$, and so $q$ is divisible by some prime, which must be in the original list. Call that prime $p_j$. Then the remainder of dividing $q$ by $p_j$ is $0$. But we can compute the remainder of dividing $q$ by $p_j$ to be 1 as well. Thus $0=1$. This proves that the set of primes is not finite.

What makes this a "direct" proof in the formal sense? It can be proved (with appropriate axioms of number theory) in minimal logic, which is a reasoning system that does not have the inference rule for proof by contradiction.

In constructive mathematics, they often redefine concepts that have "negative" definitions in ordinary mathematics. In particular, they would usually define "$X$ is infinite" to mean there is an infinite sequence of distinct members of $X$. This is a stronger statement, in a constructive setting, than "$X$ is not finite". In that setting, although proof 3 shows them that the set of primes is not finite, it does not show them that the set of primes is infinite. But the original direct proof (proof 2) does show them this, because proof 2 is also constructively valid (with appropriate axioms for number theory).

The fact that the proof is constructively valid is closely related to the fact that it gives an algorithm for enumerating an infinite set of primes. Even for mathematicians who are unworried about constructive math, that algorithm is likely to be of interest. A key intuition from logic is that these two topics (constructive provability and algorithms) are closely intertwined.

This entire issue is somewhat similar to the distinction between proof by contrapositive and proof by contradiction, which I wrote about at http://math.stackexchange.com/a/705291/630

-
Dear Carl, In the third-to-last para., I think you mean "the original direct proof (proof 2)", rather than "(proof 1)" (as is currently written). Or maybe I got confused? Cheers, –  Matt E Mar 17 at 16:43
@Matt E: thanks for catching that typo –  Carl Mummert Mar 17 at 16:45

Maybe the other answers already have it, but your table is constructed in the actual natural numbers, whereas in the hypothetical natural numbers with a greatest prime, it is showable that the product of all primes (which hypothetically may be much larger than your table) plus 1 is prime. This hypothetical natural numbers explodes, so you can't test it.

-
. . . and this is one of several reasons it's better not to write it as a proof by contradiction: precisely because the point made in this posted answer is harder to understand than is Euclid's actual proof, which was not by contradiction. (See my posted answer to this question.) –  Michael Hardy Jan 9 at 3:52
Maybe textbooks present it as a proof by contradiction as a way to encourage use of the method? It sure is an effective method for getting things proved, though its very power makes the insight harder to see here. –  Jacob Wakem Jan 9 at 4:26

When you examine those numbers, you can see that they are divisible by the numbers greater than $p_k$. but originally Euclid assumed the greatest prime number is $p_k$.

In normal conditions, if you assume any prime number $p_k$, then $2 \cdot 3 \cdot 5 \cdots p_k + 1$ can be divisible by some prime number $p_n$ which is greater than $p_k$. but the problem assumes the prime number set is limited and there is not a prime number greater than pk.

For example, in the $30031$ case. you assume $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031$ but it is divisible by $59$ and $509$ which are both greater than 13. If 13 was the last prime number, than 30031 must have also been a prime number. That is the idea.

-
Euclid did not assume anything about a greatest prime number. He just said that if $A$ is any finite set of primes (for example $A=\{5,7\}$) then the number $\left(\prod A\right)+1$ has prime factors not in $A$ (in this example those are $2$ and $3$). –  Michael Hardy Jan 10 at 17:54

The proper way to express Euclid's idea in Mathematica would be something like this:

LimitedPrimeQ[x_, y_] := Not[Or@@(Divisible[y,#]&/@Prime/@Range[x])]
f[x_] := Product[Prime[n], {n, 1, x}] + 1
TableForm[Table[{f[x], LimitedPrimeQ[x, f[x]]}, {x, 1, 20}]]


Here LimitedPrimeQ checks whether y is divisible by the first x primes. If there were only x primes in total, as the assumption of the proof by contradiction states, then this would be equivalent to PrimeQ. But the above will print True for every single row, and you can proove that it does so for any row, just as Euclid did.

-
Wow, it's hard to understand how mathematicians stumbled along writing things in plain ol' math notation before Stephen Wolfram invented this much more clear, concise and attractive language for expressing mathematical ideas! –  jwg Jan 10 at 9:03
@jwg: And you wouldn't believe how long it took me as a Mathematica novice to figure out the syntax above. With sage I'd have been that much faster… But I do believe in trying to adapt to people's language when explaining stuff, and there are those who think in Mathematica. Thus my effort. I could have added proper math notation as well, but others already did that, so I concentrated on the code. –  MvG Jan 10 at 9:12
Sorry. You were quite right to respond to the OP in Mathematica since they used it. –  jwg Jan 10 at 9:29
@jwg: No need to feel sorry, I didn't feel criticized. In fact I wholly agree with your view. –  MvG Jan 10 at 10:16

There is an older post from 2011 that you should check out: Is there an intuitionist (i.e., constructive) proof of the infinitude of primes?.

Also you should have a look at a proof (attributed to Filip Saidak) that runs as follows:

Let $n \gt 1$ be a positive integer. Since $n$ and $n+1$ are consecutive integers, they must be coprime, and hence the number $n_2 = n(n + 1)$ must have at least two different prime factors. Similarly, the integers $n(n+1)$ and $n(n+1)+1$ are consecutive, therefore coprime, hence the number $n_3 = n(n + 1)(n(n + 1) + 1)$ must have at least three different prime factors. Now continue this process indefinitely.

-

Your own experiment actually proves the infinitude of primes!

You are considering the set of first n primes. Now consider the product of the primes in this set other than '2'. Let us consider this number as 'x' an odd number. Now what you have done is multiplying this 'x' by '2' and adding '1' to the result. This is nothing but the expression '2x+1' again an odd number.

From your experiment you obtained the result that '2x+1' may or may not be prime. Consider the case where the result is not a prime number. This means that out of all the odd numbers between the largest prime that you had considered and '2x', at least one is a prime.

-