This really belongs on the lamented Fiat Lux's "e to the pi to the i" board, but since that's no longer with us, I'll use it to check whether we still have any readers here.
Not long ago I was in Rhode Island visiting my brother and his family. Somehow the question of whether the number of primes is infinite came up in casual conversation. My sister-in-law was of the opinion that there likely is only a finite number of primes. My brother and I, both being somewhat math nerds, knew that that was contrary to fact.
"Ah-ha, but can you prove it?" Ku asked, a little smugly, knowing our best mathing years were well behind us.
It turns out I was able to recall/reconstruct the quite elementary proof in my head, right there in the kitchen. Anybody care to take a crack at it?
A couple hints:
Assume the contrary and demonstrate a contradiction.
The first step is to construct an integer with certain useful properties.
Subscribe to:
Post Comments (Atom)
9 comments:
I will be so bold as to say what follows is a spoiler. I may sometimes stumble on my way toward completing the square, but I will truly despair the day I cannot recall Euclid's lovely proof of the infinitude of primes.
Assume some number p is the largest prime. Calculate the larger number P' by multiplying the series 2 x 3 x 4 x ... x p and adding 1. Is P' prime or composite? Dividing P' by any number less than or equal to p will leave a remainder of 1. Therefore, P' is prime, and our original assumption that the largest prime p exists is untrue. Q.E.D.
This is actually a little more elegant than what I remember as the canonical proof - meaning that my memory is probably wrong.
The way I remember it is: let p' = p1 x p2 x p3 x ... x pn + 1, where pn is the largest prime. This is composite by assumption, so some prime divides it. But that prime also divides the product of all primes, and hence must also divide 1, which no integer does.
Err, make that "...which no _prime_ does"
I've been itching to look up the real proof, because I can't figure out how to rebut this objection:
"Sure, no number less than or equal to p divides P', but maybe p+14 times p+38 equals P'."
Henh? Not following you here. Who said "no number less than or equal to p divides P'"?
Longer form of my version:
Suppose there are only finitely many primes
Then enumerate them in ascending order: p1, p2, ..., pn
Then let k = p1*p2*...*pn + 1
Clearly k > n, so k is composite by assumption
Therefore some number x divides k
Because of the fundamental theorem of arithmetic, we can assume x is prime, and therefore divides the product of all primes
But the simplest children in the streets have long known that if a + b = c, and d divides both a and c, then d must divide b as well
So x must divide 1, which it doesn't
so there are infinitely many primes, QED.
Oh, you said "no number less than or equal to p divides P'". So my proof must be the real one. Guess you better start despairing.
However, your faux proof is very useful as a starting point for the followup I posted.
Yes, my confidence is shaken, but your version is unnecessarily complex.
If k is one plus the product of all the (assumed finite collection of) primes, then k is demonstrably prime, because no existing prime divides it evenly. They all leave a remainder of 1. I gummed things up by throwing all the integers into the product, but there's no need to invoke unwieldy fundamental theorems.
The objection I proposed is neatly handled by answering that p+14, being larger than the assumed largest prime, is the product of smaller prime numbers. If P' is a multiple of p+14, then it must be a multiple of all factors of p+14, but we have already seen that no primes are factors of P'.
Thanks to xkcd, here is the proof in Haiku format ;)
http://xkcd.com/622/
Post a Comment