Hacker News Reader

Comment by buzzdenver | Hacker News Reader

Engineer's honest question to a mathematician: is this proof more simple than the one the multiplies all the supposedly finite primes and shows that their product plus or minus one is not divisible by any of those primes, ergo there are always more primes ?

View on HN

People tend to think of the proof you are thinking of as easier because they are more familiar with it. There are some subtle things that the proof you mentioned glosses over. Namely, if p|A and p|B then p|(A-B). Now this is not a deep concept but it is something which people who are not accustomed to thinking of proofs tend to gloss over. Namely, they will see the part that if P = p1 p2 p3...pn + 1 and p|P then p|1 and not think that this does itself require justification.

Personally, I really like the proof using sines. I won't claim it is easier or simpler but it is very nice. I've never thought to prove the infinitude of primes this way and it uses facts from trigonometry. I will now incorporate this into my trig classes.

I think it is quite straightforward and easy for one to understand. Students in trigonometry and calculus generally do not have experience in proving statements about arithmetic. Here is an excellent way to show a connection between concepts that seemingly have nothing to do with each other. It is this that mathematicians really like.

> Namely, they will see the part that if P = p1 p2 p3...pn + 1 and p|P then p|1 and not think that this does itself require justification.

While your point that every step of a proof requires justification is a good one, this is really, really easy to verify. That doesn't excuse one from actually giving that justification, in the course of a formal proof; but there's at least as much implicit knowledge bound up in the linked proof. (For example, one needs the existence of sine, its 2π-periodicity, the fact that it is positive from 0 to π/2 ….)

Yes, definitely there is more information implicitly wrapped into the sine proof. That's why it's not simpler. However, it is not a worse proof either. It's just a different one that is clever and can help to reinforce concepts from trigonometry.

There's not much trigonometry in this proof, just the fact that sine has period 2pi is zero at pi. Any function that has these two properties could directly replace sine in this proof.

And actually any periodic function that is zero somewhere could be used in a tiny bit modified version of this proof.

That is true but in Trigonometry Sine the function one studies and so using this result in a trigonometry course is nice.

> And actually any periodic function that is zero somewhere could be used in a tiny bit modified version of this proof.

I think that, for the modification to be tiny, you need something like: there is an interval on which the function is positive, and on the boundary of which it vanishes. (Some sign condition is necessary; taking the constant function at 0 doesn't work! Of course, this particular condition is automatically satisfied for any continuous, periodic function that vanishes somewhere, but is not identically 0.)

As others have said, the proof relies on some trig facts (Though maybe you can replace `sin` with any zero-crossing periodic function). But it's worse than that.

The only proof I can see for the second equality there depends on showing the numerator is composite. And that in turn depends on something very like the argument you mention.

So unless there is a much simpler proof of that equality, the proof is only a "one liner" because it leaves Euclid's argument as an exercise to the reader.

I see that proof, due to Euclid, as simpler because it doesn't require any facts about trigonometric functions.

It might be harder to write out in mathematical notation in one line, but maybe I should try (using set-builder notation or something).

We know it can be written out as a haiku: https://xkcd.com/622/!

While that's very clever, it doesn't accurately present Euclid's argument because the haiku is

  Top prime's divisors'
  product (plus one)'s factors are...?
  Q.E.D., bitches!

This doesn't include Euclid's argument about multiplying all of the primes, mistakenly referring instead to "top prime's divisors".

The "top prime's divisors' product" would be equal to the top prime itself, so Randall's haiku asks "if there is a largest prime p, what are the divisors of (p+1)?" which doesn't create any contradiction (it could simply be divisible by various smaller primes!).

Maybe we should amend it to

  Take factorial
  of top prime, then add one: what
  are the divisors?

It's not the factorial either, that would include composites in the product too.

Euclid didn't use the factorial in his original proof, but it still produces a logically correct argument and it has fewer syllables. Metri causa. :-)

Using the factorial is better, I think, even if ahistorical; it avoids the slight unpleasantness of having to show that every non-unit integer is divisible by a prime.

But then you can't exclaim Q.E.D., bitches! and it would be a terrible cartoon. :)

It's restored in a version further down in the thread.

Couldn't you just change "divisors' product" to "factorial's"? I guess that it does some violence to the metre.

You could work with it and get the original last line back:

  Factorial of
  top prime, plus one: factor that!
  Q.E.D., bitches!

Depending on how much you're willing to assume and what exactly counts as "one line," it could be as simple as:

> One plus the product of all primes is itself prime, and larger than all primes.

This omits a bunch of stuff, but it seems like less than the linked paper.

> One plus the product of all primes is itself prime

One plus the product of the first N primes is not necessarily prime. Consider 2 * 3 * 5 * 7 * 11 * 13 + 1 = 30031 = 59 * 509

How about: one plus the product of a list of primes has a prime factor not in the list.

Yup, that works!

I like that version better anyway. Thanks for helping me improve it!

Yes! Because primes are infinite! The statement assumes limited primes. And, because it falsifies, it proves primes must be unlimited. I find this argument based on prime factors much simpler.

I would have been fine with "would have to be prime"; I like the edit Mike suggested even better.

I'm not a mathematician but I'd say no since trig functions inherently require a lot more math to formulate, whereas Euclid's proof follows from much simpler facts.

This proof is nearly equivalent to that proof, but uses the sine function to generate a contradiction. The crucial step involves the fact that:

1 + 2 * product(p', p')

must be divisible by some prime number, where

product(p', p')

is the product of all primes you were talking about.

Reply on news.ycombinator.com