

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.
It is a common mistake to think that this proof says the product p_{1}p_{2}...p_{r}+1 is prime. The proof actually only uses 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 counts of units (the unit, one, was not a number, two was thier first) and represeted them with lengths of line segments (multiples of some unit line segment). Where we talk of divisibility, Euclid wrote of "measuring," seeing one number (length)a as measuring (dividing) another 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 (in this regard). For example, they viewed lines as segments 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 todaygiving 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.
Note that what is found in this proof is another primeone not in the given initial set. There is no size restriction on this new prime, 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 the smallest choice of P is the product of these seven primes plus on, so P = 547^{.}607^{.}1033^{.}31051. The new prime found would be 547, 607, 1033 or 31051, all of which are smaller than the last prime in the original set. 
Another prime page by Chris K. Caldwell <caldwell@utm.edu> 