I had a fight with Euclid on the nature of the primes.
It got a little heated – you know how the tension climbs.
It started out most civil, with a honeyed cup of tea;
we traded tales of scholars, like Descartes and Ptolemy.
But as the tea began to cool, our chatter did as well.
We’d had our fill of gossip. We sat silent for a spell.
That’s when Euclid turned to me, and said, “Hear this, my friend:
did you know the primes go on forever, with no end?”
I took a napkin to my face,
to wipe the tea and shock.
At length I said, “The primes don’t end?
My friend, that’s crazy talk.”
In general, the integers have factors we can find.
Take 12. That’s 4 times 3.
Or 54. That’s 6 times 9.
But certain numbers can’t be broken down in any way.
Take 17. It has no factors.
So it’s “prime,” we say.
At first, the primes are plentiful.
There’s 2, 3, 5, and 7.
There’s 31 and 43.
There’s 19 and 11.
But as our sights climb higher, the primes start thinning out.
Long gaps pass without one – throwing Euclid’s claim in doubt.
So when he held his ground and said, “It’s true. The primes don’t end.”
I laughed and told him, “Euclid, boy, you’ve gone around the bend!”
Then Euclid mused, “Suppose you’re right.
Suppose they hit a max.
In that case, there’s a largest prime.
Do you accept these facts?”
I nodded my acknowledgment, and felt a speck of pride
that Euclid, proud and lauded Greek, had come to see my side.
“This largest prime must have a name,”
he pressed. “Let’s call it p.
The biggest prime of all the primes,”
he said. “Do you agree?”
Once again I nodded, with a smile on my face,
for I was putting Euclid, mighty Euclid, in his place.
“Now, let’s gather all the primes,
from 2 on up to p,
and multiply them all together,”
Euclid said to me.
“Fine,” I said, a note of worry ringing in my thoughts.
What was Euclid plotting? Had he given up or not?
“Multiply out all those primes,” he said,
“and when you’re done,
take that final product,
and simply add on 1.”
My confidence was fading. I was swiftly feeling dumber.
I could not see the reason Euclid conjured up that number.
“Let’s call this number q,” he said,
“this newly minted figure.
And notice that, compared with p,
our q is much, much bigger.”
I could not disagree with this. His argument rang true.
After all, we’d multiplied by p to get to q.
“Since q is larger than the largest prime,”
old Euclid said,
“our q cannot be prime itself.
It factors out instead.”
I felt a trap was being sprung, but I could not resist.
A prime that’s larger than our p could simply not exist.
“Now, q has factors,” Euclid said.
“What can those factors be?
We can’t divide our q by 2.
We can’t divide by 3.
We can’t divide by 5 or 7.
Can’t divide by p.
We can’t divide by any prime,” he said,
“Do you agree?”
I saw his logic, blinding now. It scorched me like the sun.
Divide our q by any prime; you’ll get remainder 1.
That means it has no factors.
That means it must be prime.
But already, we’ve said it’s not.
And if that’s true, then I’m…
“You’re wrong!” he cried. “You see the flaw?”
I felt like such a dunce.
“You say q’s prime,
then say it’s not.
It can’t be both at once!
“So take your claim that ‘primes must end,’
and stick it on a shelf.
I’ve shown you now. That stance is flawed.
It contradicts itself!
“That only leaves one option.
And now, you see the light.
The primes must never, ever end.”
I sighed. The man was right.
We poured another cup of tea,
and smoothed our ruffled shirts.
I said, “Your argument hit hard,
and I confess, it hurts.
I thought you had conceded,
but the whole charade was fake.
You only took my side
so you could show me my mistake.”
Euclid sipped his teacup with a twinkle in his eye.
“The proof by contradiction,” he agreed, “is rather sly.
You stand upon the sidelines.
Your opponent takes the field.
You let him play against himself,
until his flaw’s revealed.”
“The truth wins out then, I suppose.” I glumly drained my cup.
“The truth will win out even when it seems it’s given up.”
“So it is,” said Euclid, “and so may it always be.”
And then he kindly offered up another cup of tea.
Loved this 🙂
How can we claim that P is prime if we don’t know where it stops?
Good question. Basically, it’s like pointing to the sky and saying, “One of those stars must be the farthest away. Sure, we don’t know which one it is. But whichever one it is, let’s call it ‘Star P.'”
Similarly, we’re saying, “Suppose that, somewhere out there, the primes end. If they do, there must be a biggest prime. We don’t know where it is, or exactly how big, but we know it’s out there somewhere. So we can give it a name – and that name is ‘p’.”
But he didn’t just pick a prime. He got P by adding primes. That’s kind of a big difference, right?
Not a math major, here, just having a bit of a problem with his argument. It seems to force an acceptance of impossibilities to work. Trying to figure it out what I’m missing. 🙂
Well, text explanations of math are always tricky, but I’ll give it another shot:
He’s not adding primes. (In fact – could you point me to the line that gave you that impression? I could try to make a clarifying edit.) Basically, he’s saying that we know some primes: 2, 3, 5, 7, 11, 13…. and so on.
Now, the question is: How long is that list? Does it go on forever, with bigger and bigger primes (Euclid’s view)? Or does it eventually hit some end, some largest prime, after which there are no more (my incorrect view, which Euclid disproves)?
And so what Euclid says is, “Suppose you’re right. Suppose the primes DO end. Well, in that case, let’s call the largest prime P.”
(You’re right, though, that there is an “acceptance of the impossible” here. Euclid temporarily accepts a false idea, so that he can show me WHY it must be false.)
Oops, sorry about that, he multiplied them not added (my memory is just as bad as my math), “”“Now, let’s gather all the primes,
from 2 on up to p,
and multiply them all together,””
Multiply, add, doesn’t matter.
It’s just his argument that fails not the overall concept. There is no need to argue once the concept of infinity is established. Silly, silly Euclid. 🙂
Right – although I wouldn’t say that his argument fails. This is exactly how it succeeds!
He pretends to let me win (“Suppose you’re right” he says), then shows how such a view would lead to chaos and contradiction. Once he’s established that my view is impossible, we know that his view must be the right one.
So it’s not Euclid who’s being silly. It’s me. (Or the poem version of me, anyway.) Euclid only PRETENDS to agree with me to reveal my silliness.
Well, my word, who doesn’t get infinity? haha
I note echoes of “Casey At The Bat”. Beyond the meter and rhyme scheme, your couplet “Once again I nodded, with a smile on my face, / for I was putting Euclid, mighty Euclid, in his place” echoes Thayer’s “There was ease in Casey’s manner as he stepped into his place / There was pride in Casey’s bearing and a smile lit Casey’s face”. We also find “Casey, mighty Casey” elsewhere in the original poem.
Nice catch! I love Casey at the Bat. A few years ago I was working on committing it to memory… might take the challenge back up.
Beautiful.
Thanks!
This is one of the greatest things you have ever written! I love it! You need to make it into a children’s book and sell it. I am completely serious.
Thanks! One day, perhaps… when the children of the world are clamoring for some insight about the distribution of the primes.
I have two girls (at least, others not quite old enough, yet) who would *devour* this proof, especially in this poetic/conversational format. I agree w/tbf!
I concur! I bet you could make some kind of digital comic book pretty easily (Adobe Spark apps or something?) with the content already here. It would be more enjoyable to share with my kids that way than just scanning down the usual blog post format. I would absolutely buy this as a picture book, and at least one of my kids would enjoy it.
Have you seriously considered this suggestion? Please do! 🙂
Amazing! That is one of the best explanations I’ve seen of Euclid’s proof together with an engaging story, in couplets AND bad, but hilarious drawings. Bravo!
“bad, but hilarious” – awesome! I’ll take it!
Nice job setting Euclid’s reductio ad absurdium to verse! Loved it!
Thanks for reading!
Brilliantly written! Thoroughly enjoyed the journey…
Thanks!
Reblogged this on ParParAway and commented:
And math is more fun this way! 🙂 Brilliant piece!
Thanks!
Reblogged this on Math Education Concepts.
Maybe I’m not understanding, I tested the first 10 primes and only the first 5 worked out?
Prime Prime Product +1
2 3 prime
3 7 prime
5 31 prime
7 211 prime
11 2311 prime
13 30031 not prime divides by 59
17 510511 not prime divides by 19
19 9699691 not prime divides by 347
23 223092871 not prime divides by 317
29 6469693231 not prime divides by 331
That’s an interesting pattern, although it’s a little different than the number q that we’re considering, which is defined like this:
q = (2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * … * p) + 1.
q is just one number, formed by multiplying ALL the primes together (not just a pair of primes), and then adding 1.
(Of course, “multiplying all the primes together” isn’t actually possible, because there are infinite primes. In fact, that’s what we’re proving. But in order to prove it, we temporarily pretend that there are only finitely many primes.)
thanks for responding, but I’m just not getting the circular logic. when you say “multiplying ALL the primes”, you are saying we temporarily pretend this is a finite number, but when I test that with a finite list of primes, the proof is false?
when it says”Divide our q by any prime; you’ll get remainder 1.
That means it has no factors.
That means it must be prime.”
I agree that it is true you can’t get a factor of a prime, but that doesn’t prove there isn’t a non-prime factor. That was what I set out to test with my multiplying out the primes.
Hopefully G.G.’s reply is helpful – I think that’s a good explanation. There’s one more point I should elaborate on, because I didn’t do a good job of explaining it in the original poem:
“I agree that it is true you can’t get a factor of a prime, but that doesn’t prove there isn’t a non-prime factor”
Actually, if a number has no prime factors, then it must have no factors at all.
Imagine that a number N has a non-prime factor (like 14). Well, that factor has factors of its own (in this case, 2 and 7). So our original number N isn’t just divisible by the non-prime factor; it’s also divisible by the factors OF that factor.
In other words: Saying “a number has factors” is the same, essentially, as saying “a number has prime factors.”
You’re right that 30031 is divisible by 59.
We’re temporarily assuming that the largest prime is 13. Remember, we’ve temporarily defined all primes in the universe as {2, 3, 5, 7, 11, 13} and no more.
That means we’re temporarily assuming that 59 is composite! And composites *by definition* can be factored into primes. Every composite can be broken down into primes. So, if 59 is composite, then it can be factored into some combination of {2, 3, 5, 7, 11, 13}. By definition. We both know 59 can’t be factored like that, but that’s not the contradiction we’re interested in right now.
So 30031 should be divisible by either 2, 3, 5, 7, 11, or 13. Which, obviously, it isn’t — and that’s the real Contradiction.
The version of this proof that I’ve heard is not the contradiction about whether p is really prime or not, but the contradiction about whether p is really largest or not. This way, Dan’s observation is really helpful. If you multiply all the primes 1 through p and add 1, you get a number q that’s definitely bigger than p and not divisible by any number less than or equal to p (try it with Dan’s numbers — 30031 is not prime, but it’s not divisible by 2, 3, 5, 7, 11, or 13 either). Either q is prime, in which case p is NOT the largest prime, or q is composite, in which case it has at least two prime factors… BOTH of which must be greater than p. So there can’t exist any such largest prime.
(I know it’s been a few years, but…)
Technically, the poem does not accurately present Euclid’s proof. A better modern version of the actual proof is:
Let us assume that the set of primes is finite. Then P exists as a finite set of all primes. Let q be the product of all elements of P, plus 1. q has no factors in P, so either q is a prime, or it has prime factors not in P. This means that there is at least one prime number not in P.
Euclid’s original proof:
Let A, B, and C be prime numbers. Let DE be a segment that is A * B * C long, and let EF be one unit long. Let G be a prime number which divides DF. If it is A, B, or C, it also divides DE. If it divides DE, it also divides EF, but nothing greater than 1 divides 1. So G is not A, B, or C, and therefore there exists a prime number other than A, B, and C. We can generalize to any finite set of primes.
One can get rid of the reductio step entirely. Consider any finite set of primes; take the product of its members; add one; the result can be prime-factorised and its prime factors aren’t in the set you started with, so there are primes not in your finite set. Therefore, no finite set of primes is exhaustive. Therefore the set of primes is not finite.
Here’s an idea – build a set of primes by iterating this procedure:
product({}) +1 = 2 is a prime not in {}
product({2}) +1 = 3 is a prime not in {2}
product({2, 3}) +1 = 7 is a prime not in {2, 3}
product({2, 3, 7}) +1 = 43
product({2, 3, 7, 43}) +1 = 1807 = 13 * 139
product({2, 3, 7, 13, 43, 139}) +1 = 3263443
product({2, 3, 7, 13, 43, 139, 3263443}) +1 = 10650056950807 = product({1033, 31051, 547, 607})
product({2, 3, 7, 13, 43, 139, 547, 607, 1033, 31051, 3263443}) +1 = 113423713055421844361000443 = product({29881, 67003, 9119521, 6212157481})
(No, I didn’t work that out in my head; python helped me – and got rather slow on the last one (my code to search for primes and factorise numbers is a bit clunky, TBH), so I stopped there. Here:
https://github.com/ediosyncratic/study.py/blob/master/maths/primes.py is the module whose factorise() I used. My attempt to replace it with something better foundered on a bad case of the second-system effect.)
Notice that some back-filling happens; prime factors of the product+1 may be less than some of the primes we multiplied together.
Open question: will this set of primes, eventually, fill in all the gaps ?
Guess: no. Hence secondary question: is there a way to determine whether a given prime is in the limiting union from this sequence, without having to iterate this sequence infinitely many times ?
(If anyone is wondering why product({}) = 1, notice that the product of a union of disjoint sets of numbers is the product of the united sets’ respective products; which requires that, if {} is to have a product, it must be 1. Likewise, sum({}) = 0.)
This is a great math poem! Good job to the author. Bonus points for the “are eu clidding me” caption!
Thanks! I was happy with that one. (Disappointed to find Ian Stewart already used “Game, Set, Math” as a book title.)
This is a brilliant way of explaining the proof of infinite primes with a poem. Love it! 🙂
Thanks for reading!
“q” is not necessarily prime. There could be a prime larger than “p” that is a factor of “q”. For instance, (2 x 3 x 5 x 7 x 11 x 13) + 1 = 30031. 30031 = 59 x 509, so it’s not prime. However, even if “q” isn’t prime, it still proves that there is a prime factor of “q” larger than “p”, which still proves that the number of primes is infinite.
Ahh ha! I finally get it, 59 > 13. My fluorescent light turned on! Thank you.
Yeah – that explanation is more faithful to Euclid’s proof (which simply said, “Take any finite list of primes,” and showed that there must exist at least one prime not on the list).
And I’m glad it clicked, Dan!
Slick Boston tee. Where’d you get it?
Fictional, alas, although I’ve got some Bruins gear and an old Vinatieri jersey.
This is the standard misrepresentation of Euclid’s method of proving the infinitude of primes. Euclid’s actual proof was not by contradiction; it was simpler. See my joint paper with Catherine Woodgold in the autumn 2009 issue of the Mathematical Intelligencer, where we refute this erroneous account of history. Here’s Euclid’s actual proof: Suppose you have any finite set of primes (don’t assume they are all the primes that exist). Multiply the and add 1. The resulting number must be divisible by some prime. Then prove (and _this_ part, at least, was by contradiction) that that prime cannot have been among those in the set you started with. Thus every finite set of primes can be extended to a larger finite set of primes.
Right. I’ve seen that last step of Euclid’s original argument presented more as casework: Either your product-plus-one is prime, or, if not, then the prime that divides it must be missing from your list.
When it comes to elegant math, I suppose I slightly prefer Euclid’s original version. But when it comes to teaching proof by contradiction to students, I strongly prefer the standard “misinterpretation” (which is, of course, still a valid proof – just a modified one). It’s easier to learn the technique when the proof-by-contradiction structure encompasses the whole argument, not just a piece of it.
The verse is wonderfully done. But such a shame that it perpetuates a false version of history. There is a controversy over proof by contradiction, with intuitionists and constructivists restricting its use to decidable propositions. Euclid gave a simple algorithm. Input: any finite set of primes. Output: a prime not in that set. This gives a nice algorithmic definition of infinity: to prove a set S is INFINITE, provide an algorithm that, given a finite subset of S, outputs an element p not in that set. The verse hides the algorithmic nature of the concept of infinity. The 2009 paper of Hardy & Woodgold documents the shocking extent to which the algorithmic nature of infinity has been obscured by the compulsion to wrap Euclid’s algorithm in an irrelevant proof by contradiction. But I would disagree slightly with Michael Hardy’s assertion that the proof that p is not in S is by contradiction. You don’t need to assume that p is in S and then derive a contradiction. You simply show that for each q in S, p is different from q.
Well, among ‘falsehoods’ I’m perpetuating here, I’d rank Euclid’s speaking English and talking to a guy in a Red Sox shirt as more dire than my restructuring of his proof to make it more accessible to the casual reader.
I’ll check on the Hardy & Woodgold paper; sounds like a fun read (and certainly a rigorous notion of ‘infinity’ in its various contexts is one of the hardest things to acquire as a student). Thanks for the tip.
Enjoying the paper (or the two pages that aren’t paywalled, in any case), though it acknowledges that the lemma in Euclid’s original proof also works by contradiction.
Their complaints about the proof seem to be less historical than pedagogical, for what it’s worth. I do think they provide some nice warnings about possible student misconceptions.
Just discovered this, loved it, thanks a lot! I especially like the little philosophic epilogue.
Thanks for reading!
“The first time you share tea with a Balti, you are a stranger. The second time you take tea, you are an honored guest. The third time you share a cup of tea, you become family…”
Read this in At Right Angles magazine(Nov 2013 issue). Loved it!
Sheer genius Mr. Orlin. I love all of the content you have on your corner of the Internet. It is some really high quality stuff! I’ve seen your stuff come up on other websites too. I especially liked the “Math experts split the cheque” post. I hope you keep this blog going. I have read every post, there aren’t enough!
nice post….i loved the explanation…
It was aight.
Good info. Lucky me I recently found your blog by chance (stumbleupon).
I have book marked it for later!
I love what you guys are usually up too. This sort of clever work
and coverage! Keep up the amazing works guys I’ve you guys
to our blogroll.
I’m missing something. Why can’t q be an even number?
Hi Malcom,
For q to be even either there must be a way to (a) multiply two odd numbers to create an even product, or to (b) multiply an odd number by two and still obtain an odd product or (c) add one to an even number to get an even sum.
Friendship leads to tea, apparently
Really nicely illustrated the concept of prime with awesome poetry
Whoa, I understand Q can’t be a multiple of any of the primes but why can’t it just be a multiple of some other number like 4 or 6? I think I’m missing something here…
But I love this poem so much nevertheless man!
Dear Ben,
Greetings. I had written to you many months back (years?) requesting permission to reproduce in my magazine At Right Angles a piece of yours – A Fight With Euclid (such a lovely little piece!).
Subsequently we had indeed published the piece.
We would like now to make use of some of the beautiful and appealing stick figures which you so often have in your posts. May I request your permission to do so? I do not have a precise list of which figures we would like to use; but of course, we will give full attribution to your blog on all the pages where the figures are used.
I have an additional request for you, for consideration a little later in the year or early next year. I will write to you about this after hearing from you.
Many thanks,
Shailesh
Love it!
I would like to criticize that q is not proven to be prime. Rather instead, it is either a prime, or a composite number comprised of prime numbers not on the list.
But that’s the beauty of the argument.
The initial assumption is that there is a finite number of primes and therefore a largest prime. q is all of primes multiplied together plus 1. The list of primes given (from smallest to largest) is the *entire* list of all of the primes there are. This leads us to a contradiction because we made a new prime that isn’t in the list–we know it isn’t in the list because it’s bigger. So, whether you frame the contradiction as “Aha! We found a prime that wasn’t on our list of all of the primes!” or “Aha! We found prime bigger than the biggest prime!”, the contradiction stands.
Haha that was amazing!
I really liked the drawings!
Note to all: This is actually wrong as explained here: https://math.meta.stackexchange.com/questions/16518/how-do-you-know-that-their-answers-are-correct/16528#16528
You can see for yourself
2x3x5x7x11x13+1=59×509
Yes, counterexamples like this are quite compatible with the proof in the poem – in fact, the point of the poem is to show that such counterexamples *must* exist!