Euclid may have been the first to give a proof that there are infinitely many primes. Even after 2000 years it stands as an excellent model of reasoning. Below we follow Ribenboim's statement of Euclid's proof [Ribenboim95, p. 3], see the page "There are Infinitely Many Primes" for several other proofs.
Theorem.
There are infinitely many primes.
Proof.
Suppose that p1=2 < p2 = 3 < ... < pr are all of the primes. Let P = p1p2...pr+1 and let p be a prime dividing P; then p can not be any of p1, p2, ..., pr, otherwise p would divide the difference P-p1p2...pr=1, which is impossible. So this prime p is still another prime, and p1, p2, ..., pr would not be all of the primes.
It is a common mistake to think that this proof says the product p1p2...pr+1 is prime. The proof actually only using the fact that there is a prime dividing this product (see primorial primes).
The proof above is actually quite a bit different from what Euclid wrote. We now understand the integers as abstract objects, but the ancient Greeks understood them as lengths of line segments (multiples of some unit line segment). Where we talk of divisibility, Euclid wrote of "measuring," seeing length a as measuring (dividing) length b if some integer numbers of segments of length a makes a total length equal to b.
The ancient Greeks also did not have our modern notion of infinity. School children now easily understand lines as infinite, but the ancients were again more concrete. For example, they viewed lines as something that could be extended indefinitely (not something infinite that we view just part of). For this reason Euclid could not have written "there are infinitely many primes," rather he wrote "prime numbers are more than any assigned multitude of prime numbers."
Finally, Euclid sometimes wrote his "proofs" in a style which would be unacceptable today--giving an example rather than handling the general case. It was clear he understood the general case, he just did not have the notation to express it. His proof of this theorem is one of those cases.
Below is a proof closer to that which Euclid wrote, but still using our modern concepts of numbers and proof. See David Joyce's pages for an English translation of Euclid's actual proof.
Theorem.
There are more primes than found in any finite list of primes.
Proof.
Call the primes in our finite list p1, p2, ..., pr. Let P be any common multiple of these primes plus one (for example, P = p1p2...pr+1). Now P is either prime or it is not. If it is prime, then P is a prime that was not in our list. If P is not prime, then it is divisible by some prime, call it p. Notice p can not be any of p1, p2, ..., pr, otherwise p would divide 1, which is impossible. So this prime p is some prime that was not in our original list. Either way, the original list was incomplete.
You can see that it is a very sort step from this proof, to the version given above. It is also worth noting that what is found in this proof is another prime, one not in the given initial set. It may even be smaller than some of those in the initial set. For example, if we begin with the set:
{2, 3, 7, 43, 13, 139, 3263443},
then P = 547.607.1033.32051. The new prime found would be 547, 607, 1033 or 32051, all of which are smaller than the last prime in the original set.
![[Linked Image from i6.photobucket.com]](http://i6.photobucket.com/albums/y203/JoeMama13/RedSoxBanner05.png)
