Euclid’s proof that there are infinitely many primes

Paul Erdős had this notion that God kept a book of the best proofs. Erdős called God’s book simply “the book.” Springer recently published Proofs from THE BOOK, a collection of elegant proofs that the authors suppose might be in God’s book.

For many mathematicians, the first proof that comes to mind as a candidate for a proof in the book is Euclid’s proof that there are infinitely many primes. The proof is so short and simple that it can almost be written within the 140-character limit of Twitter. I give the proof in my AlgebraFact Twitter account as follows.

There are infinitely many primes. Proof: If not, multiply all primes together and add 1. Now you’ve got a new prime.

Several people pointed out that I was a little too terse. If N is the supposed product of all primes + 1, N itself doesn’t have to be a new prime. It could be that N has a factor that is a new prime. The smallest prime factor of N must be a prime not on the list. Either way “you’ve got a new prime,” but the proof above leaves out some important details.

Here’s an example. Suppose we believed the only primes were 2, 3, 5, 7, 11, and 13. Let N = 2*3*5*7*11*13 + 1 = 30031. Now N cannot be divisible by 2, 3, 5, 7, 11, or 13 because there is a remainder of 1 when dividing N by any of these numbers. Maybe N is a new prime, or maybe N is composite but N has a prime factor not on our list. The latter turns out to be the case: 30031 = 59*509.

If you can find a better summary of Euclid’s proof in 140 characters or less, please leave it in the comments. Please include the character count with your proposal.

Related posts:

12 thoughts on “Euclid’s proof that there are infinitely many primes

  1. Suppose the set of primes P is finite. Multiply them all and add one. The result has prime factors but they can’t be in P. So P is infinite.
    (140)

    Will – you mean product, not sum?

  2. One plus the product of any finite set of primes is not divisible by any of those primes. Add its (new) prime factor(s) to the set. Repeat.
    (139 chars)

    No prime factor of one plus the product of any finite set of primes is in that set. Thus a finite set of primes can be extended indefinitely
    (140 chars)

    These constructive proofs are actually closer to Euclid’s original proof than is the modern reductio ad absurdum form of the proof. See Euclid’s Proof of the Infinitude of Primes (c. 300 BC) and OEIS:id:A000945.

  3. The smallest prime factor of N must be a prime not on the list.

    Actually all prime factors of N must be prime(s) not on the list.

    Your version of the statement is still true, of course, in the sense that “all squares have three sides” is also true.

  4. Let P=largest prime. Then N=P!+1 not divisible by P or any smaller prime, so a larger prime than P must exist!

    110 chars

    This was my first attempt at a #tweetproof, last December.

  5. I think you’re original proof is fine, if you change the last part from “Now you’ve got a new prime” to “This number is neither composite nor prime, -><-."

  6. Let me try again (130 characters). It still leaves a bit to the imagination…

    Is there a fixed number of primes? No. If you multiply them all and add 1, dividing it by any prime leaves 1, so it’s prime, too.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>