Talk:Euclid's theorem

Proof by contradiction

Euclid did not use proof by contradiction, he never assumed there are finitely many primes 128.146.115.217 (talk) 20:16, 8 January 2008 (UTC)

It seems that Euclid also does not claim that 'there are infinitely many prime numbers'. Euclids statement seems much closer to 'for every finite list of prime numbers, there is a prime number not on the list'. What does infinite mean here really? If it means not finite, then the argument by contradiction is hidden in 'therefore there must be infinitely many prime numbers' as stated in this article (Euclid does not need this since he never makes this step it seems). I don't think the comments about argument by contradiction in the article at the moment are helpful, at least not in the context that they are made. When a contradiction is invoked to prove this theorem along Euclids lines, the statement of the theorem is typically a negation of something (the set of primes is not finite). In this case, argument by contradiction is the only way to prove the statement. — Preceding unsigned comment added by David Eklund (talk • contribs) 04:46, 8 March 2012 (UTC)

The main point is that whether or not the argument follows Euclid exactly or some variant is used where the whole statement is a negation (and proven by contradiction) is of rather minor importance. One might note though that there is a significant difference between constructing a prime number not on Euclids finite list, compared to simply assuming that there is no such thing and deriving a contradiction.

Perhaps one could say that Euclid does more than showing that there are infinitely many primes. — Preceding unsigned comment added by David Eklund (talk • contribs) 05:39, 8 March 2012 (UTC)

What Euclid actually proved is that given any set of exactly THREE primes, there is a fourth prime not in the list. He says that he's going to prove that the primes are greater than "any given multitude" of primes, but he only addresses the case that the "multitude" contains three primes. Mnudelman (talk) 04:10, 17 October 2013 (UTC)

Euclid assumes that his readers are reasonably intelligent and can see that his proof involving three primes can be trivially extended to more than that.

Technically, what Euclid offers is a proof by cases. Taking P to be the product of the numbers in the given list, he considers

1. That P+1 is prime, and
2. That P+1 is not prime.

The real work is done in deriving a contradiction from the second case. The Euclid's Theorem article now claims that "Euclid's proof deduces the infinitude directly," whatever that means — if it excludes either proof by cases or proof by contradiction, it is incorrect, since Euclid employs both approaches. My attempt to delete that claim as well as the claim that attributing proof by contradiction to Euclid is "erroneous" was reverted by Wcherowi, according to whom "This edit destroys the intent of the previous citation … ." Perhaps Wcherowi is referring to the citation from Hardy & Woodgold in Mathematical Intelligencer; not having access to this publication, I cannot dispute Wcherowi's assertion. However, Euclid derives from the assumption that P+1 is not prime the conclusion that some prime is a divisor of 1, "which is absurd" according to the proof of Proposition 20 in this translation of Book IX of the Elements. Whatever Hardy and Woodgold may have claimed and however "deduces directly" may be understood, there is indisputably a reductio ad absurdum in Euclid's argument. May I not edit the article Euclid's Theorem to say so?

Peter Brown (talk) 20:58, 8 November 2019 (UTC)

recent proofs?

It would be great if there were some references that attest to the significance of the recent proofs. I'm sure there are tons of proofs of Euclid's theorem, what makes these proofs so special that they need to be included in this article?--345Kai (talk) 03:44, 12 September 2011 (UTC)

Hey... just been looking at the proof using the irrationality of Pi. ... I'm not sure if that series as given is a legitimate thing- tried it out using the first hundred or so primes and got Pi=3.15... There doesn't appear to be any citations in that part of the page, so it's possible that that formula is a hoax. If it is a legitmate formula, can someone please give a citation, and if it isn't, then it should probably be take down. — Preceding unsigned comment added by 121.72.237.205 (talk) 02:13, 28 May 2012 (UTC)

I agree with 345Kai's statement. The reason you get π=3.15 is because, as stated in the article, "If there were finitely many primes, π would be rational." You mentioned trying the first hundred or so primes; this does not work because as long as you have finitely many numbers inside the formula, you approach but never reach pi. However, your number may not be displayed accurately because there is a limited amount of space on a calculator or computer screen. There is not enough room for an irrational or even a rational number with many digits to be displayed properly, and the number is automatically rounded to a more appropriate size. This is Madness³⁰⁰ 04:47, 30 June 2012 (UTC)

