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?

• They are the Euclid numbers, it is not known whether there are infinitely many Euclid primes. Jan 9 '14 at 0:03
• Wikipedia: Primorial prime. Jan 9 '14 at 9:28
• You shouldn't say "infinite primes" if you mean "infinitely many primes". Only if there is more than one "infinite prime" (whatever that might be) would you have "infinite primes". $\qquad$ Dec 9 '16 at 21:38
• @MichaelHardy I'm from Brazil and have portuguese as my native languange. At the time of this question, I didn't know about this distinction (at some minutes ago, I also didn't know about it - discovered only when I read your comment). Dec 9 '16 at 23:06
• @OppaHilbertStyle : Many native English-speaking confused students make this same mistake. Dec 10 '16 at 4:56

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). Jan 9 '14 at 17:59
• @MarcvanLeeuwen : That is true; I was translating into modern concepts. Jan 9 '14 at 18:04
• @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. Jan 10 '14 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." Jan 11 '14 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. Jan 11 '14 at 9:52

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{}$ Jan 9 '14 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. Jan 9 '14 at 17:07
• @JulienFr : It was not Euclid who claimed that; it was later writers. Jan 9 '14 at 17:15

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

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

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\,$$ and some (new!) prime factor of $$\,n\!+\!1 > 1$$.

• 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. Jan 9 '14 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. Jan 9 '14 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. Mar 17 '14 at 11:51
• You might find this humorous. I lifted your 'Remark' logic over to my, now, somewhat convoluted setting at math.stackexchange.com/q/3009367/432081 Nov 23 '18 at 12:10

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. Feb 2 '14 at 18:55

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.

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 https://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, Mar 17 '14 at 16:43
• @Matt E: thanks for catching that typo Mar 17 '14 at 16:45
• 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 is true of typical proofs, but it is not at all intrinsic to so-called indirect proofs but rather an ancient artifact of prose proofs. Many formal systems do not have this problem, and so one should clearly distinguish between proofs that mathematicians write and the logic underlying them. Also, there's a lot hiding in the "..." in the version proposed for a constructive statement and proof. Unending lists are non-existent in the real word. =) Apr 3 '15 at 1:03
• I'm quite late to the party, but isn't the "positive" definition of infinite as "unending" still a negative definition, because "unending" means "without an end" which is essentially the same as "not finite"? Or am I thinking about this wrong? Jun 5 '19 at 18:58
• Also, other answers mention that an arbitrary set of primes multiplied together + 1 is not always a prime, which is also stated in the question, so I think your inductive proof fails at the point you assume that. Jun 5 '19 at 19:05

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??? Jan 9 '14 at 15:23
• It is a proof by contradiction. This fact is not needed to understand the OP's question.
– jwg
Jan 9 '14 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. Jan 9 '14 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 '14 at 17:39
• @AnonymousPi No need to be mean. Jan 9 '14 at 19:55

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.) Jan 9 '14 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. Jan 9 '14 at 4:26
• @MichaelHardy It is good to have things that are hard to understand. This exercises the understanding. Jan 1 '16 at 16:15
• It is not good to write proofs intended to be understood by students or by ones fellow mathematicians in a way that makes them hard to understand or makes the proof appear more complicated than it is. There are lots of things that one can assign as exercises in understanding without making things appear more complicated than they really are. ${}\qquad{}$ Jan 2 '16 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, Jan 9 '14 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$. Jan 9 '14 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. Jan 9 '14 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, Jan 9 '14 at 0:43
• @StefanHamcke : In a direct proof, one does NOT show that $b$ is another prime, but rather that the prime factors of $b$ are not among the primes $p_1,\ldots,p_n$. Jan 10 '14 at 17:42

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$). Jan 10 '14 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 '14 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 '14 at 9:12
• Sorry. You were quite right to respond to the OP in Mathematica since they used it.
– jwg
Jan 10 '14 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 '14 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.