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:
In praise of tedious proofs
Proofs of false statements
{ 1 trackback }
{ 8 comments… read them below or add one }
Will Fitzgerald 02.13.10 at 09:51
Say P (all primes>1) is finite. Let s=sum of P+1; s is not in P, so s has a factor t in P, falsely implying t divides 1. So, P is infinite.
(characters: 140)
Alan Stokes 02.13.10 at 12:10
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?
Nick 02.13.10 at 16:30
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.
Will Fitzgerald 02.13.10 at 19:18
Grr, of course I meant product. (But of course it puts it up over 140 characters!)
David R. MacIver 02.14.10 at 07:34
Let p be the largest prime. p! + 1 is not divisible by any primes. Oops.
(73 characters)
Nemo 02.14.10 at 10:08
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.
Also Nick 02.14.10 at 11:36
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.
Benvitale 09.15.10 at 14:30
And there’s Kummer’s counter example and others … http://www.gbbservices.com/math/primes.html