Comment by thaumasiotes | Hacker News Reader

Comment by thaumasiotes | Hacker News Reader

Parent Full thread

Here's the proof I learned:

1. Assume there is no prime number larger than p_n.

2. Compute the product of all the prime numbers less than or equal to p_n, plus one. Call this number c.

3. By construction, no prime number less than or equal to p_n divides c.

4. But all integers greater than one have one or more prime factors. (This is not proven.)

5. Therefore, since c has no prime factors less than or equal to p_n, it must have one which is not less than or equal to p_n, or in other words c must have a prime factor greater than p_n, which contradicts step (1).

Viewing https://en.wikipedia.org/wiki/Euclid%27s_theorem, I see that Euclid's original proof doesn't involve using all the primes within a certain range ("your collection so far need not contain all primes so far"), so what you've said here does apply to it. However, I also read:

> Euclid is often erroneously reported to have proved this result by contradiction, beginning with the assumption that the set initially considered contains all prime numbers, or that it contains precisely the n smallest primes, rather than any arbitrary finite set of primes.

So I don't feel too bad about referring to the proof I gave above as "the famous proof". I didn't call it "the proof that appears in Euclid's Elements".

Since this result is by contradiction, there are several different points where you could choose to observe the contradiction. But you can certainly do it before you actually produce a new prime.

In step 1 you haven't assumed that you know all the primes up to p_n, and then in step 2, you assume that you do have them. If you don't make step 1 more precise, saying that you know all the primes up to p_n, then when you multiply them all together and add 1, step 3 fails.

The point is that the proof is fairly robust, and yet stating it all completely correctly is actually quite hard. Here is a more correct version:

We know there are at least some primes. For example, 3 is prime. Take any non-empty finite collection of primes. Multiply them all together, and add 1. The result may not be prime, but it is expressible as the product of primes, and hence there is at least one prime that divides it. That prime cannot be one of the primes in our finite collection, and hence any finite collection of primes does not contain them all.

The classic counter-examples used when there are proof with holes are these:

Consider the set of primes { 3, 5 }. Multiply them together and add 1, and all the primes that divide the result are less than the primes you have.

Starting with 2 and then repeatedly getting a new prime by multipying and adding 1 we get 3, then 7, then 43, but 2.3.7.43+1 = 13.139.

Finally, taking known successive primes we get "failure" at: 2.3.5.7.11.13+1 = 59.509

And as an addendum, I've heard this before, but a few days ago Carl Pomerance told me of a joke he heard from Henrik Lenstra. Here's a proof that there are infinitely many composites:

4 is composite, 6 is composite. Suppose by way of contradiction that the set of all composites is finite. Multiply them all together and don't add 1! That's a new composite, hence contradiction. QED.

> In step 1 you haven't assumed that you know all the primes up to p_n, and then in step 2, you assume that you do have them. If you don't make step 1 more precise, saying that you know all the primes up to p_n, then when you multiply them all together and add 1, step 3 fails.

Why? We know that the largest prime is p_n, and the numbers from 1 to p_n are finite. Each of them might or might not be prime. It's perfectly legitimate to say "multiply together all the primes between 1 and p_n" without knowing which numbers in particular those happen to be. Since I don't know which numbers I multiplied together, I won't know the numeric value of the number produced in step 3, but I certainly do know that by construction, it is not divisible by any prime <= p_n. (Technically, I know this conditional on the lemma "all prime numbers are greater than one.)

The proof I've given doesn't deal with arbitrary sets of primes at all. There is no point in the proof at which you could multiply 3 and 5 and then add one to produce 16. If 5 is the largest prime, the number (implicitly) computed in step 3 is 2⋅3⋅5 + 1 = 31. Iterating from 2 (but why?), you'd compute 3, then 7, then 211, and then something large. And 2⋅3⋅5⋅7⋅11⋅13 + 1 = 30031 = 59⋅509 isn't a counterexample to the proof I've given, because the conclusion is explicitly "the number constructed must have a prime factor greater than p_n", and p_n in this example is 13. 59 and 509 are both greater than 13.

Where does my proof fail? How is yours more correct? You still seem to think that I'm misstating the proof found in the Elements. You can prove things more than one way.

I really don't have time for a complete point-by-point here, I really don't. The proof as you've stated it here is really, really close to being complete and correct. Mostly the problems are where you haven't said something that is, in fact, true, reasonable, and easy to add. The point being that you haven't actually said it.

Step 1 is the specific example. You say:

    1. Assume there is no prime number larger than p_n.

But you haven't said that p_1 through p_n are all the primes up to and including p_n. A set that satisfies your step 1 is the set { 7 }. I can read your step 1 and say: OK, I'll assume that { 7 } is the set of all primes.

Then you say:

    2. Compute the product of all the prime
       numbers less than or equal to p_n,
       plus one. Call this number c.

The natural reading of this is to think you're saying that p_1, p_2, p_3, ..., p_n are the primes up to p_n. If not, why have you called it p_n and not simply called it P. Doing so makes it clear that in step 2 you are taking all the primes up to some limit, rather than taking all the primes in a collection of size n, with p_n the maximum element.

This is exacerbated by the fact that the usual proof does start with a specific collection, which is at odds with what you seem to be saying.

You say:

    > Since I don't know which numbers
    > I multiplied together, I won't
    > know the numeric value of the
    > number produced in step 3, but
    > I certainly do know that by
    > construction, it is not divisible
    > by any prime <= p_n.

Yes, but only if you use this unexpected interpretation that p_n is simply a limit, and not the largest/last element of an arbitrary set of primes.

So the proof you've given is not exactly the usual proof, it's subtly different. The notation you use brings to mind the usual proof, and creates a confusion about what you're actually saying. The objective of the proof I gave is to avoid those potential mis-interpretations.

Does that make it clear? Perhaps it's important to add that I'm not saying your proof is actually wrong, I'm just saying that if an undergrad produced it I'd be asking for clarification on a few points to see if they really understood it, or if they'd just memorised it and perhaps missed a point, or muddled two formulations.

It is a common simplification of Euclid's proof to convert it to a proof by contradiction. In fact, I believe I was taught this version of the proof in an early undergraduate math class. This version is not constructive, actually the first example of the wikipedia article on constructive proofs points this out:

Euclid's proof is constructive. But a common way of simplifying Euclid's proof postulates that, contrary to the assertion in the theorem, there are only a finite number of them, in which case there is a largest one, denoted n. Then consider the number n! + 1 (1 + the product of the first n numbers). Either this number is prime, or all of its prime factors are greater than n. Without establishing a specific prime number, this proves that one exists that is greater than n, contrary to the original postulate.

Reply on news.ycombinator.com