Hacker News Reader

Comment by ivegotnoaccount | Hacker News Reader

The issue is that it is not divisible by any other prime *from the list*. The two cases (prime or composite) must be handled separately since they do not use the same logic to infer there is one more prime.

For instance, 2 * 3 * 5 * 7 * 11 * 13 + 1 = 30031 = 59 * 509.

View on HN

You don't need two separate cases.

Assume p1, ..., pn is a finite list of primes. The sum p1+...+pn+1 is divisible by a prime, because every natural number> 1 is. However, it's not divisible by p1,...,pn, hence there must be an additional prime not in the list.

(I think you're right though that GP's "contradiction" doesn't work)

too late to edit: p1 * ... * pn+1, of course. not plus.

Oh, you're right.

Never thought of using "by definition, all numbers can be divided by a prime" tu merge the two cases. It's not that shorter, but is IMHO quite elegant, I'll remember it. Thanks for correcting me.

Well, it's not by definition, but "every number is divisible by a prime" is fairly obvious (just keep dividing until you reach a prime) and can technically be proven by using (strong) induction.

But to get the contradiction, you assume a finite number of primes. As each of them does not divide the new one, the new one is not divisible by a prime. It seems like your method is some kind of induction? Which probably gets a little closer to the "reason" for it, but isn't the standard proof I've seen.

These are really just logically equivalent ways of getting at the same result. You can either prove the statement "for every finite list of primes, there exists a prime not in this list" directly from the axioms of arithmetic, or you can add its negation "there are finitely many primes" as an assumption, derive a contradiction, and therefore conclude the negation of that new assumption. Nothing substantially changes about the proof either way.

I mean, yeah? It's still true you don't need to prove the composite case separately if you structure it a little different. Plus the original comment was clearly angling for the contradiction, so pivoting without warning to induction is just misleading

There is no induction involved (I mean, yes, for some of the lemmas about divisibility, probably you'll need induction, but not for the main proof).

Oh I see! I was talking about bootstrapping from "there's always another prime" to "there's a countably infinite number of primes", but you can just piggyback off the naturals.

Well, I suppose it matters which definition of "infinity" you want to use. The modern definition of an infinite set is that it's a set for which there exists an injection into the natural numbers. But that definition brings you into the territory of set theory, which seems unnecessarily complex when you're just trying to prove something about arithmetic.

Euclid's original proof of the theorem is of the form "for any list of primes, I can find an additional prime" [0], and for good reason: in Ancient Greece, thinking of infinity, or infinite sets, as a concrete object that you could manipulate would have seemed weird.

But the proof variant where you produce a contradiction doesn't really get into the set-theoretic details either. All it does is say: "Assume there is a finite list of all primes. Derive a contradiction. Therefore there is no such list." That's pretty much equivalent to the direct proof, it's just using different logical inference rules.

[0]: http://aleph0.clarku.edu/~djoyce/java/elements/bookIX/propIX...

Reply on news.ycombinator.com