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:

3True7True31True211True2311True30031False510511False9699691False223092871False6469693231False200560490131True7420738134811False304250263527211False13082761331670031False614889782588491411False32589158477190044731False1922760350154212639071False117288381359406970983271False7858321551080267055879091False557940830126698960967415391False

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?

Answer

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.

I had a joint paper with Catherine Woodgold about this in the Mathematical Intelligencer in autumn 2009. “Prime Simplicity

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 p1pn+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 p1pn+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 p1pn+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.

Attribution
Source : Link , Question Author : Red Banana , Answer Author : Michael Hardy

Leave a Comment