[deleted]
The proof isn't referring to n, n+1, and n+2 -- it refers to n, n+1, and n(n+1) + 1. In your example, this would be 2, 3, and 2*3 + 1 = 7, which in fact include 3 prime factors.
A new proof of Euclid's Theorem (2006)
11–20 of 34 posts
Re: A new proof of Euclid's Theorem (2006)
#12[deleted]
You've misread the proof. They do not argue that n, n + 1, and n + 2 are co-prime; they only note that n, (n + 1), and n * (n + 1) + 1 are co-prime [and more generally they continue in the same fashion, using the basic fact that n and n + 1 are co-prime for any n].
The proof is sound. However, it is also not particularly different in essence from the classic proof; considering it so is misguided (see https://news.ycombinator.com/item?id=10889290).
Re: A new proof of Euclid's Theorem (2006)
#13Old proof: Let's produce a series of values v_1, v_2, ..., such that v_n has at least n distinct prime factors. We can do this by noting that v_n + 1 has at least one prime factor but no prime factors in common with v_n, and thus taking v_{n + 1} to be v_n * (some prime factor of (v_n + 1)). "New" proof: Let's produce a series of values v_1, v_2, ..., such that v_n has at least n distinct prime factors. We can do thi…
That's not really an accurate representation of the old proof. You've turned it around to make it look like the new one, but that's not how it is originally laid out at all.
The fundamental problem (for constructivists) with Euclid's proof is that it assumes the existence of a set of all primes, and then proves that that set is incorrect (either contains a composite, or doesn't contain at least one specific prime).
Saidak's proof, on the other hand, only assumes the existence of a single integer, and then constructs infinitely many primes from that integer.
Your restatement of Euclid's proof is basically "look, Euclid and Saidak proved the same thing", not "look, Euclid's proof is constructive too".
Re: A new proof of Euclid's Theorem (2006)
#14Off-topic, but, what's the deal with all those dashes in the document?
The markup is really weird on that page. There are empty spans in the middle of words. For example, here is how the word "positive" is represented:
positive
Re: A new proof of Euclid's Theorem (2006)
#15[deleted]
You've misread the proof. They do not argue that n, n + 1, and n + 2 are co-prime; they only note that n, (n + 1), and n * (n + 1) + 1 are co-prime [and more generally they continue in the same fashion, using the basic fact that n and n + 1 are co-prime for any n]. The proof is sound. However, it is also not particularly different in essence from the classic proof; considering it so is misguided (see https://news.yco…
You're right.
Re: A new proof of Euclid's Theorem (2006)
#16Old proof: Let's produce a series of values v_1, v_2, ..., such that v_n has at least n distinct prime factors. We can do this by noting that v_n + 1 has at least one prime factor but no prime factors in common with v_n, and thus taking v_{n + 1} to be v_n * (some prime factor of (v_n + 1)). "New" proof: Let's produce a series of values v_1, v_2, ..., such that v_n has at least n distinct prime factors. We can do thi…
That's not really an accurate representation of the old proof. You've turned it around to make it look like the new one, but that's not how it is originally laid out at all. The fundamental problem (for constructivists) with Euclid's proof is that it assumes the existence of a set of all primes, and then proves that that set is incorrect (either contains a composite, or doesn't contain at least one specific prime). S…
I think the point is you can easily remove the "deficiencies" of Euclid's proof. Basically, say: let p_1, ..., p_n be the first n primes. We can construct a new prime by examining p_1...p_n + 1. This process can be continued indefinitely.
In fact, I think the statement "this process can be continued indefinitely" is quite misleading -- to formalize this, I think you need proof by contradiction. So, the difference is the syntax used, not the actual semantics of the proof.
Re: A new proof of Euclid's Theorem (2006)
#17Old proof: Let's produce a series of values v_1, v_2, ..., such that v_n has at least n distinct prime factors. We can do this by noting that v_n + 1 has at least one prime factor but no prime factors in common with v_n, and thus taking v_{n + 1} to be v_n * (some prime factor of (v_n + 1)). "New" proof: Let's produce a series of values v_1, v_2, ..., such that v_n has at least n distinct prime factors. We can do thi…
That's not really an accurate representation of the old proof. You've turned it around to make it look like the new one, but that's not how it is originally laid out at all. The fundamental problem (for constructivists) with Euclid's proof is that it assumes the existence of a set of all primes, and then proves that that set is incorrect (either contains a composite, or doesn't contain at least one specific prime). S…
Two points:
A) Euclid never assumes the existence of a finite set of all primes (doing so at the outset is a framing adopted only by later mathematicians); people just frequently erroneously think Euclid's proof did this, never having actually read it.
Rather, Euclid constructively frames things, directly arguing that, for any finite set of primes, there is furthermore some prime outside that set. See http://aleph0.clarku.edu/~djoyce/elements/bookIX/propIX20.ht....
B) Regardless, I don't particularly care how Euclid phrased his proof; I never mentioned Euclid. Certainly, mathematicians have been aware that Euclid's insight could be framed in the way I called an "old proof" for a long, long time. The distinctions between the various framings here are trivial.
Re: A new proof of Euclid's Theorem (2006)
#18The idea of using `consecutive numbers are coprime` as the sole property for this concise proof is quite remarkable. I would definitely be interested to know if there are any other such simple proofs exist for other theorems. (i.e. ones where a new proof simplifies it massively by using a simpler property).
It seems to me that the original proof also uses "consecutive numbers are coprime" as the sole property. In particular, it looks at P = p_1 * ... * p_n and says that it is coprime to Q = P + 1; hence, there must exist another prime number.
Re: A new proof of Euclid's Theorem (2006)
#19The idea of using `consecutive numbers are coprime` as the sole property for this concise proof is quite remarkable. I would definitely be interested to know if there are any other such simple proofs exist for other theorems. (i.e. ones where a new proof simplifies it massively by using a simpler property).
What property does the classic proof use that the "new" proof does not?
From the article:
The proof just given is conceptually even simpler than the original proof due to Euclid, since it does not use Eudoxus’s method of“reductio ad absurdum,” proof by contradiction. And unlike most other proofs of the theorem, it does not require Proposition 30 of Elements (sometimes called “Euclid’s Lemma”) that states: if p is a prime and p|ab, then either p|a or p|b. Moreover, our proof is constructive, and it gives integers with an arbitrary number of prime factors.
Edit: Actually, even though the article seems to imply that the classic proof ("most proofs") uses prop 30, it doesn't really seem to.
Re: A new proof of Euclid's Theorem (2006)
#20Earlier quoted context omitted.
What property does the classic proof use that the "new" proof does not?
From the article: The proof just given is conceptually even simpler than the original proof due to Euclid, since it does not use Eudoxus’s method of“reductio ad absurdum,” proof by contradiction. And unlike most other proofs of the theorem, it does not require Proposition 30 of Elements (sometimes called “Euclid’s Lemma”) that states: if p is a prime and p|ab, then either p|a or p|b. Moreover, our proof is constructi…
The article makes suggestions here about the classic proof which aren't true.
Euclid's proof of the infinitude of the primes was not phrased in terms of an overarching reductio ad absurdum (and even had it counterfactually been, mathematicians would've long ago been able to trivially rephrase it so as not to be, showing "For any finite set of primes, there is some further prime" directly).
And the classic proof of the infinitude of the primes does not anywhere use Proposition 30 of the Elements (see for yourself at http://aleph0.clarku.edu/~djoyce/elements/bookIX/propIX20.ht... ; Proposition 31 (that every composite has some prime factor) is used, but this in turn is argued for without any invocation of Proposition 30).
Where in the classic proof would you imagine "if p is a prime and p | ab, then p | a or p | b" would come up?