I have a different issue with this "proof", namely that it's a circular argument. (And I apologize if this proof was included as a joke and it just went over my head.) Every proof I've seen that $\pi$ is irrational actually uses the fact that there are infinitely many primes. The proofs of irrationality usually start off by saying something like, "Assume $\pi$ is rational. Now let $p$ be a prime to be specified later, and define the following polynomial which depends on $p$." Then later in the proof, you require that $p$ has to be greater than a few different quantities that come up during the proof. The point is that in order to guarantee that you can find such a prime number, you need to know that there are primes of arbitrarily large size, and therefore you need to know there are infinitely many primes.

So can we delete this "proof"? Ceresly (talk) 20:19, 31 March 2019 (UTC)

I don't know which proof of the irrationality of pi you are referring to. For instance Niven's classical proof (which can be found in the Niven-Zuckerman) certainly doesn't appeal to an infinity of primes. Under the assumption that pi = a/b is a rational number, it is shown that there is an integer strictly between 0 and 1 (see for instance [1]) Sapphorain (talk) 20:57, 31 March 2019 (UTC)

There certainly seem to be proofs of pi's irrationality that don't depend on there being infinitely many primes, so this might very well be valid. But it's also unsourced, and there might very well be some subtle bits that aren't immediately obvious that cause some issues. So I, at least, wouldn't object if it were removed. –Deacon Vorbis (carbon • videos) 20:51, 31 March 2019 (UTC)

Aha... Niven's proof does not use primes! You're right. He does use primes though for his more general proof that the cosine of a non-zero rational number is irrational (from which you can quickly conclude the $\pi$ is irrational). It's very odd to me that this special case does not use primes!Ceresly (talk) 21:30, 31 March 2019 (UTC)

New"?" Easier Argument For the Infinitude of Primes?

Providing this argument isn't false (because it definitely is not a proof) it may be the most easy-to-understand argument for the infinitude of the primes.

Rather than ordering numbers by quantity, order them in a different way. Order them like this, where all the letters are the prime numbers (which we know not the quantitative value of yet):

A, B, 2A, 2B, C, 3A, 3B, 3C, 2C, D, 4A, 4B, 4C, 4D, 3D, 2D, E, 5A, 5B, 5C, 5D, 5E, 4E, 3E, 2E, F, 6A, 6B, 6C, 6D, 6E, 6F, 5F, 4F, 3F, 2F, G, 7A, 7B, 7C, 7D, 7E, 7F, 7G, 6G, 5G, 4G, 3G, 2G, H,.......

I think the pattern can be seen by now, provided there are no typos. It's kind of organizing numbers in such a way that they are put in order by groupings of primes rather than by quantity. A is the prime of lowest value, B is the prime of second lowest value, etc.

Using this system, every prime and composite number should be able to be generated eventually, even though they'll be generated out of quantitative order, and some composite numbers will be repeated. (If this were a proof I'd probably have to reference the fundamental theorem of arithmetic here.) Provided all primes and composites are generated by the pattern above, it's pretty easy to see that by following the pattern, you'll have to generate a prime (represented by the letter characters) in order to keep counting once you run out of multiples of previous primes. Therefore the primes are infinite.

Theboombody (talk) 15:53, 1 March 2014 (UTC)

This argument doesn't work. You've assumed what you are trying to prove -- that at the point in your pattern where you go "...4X, 3X, 2X, hmm, next would come the 25th prime, is there a 25th prime?" there will always be a new prime. 109.246.123.214 (talk) 22:46, 28 April 2019 (UTC)

"Weasel word"

