A Fight with Euclid

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.

About these ads

52 thoughts on “A Fight with Euclid

    • 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.)

  1. 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.

  2. Pingback: Math That Is Fun: Infinite Primes | Let's Play Math!

  3. 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.

      • 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!

  4. 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!

  5. 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.

  6. “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.

    • 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!

  7. 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.

  8. Pingback: A Fight with Euclid | Stem4kids.info

  9. “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…”

  10. Pingback: Fun Recreational Math Games | Drawalot.com

  11. 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!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s