(moved this from my talk page, where it doesn't serve any useful purpose. Sapphorain (talk) 20:13, 6 September 2018 (UTC))

Hi. I'd like you to reconsider a recent revert you made at Euclid's theorem. I had reverted the removal of "well known" in the lead and you reverted my revert claiming it was a weasel word. Most uses of that term are definitely "weasily", but I think that in this case that is not true and this clearly falls into the exception mentioned in that guideline. There are literally thousands of proofs of this result, most of which are justifiably obscure. The article goes on to talk about several proofs, each labeled by its author. In my mind, that labeling is itself an indication of the notability of the proof and the fact that these have been selected qualifies them as being well known (note that I am only referring to the main body of the article as there is a section of more modern proofs that I don't think qualify as being well known). I think that the expression "well known" used in the lead here is serving a function and should be present. Thanks for considering this. --Bill Cherowitzo (talk) 18:03, 6 September 2018 (UTC)

« Well-known » might in some cases (in everyday’s life and in the media) not be a weasel word, but certainly not in any specialized scholarly subject. In the present case its use is completely subjective. I am a number theorist, and even though the theorem itself and its classical historic proofs are of course « well-known » to me, some of the proofs presented in the article were not. For a mathematician working in another field I should say that only Euclid’s is «  well-known ». It is doubtful that even this proof is familiar to a non-mathematician scientist. And the great majority of other people’s knowledge concerning prime numbers comprises nothing more than the definition. Wikipedia is not a mathematical, let alone a number theory, encyclopedia.Sapphorain (talk) 20:13, 6 September 2018 (UTC)

Proof by contradiction again

Response to Peter M. Brown's comments in the above section #Proof by contradiction. No one is arguing that Euclid does not employ a reductio ad absurdum argument in a portion of his proof. However, lots of direct proofs use such techniques in the course of the argument and are not considered proofs by contradiction. This is the thesis of the Hardy article, namely that the overall structure of the proof is not that of a proof by contradiction. Of course, Euclid's proof can be tweaked so that it is a proof by contradiction and many authors have used this revised vision to claim that that is what Euclid did. Euclid's proof is, as you have noted, a proof by cases, which is a direct proof technique (unless you prove that all cases lead to contradictions), and it does not matter what technique is used to prove any individual case. --Bill Cherowitzo (talk) 22:52, 8 November 2019 (UTC)

Hello, Mr. Cherowitzo.

I have deleted from the text of Euclid's theorem § Euclid's proof the sentence

"While such a proof does follow from Euclid's method, Euclid's proof deduces the infinitude directly"

and replaced it by other text. My objections to the text prior to my edit are as follows.

• Euclid's method

Perhaps some scholar has a good handle on the methods employed by a mathematical genius 2300 years ago. Perhaps you do. Without some sourcing, though, we cannot assume that the reader shares that understanding.

In the translation I am using (by Heath, not Williamson), the proof ends with

Therefore the prime numbers A, B, C, G have been found which are more than the assigned multitude of A, B, C.

So Euclid has only proved that there are more than three primes.

Euclid's own statement of of the theorem, remember, is

"Prime numbers are more than any assigned multiple of prime numbers"

or, in Williams' translation cited in a footnote in Wikipedia,

"The prime numbers are more numerous than any proposed multitude of prime numbers."

Thousands of years after Euclid, we can reformulate the proof as does the so-called "paraphrase" in the Wikipedia exposition, using machinery that Euclid did not have and proceed to use additional tools that he lacked to produce a proof that actually concludes with the theorem as he stated it. But these methods are not Euclid's. His "method" involves relying on the readers' intuition to overcome the logical gap between what he actually proved and what he set out to prove. The sentence I deleted claimed, falsely, that "such a proof", viz. the proof in the "paraphrase", does follow from Euclid's method.

• deduces the infinitude directly

You have your ideas as to what is a direct deduction. I think that any proof that uses reductio ad absurdum even in a subsidiary result is not direct. We can agree to disagree on terminology, but we cannot assume a particular understanding on the part of the reader. Importantly, neither translation of the theorem statement mentions infinitude.

Peter Brown (talk) 16:10, 9 November 2019 (UTC) Revised 02:48, 10 November 2019 (UTC)

I would characterize these remarks as "Much Ado About Nothing". The sentences you object to are cited, while none of your additions have a valid citation. The citation you gave is a Master's thesis from an education department, not quite a reliable source for historical matters. Furthermore, I could not find the quote that you attribute to this source since you did not provide a page number, and it is highly unlikely that this thesis, concerning the precursors of calculus, would have much to say about Euclid's concept of the infinite of a scholarly nature.--Bill Cherowitzo (talk) 23:00, 9 November 2019 (UTC)

OK, I'll find a better citation or delete the claim. But what do you mean by "The sentences you object to are cited"? The only sentence I objected to read

"While such a proof does follow from Euclid's method, Euclid's proof deduces the infinitude directly."

This was not cited. I believe that, above, I have detailed my objections to it. If you wish to defend it, please go ahead. That's what talk pages are for.

Peter Brown (talk) 23:32, 9 November 2019 (UTC)

OK, I've replaced the citation. Give me a week, though, and I'll find some even better sources. Peter Brown (talk) 00:10, 10 November 2019 (UTC)

I hope you do. The current citation cites the throw away line in a discussion that does not even mention Euclid. While I am familiar with the objections of some ancient Greeks to the concept of infinity, you are asserting that Euclid was in agreement with them and I see no support for that claim. I do not believe it will be possible to find any citation that does support this since we know so little about the man and what he thought. To clean up a couple of stray comments: firstly, Proof by cases is a direct proof technique - just look at the page, it says so in the first paragraph. I can also back that up with several text citations that say the same thing; secondly, although the lines, as you point out, are not cited in the Hardy paper, that paper does quote the philosopher Frazén who does say this; finally, I believe that you are misreading the phrase "While such a proof does follow from Euclid's method, ...". This refers to proofs by contradiction and not to a generalization of Euclid's argument, as is made clear by the conclusion of the sentence. --Bill Cherowitzo (talk) 21:22, 10 November 2019 (UTC)

You're right, I remembered in error what "such a proof" referred to. I should have checked. The context of the sentence was

Euclid is often erroneously reported to have proved this result by contradiction beginning with the assumption that the finite set initially considered contains all prime numbers. While such a proof does follow from Euclid's method, Euclid's proof deduces the infinitude directly.

Whether "such a proof" does follow from Euclid's method depends on what one means by "follow", which is kind of a weasel word in this context. Euclid's methods were utterly inadequate to derive a contradiction from "the assumption that the finite set initially considered contains all prime numbers" since he did not possess the set-theoretic machinery required to make this assumption and deduce its consequences. Is it being claimed, rather, that such an argument could be constructed by augmenting his tools with this machinery? In this much broader sense of "follow", the point must be granted. I do not apologize for deleting a sentence with so imprecise a term.

"Euclid's proof deduces the infinitude directly" is flat-out incorrect. Euclid deduced nothing about infinitude, only that there are at least four primes. Does his argument convince a rational reader that "The prime numbers are more numerous than any proposed multitude of prime numbers," as Williams translates the hypothesis? Yes, because Euclid provided a template for proving, given any such multitude, that it lacks some prime number. That isn't a deduction but it does everything Euclid wanted.

And I do owe you a citation.

Peter Brown (talk) 23:40, 10 November 2019 (UTC)

Really? There is no problem with the word "follows", as it is a trivial matter to turn any direct proof into a contradiction proof in a totally artificial way. And bringing up Euclid in this context is a red herring, we are talking about what authors after him have done to his proof and what Euclid would or could have done is just not germane. As to the statement that he only proved that there are at least four primes, I can only say that that is an extremely narrow view that confuses style with substance. All of the proofs in Book IX that deal with an arbitrary number of integers are styled in this manner; starting with the assumption that three or four or five integers are given, as many as are needed to show the general outline of the argument and then completing the argument for them. It is perfectly clear that Euclid understood that he was giving general arguments in specific cases; as is done today to illustrate a proof without getting involved with excessive terminology and notation. To claim that this style of writing indicates a lack of understanding of the concept of infinity seems far fetched to me, although it is also clear that he would not use modern terminology to talk about it. --Bill Cherowitzo (talk) 20:14, 11 November 2019 (UTC)

The section should not be entitled "Euclid's proof" if what is really under discussion is "what authors after him have done to his proof." A normal reader will interpret "Euclid's proof" to refer to a proof that Euclid actually produced, which does not "deduce the infinite" either directly or indirectly.

I have not said anything at all about Euclid's style of writing.

Peter Brown (talk) 02:22, 12 November 2019 (UTC)

Will your nit-picking never end? I have amplified the section (with sources) to give a rounder picture of the technique. I've removed your claim about what Euclid would not do as it was uncited. If and when you do find a reliable source that says this about Euclid, we can put it back in. --Bill Cherowitzo (talk) 00:08, 13 November 2019 (UTC)

In your edit summarized as "Amplification and removing unsupported claim", the amplification is very nicely done. My compliments. The so-called unsupported claim, however, was supported (though not very well) by the Austin article. Once I come up with better support, I shall restore the claim in some form using new citations along with the Austin article as support. So long for now. Peter Brown (talk) 01:30, 13 November 2019 (UTC)

Misleading and obsolete notions

I find some statements in this article misleading or out of topic:

(1) Using "Proof by construction" as the title gives the impression, that Saidak's proof is something special, or rare, or unusual etc. However, there are several other direct (induction) proofs of the infinitude of primes. For instance,

(i) consider the infinite sequence e(0), ..., e(i), e(i+1), ... given by e(0) := 2 and e(n+1) := 1 + e(n)*e(n-1)*...*e(0). Prove by induction that all members of the sequence are pairwise co-prime, which entails the truth of the statement;

(ii) consider the infinite sequence f(0), ..., f(i), f(i+1), ... of Fermat numbers defined by f(n) := 1 + 2 ^ (2 ^ n). Prove by induction that all members of the sequence are pairwise co-prime, which entails the truth of the statement;

(iii) consider the infinite sequence a(0), ..., a(i), a(i+1), ... given by a(0) := 3 and a(n+1) := pf(a(n)!-1), where pf(x) is the smallest prime factor of x (if x ≥ 2). Prove by induction that a(m) < a(n) for all m < n, which entails the truth of the statement;

(iv) consider the infinite sequence b(0), ..., b(i), b(i+1), ... given by b(0) := 2 and b(n+1) := pf(b(n)!+1). Prove by induction that b(m) < b(n) for all m < n, which entails the truth of the statement (this is the proof skeched in subsection "Variations" of section "Euclid's proof).

(2) Why is it stressed that Euclid's Lemma is not used in Saidak's proof? This is neither unique nor eminent - none of the proofs under (1) use Euclid's Lemma.

(3) What is the remark that Saidak's proof does not resort to "reductio ad absurdum" good for? Neither the proofs in (1) nor in this article are indirect proofs. In particular it is explicitly mentioned in section "Euclid's proof" that it is not by contradiction.

(4) Whether the infinitude of primes is proved directly or indirectly is irrelevant for the subject and respective material should be eliminated as it may irritate people. Also using three different notions (proof by contradiction, indirect proof, reductio ad absurdum) for the same subject may confuse people. This should be discussed elsewhere, i.e. in an article about (mathematical) Logic or Proof Techniques or something similar.

(5) "Proof by construction" is the wrong term for Saidak's proof. It is an induction proof (like the proofs in (1) ).

Jack Rusell (talk) 21:36, 15 November 2019 (UTC) Jack Rusell (talk) 21:41, 15 November 2019 (UTC)

Link wrong?

Moved from User talk:Deacon Vorbis

 – –Deacon Vorbis (carbon • videos) 17:01, 2 May 2020 (UTC)

Hi! You claim that the link primorial at Euclid theorem is wrong, without sufficient details! This link can't be wrong! The primorial is a finite product of exactly n primes which are considered in the proof by negation of the theorem which says that the primes are an infinite set, not a finite one as would seem from considering the first n primes like there would be NO other prime.--109.166.138.105 (talk) 16:58, 2 May 2020 (UTC)

The primorial is the product of the first n primes. The proof in the article doesn't require the list to be of the first primes. It could be using {2, 11, 97}, which yields a product of 2,134, which isn't a primorial. –Deacon Vorbis (carbon • videos) 17:04, 2 May 2020 (UTC)

I think it must be said that the given example of just three primes {2, 11, 97} picked arbitrarily doesn't make sense, the product of these primes plus one, 2135, has 5 as the smallest divisor and 7 and 61 as other divisors. So the example is not useful to finding a prime divisor of 2135 greater than the greatest prime in the picked list, 97, thus it cannot find an additional prime beyond 97 or equivalently fails to illustrate/proof step/case by step/case the infinity of primes. So this failed (counter)example indicates that the proof of this theorem of infinity of primes must use the product of ALL previous primes, namely the primorial.--109.166.138.105 (talk) 15:08, 3 May 2020 (UTC)

There is a statement in the article: "Consider any finite list of prime numbers p1, p2, ..., pn. It will be shown that at least one additional prime number not in this list exists." The meaning of this excerpt from article cannot be other than the use of primorial, as the failed example {2, 11, 97} shows.--109.166.138.105 (talk) 15:13, 3 May 2020 (UTC)

For proving the infinity of the set of primes the method of an arbitrarily selected finite subset of primes only works when the number formed by addition of a unity to the product of the arbitrarily selected primes P + 1 is itself a prime, like in the following slightly modified example of arbitrarily selected primes {2, 11, 103} for which (the product 2266 plus 1) 2267 is a prime greater than 103. The theorem applies to or states something re the product plus one regardless of being prime or not prime.--109.166.138.105 (talk) 16:26, 3 May 2020 (UTC)

So from the above aspects the presence of primorial in the proof is needed/requested by the statement of the theorem.--109.166.138.105 (talk) 16:35, 3 May 2020 (UTC)

I'm afraid you're mistaken. The list in the proof is not required to be consecutive/exhaustive, nor is the new prime it generates required to be greater than all those already in the list. The link for the primorial is thus inappropriate. This is now straying into WP:NOTFORUM territory. Please direct any further questions to the math ref desk. –Deacon Vorbis (carbon • videos) 17:00, 3 May 2020 (UTC)

What is exactly the supposed mistake (of mine) in the above? IF "The list in the proof is not required to be consecutive/exhaustive, nor is the new prime it generates required to be greater than all those already in the list.", THEN the considered list is useless for the proof of the infinity of primes. I have analyzed your example (useless for proving infinity of primes) and slightly modified it to be partially useful for finding additional primes p_{n + 1}, p _{n + 2}, beyond the n known primes supposed as a finite set. The requirements you say are not necessary are an intrinsic part of the method of proof used by Euclid. So (I'm afraid) the mistake is yours. As long you have not specified the nature of the supposed mistake, it can't be any straying into WP:NOTFORUM territory. Please do not use the WP:NOTFORUM as an excuse for NOT acknowledging your mistake. (But I agree with you that the details/requirements of the Euclid method of proof of this theorem are interesting for a REFDesk question.)--109.166.138.105 (talk) 17:36, 3 May 2020 (UTC)

Deacon Vorbis is not wrong and you are being tedious. Your inability to understand simple statements that don't fit your POV tells it all. --Bill Cherowitzo (talk) 18:35, 3 May 2020 (UTC)

Maybe a translation of Euclid will help you: https://mathcs.clarku.edu/~djoyce/java/elements/bookIX/propIX20.html. He starts with an arbitrary set of 3 primes. He does not say it is the 3 smallest primes. He shows there is a prime which is not in the initial set. He doesn't require it to be larger than the 3 initial primes but merely different from them. The same argument works for any initial finite set of primes, so the set of all primes cannot be finite. It would be possible to let the set be the n smallest primes and this is often done in modern proofs. But that is not what Euclid did, and the section is called "Euclid's proof". PrimeHunter (talk) 19:41, 3 May 2020 (UTC)

May I add that it appears very difficult to decide whether Euclid’s recursive process eventually produces all the primes. I recall it is even a famous open problem. (I haven’t been able to get hold of the reference for this (who proposed the problem?): if somebody has this information I would be interested).

[Beginning with 2 we get 2+1=3; then 2.3+1=7 (5 is missing so far); then 2.3.7+1=43 (11, 13, 17, 19, 23, 29, 31, 37 and 41 are missing); then 2.3.7.43+1=1807 (which is prime); then 2.3.7.43.1807+1=3,263,443 (which is prime); then 2.3.7.43.1807.3,263,443+1=1,065,005,695,807 = 17.46,507.1,347,053 : we get the missing primes 17; 46,507; and 1,347,053 which is not much.... Etc.]. Sapphorain (talk) 21:28, 3 May 2020 (UTC)

@Sapphorain: Well, that's quite interesting, but may I add there is no such thing like an 'Euclid's process' mentioned in the article, let alone recursion.
Additionally, Euclid's proof doesn't rely on 'producing' primes. It even explicitly handles a case of the resulting number being composite.
Last but not least, it has nothing to do with (in)correctness of using primorial in the proof, which is the topic of this section. --CiaPan (talk) 21:51, 15 May 2020 (UTC)

The topic is not whether primorial can be used in the proof (it can), but whether Euclid used it (he didn't). The IP piped a link to primorial [2] in the section about Euclid's proof, thereby incorrectly implying that Euclid used primorial. PrimeHunter (talk) 00:47, 16 May 2020 (UTC)

Euler's proof

Euler’s proof is contained in Theorems 7 and 19 of « Variae Observations Circa Series Infinitas » (and also in paragraphs 271-279 p.224-235 of "Introductio Analysis Infinitorum (vol 1)), in which the sum of the reciprocals of the primes is shown to be $\log \log \infty$ (sic). The proof is direct and not by contradiction [3]. --Sapphorain (talk) 16:55, 29 June 2021 (UTC)

I do not see how avoiding simultaneously proof by contradiction and infinite product. Using an infinite product of infinite series would need (for the modern concept of rigor) a theory of infinite products that is out the scope of this article. So the present version does not allow extracting a direct proof. If you are able to write this alleged Euler's direct proof in modern terms, please do it.

Euler's proof that you refer to is not the one that is described here. In this article, he showed that the series of the inverses of the primes is divergent. This proves the theorem, but this is not the same proof. I ignore whether the proof attributed to Euler can be found elsewhere in Euler's work. D.Lazard (talk) 20:52, 29 June 2021 (UTC)

I think you and I take "Euler wrote" in a different way. I thought they was using "wrote" in the current diff because I couldn't write "proof" in terms of the modern concept of rigor. Perhaps you are using "wrote" to mean exactly what "Euler wrote".--SilverMatsu (talk) 01:35, 30 June 2021 (UTC)

Supposition about the Euler product for harmonic series, the reference says; On the other hand, if there were only finitely many primes, then unique factorization of positive integers into prime powers would imply that $\sum _{n}^{\infty }{\frac {1}{n}}=\prod _{P}\left(1+{\frac {1}{p}}+{\frac {1}{p^{2}}}+{\frac {1}{p^{k}}}+\cdots \right)=\prod _{P}\left(1-{\frac {1}{p}}\right)^{-1}.$ (See B). This supposition allows for the use of the Generality of algebra that Euler would have used. If we don't have the above suppositions, for Re (s) = 1, it seems that Mertens' third theorem (1874) proof is needed. (See C). For Dirichlet L-function based on non-principal characters, I found two preprints.--SilverMatsu (talk) 10:51, 30 June 2021 (UTC)

IMO, there are two problems in the present version of the WP article. One, relatively minor, is whether the proof in the WP article is a faithful transcription of Euler's ideas in a modern language. The second is that, in the reference, Euler did not claim for a proof of Euclid's theorem. More, if one looks at his systematic use of dots ("..."), it becomes unclear whether his proof uses of not Euclid's theorem, if one interprets the dots as representing infinite series. In fact, he proved a much stronger theorem, which has Euclid's theorem as a corollary, namely that the series of the inverses of the prime numbers is divergent. This make unimportant whether his proof is circular or not.

I rewrote the WP article for clarifying these ambiguities and fixing a mathematical inaccuracy (writing $\infty =\infty$ and deducing something from this). D.Lazard (talk) 14:53, 30 June 2021 (UTC)

I have reformulated this proof in a way that follows more closely Euler’s line of reasoning. Of course this means that it does not strictly abide by the modern standards of rigor. But that cannot be helped. Or rather should not be helped, especially if doing so implies coming to the conclusion that Euler’s proof of Euclid’s translated into modern terminology becomes a proof by contradiction: this brings a much more harmful contradiction, to the very line of Euler's reasoning, which was not by contradiction. Besides, the task of proving rigorously most of Euler’s theorems is a rather easy exercise (like for instance that of establishing the asymptotic behavior of the sum of the inverses of the primes up to x, which is much simpler than Merten’s proof of his (stronger) theorem).

Also, it seems clear to me that Corollarium 2 to Theorema 7 provides a direct alternate proof of Euclid’s theorem and was stated with this purpose also by Euler. --Sapphorain (talk) 12:12, 1 July 2021 (UTC)

references

• OCW Number Theory I Riemann's zeta function and the prime number theorem (PDF) (A)

• OCW Analytic Number Theory Primes in arithmetic progressions (PDF) (B)

• OCW Analytic Number Theory Dirichlet L-functions and primes in arithmetic progressions (PDF) (C)

• LeClair, André (2016). "Riemann Hypothesis and Random Walks: The Zeta case". arXiv:1601.00914. {{cite journal}}: Cite journal requires |journal= (help) (two preprints)

• França, Guilherme; LeClair, André (2014). "On the validity of the Euler product inside the critical strip". arXiv:1410.3520. {{cite journal}}: Cite journal requires |journal= (help) (two preprints)

Wrong contribution regarding information theory

The section Proof using information theory has a quite wrong contribution. Although proofs in similar directions appear even earlier, it is Chaitin that related the infinitude of primes and information theory in: G. J. Chaitin, Toward a mathematical definition of life, in The Maximum Entropy Formalism, R. D. Levine and M. Tribus, eds., MIT Press, Cambridge, 1979, 477–498.

This proof can easily dramatically simplified and does not requires information theory: Given an integer N, the beginning of the proof shows that, if $n\leq N$ and ${\textstyle n={p_{1}}^{e_{1}}{p_{2}}^{e_{2}}\cdots {p_{k}}^{e_{k}},}$ then $e_{i}<\lg N$ for every i. So, the tuples $(e_{1},\ldots ,e_{k})$ with this property encode a set of numbers containing all integers less than or equal to N. This shows $N\leq (\lg N)^{k}$ for every integer N, a contradiction. There is no need of information theory or incompressibility theorem.

IMO, a proof that can easily be simplified dramatically does not belong to an encyclopedia. The simplified proof could replace it if it can be sourced. Unfortunately I do not know any source. As it is possible that a source exists, I'll simply tag the section with {{disputed section}}. D.Lazard (talk) 13:34, 14 September 2021 (UTC)

Is that the correct tag to use? The page currently says "This section's factual accuracy is disputed.", which seems strange as no one has actually contested factual accuracy - whether there is a simpler similar proof or not, the facts of the current proof seem correct and are sourced. 2A00:79E0:4A:203:8521:3101:B81A:EB5D (talk) 14:55, 13 October 2021 (UTC)

The disputed fact is whether information theory is really used here. D.Lazard (talk) 16:51, 13 October 2021 (UTC)

Proof using an even-odd argument

A section § Proof using an even-odd argument has been recently added. I removed it, but this has been reverted. Here are the reasons of my removal:

• On such a very old subject, a source that is not discussed in any WP:secondary source must be considered as original reseaarch.
• This is presented as a proof by contradiction, which is unneeded if the proof if correctoly written.
• The proof is a variant of original Euclid's proof, with some complication added. Indeed both proofs are special cases of the following assertion: Let $p_{1}<p_{2}<\cdots <p_{k}$ be a list of prime numbers, P their product, and n and integer (possibly negative) that is coprime with P and such that $|n|<p_{k};$ then $P+n$ is coprime with both P and n, and its prime divisors are neither in the given list of primes nor a divisor of n. If $k>1$ or $n>0,$ one has $|P+n|>1,$ and $P-n$ has at least one prime divisor. It follows that the $p_{i}$ and the prime divisors of n do not form a complete list of primes, and thus that a finite list of primes is never complete.
  The new proof is the case $n=-2,$ while the original Euclid's proof is the case $n=1.$ It should be noted that the choice of a negative n in the new proof induces the need to prove that $|P+n|>1,$ an evidence in Euclid's case.
• The new proof does not give any new insight on the subject. One may consider that the above given generalization provide new insights, but we cannot use it, as it is WP:OR. In any case the proof should be rewritten for avoiding a proof by contradiction.

To editor Sapphorain: Unless you provide some more arguments for keeping the new proof, I'll removing it again in a few days. D.Lazard (talk) 13:37, 1 July 2024 (UTC)

The notion that a proof by contradiction is not « correct » if a direct proof is possible is a matter of personal taste. I usually share this opinion, especially when the proof by contradiction has no particular elegance of its own. But it is not the case here: the proof (I mean of course the first paragraph only, and wouldn’t mind if the Remark that follows is suppressed), is short and neat; it becomes a lot less interesting (and indeed a poor mimicking of Euclid’s reasoning) if one writes it « correctly », as a direct argument.--Sapphorain (talk) 13:52, 5 July 2024 (UTC)