information:filtering, information:classification
Euclid's proof

Euclid offered a proof published in his work Elements (Book IX, Proposition 20), which is paraphrased here.

Consider any finite list of prime numbers p, p,..., p. It will be shown that there exists at least one additional prime number not included in this list. Let P be the product of all the prime numbers in the list: P = p p... p. Let q = P + 1. Then q is either prime or not:

This proves that for every finite list of prime numbers there is a prime number not in the list. In the original work, as Euclid had no way of writing an arbitrary list of primes, he used a method that he frequently applied, that is, the method of generalizable example. Namely, he picks just three primes and using the general method outlined above, proves that he can always find an additional prime. Euclid presumably assumes that his readers are convinced that a similar proof will work, no matter how many primes are originally picked.

Euclid is often erroneously reported to have proved this result by contradiction beginning with the assumption that the finite set initially considered contains all prime numbers, though it is actually a proof by cases, a direct proof method. The philosopher Torkel Franzén, in a book on logic, states, "Euclid's proof that there are infinitely many primes is not an indirect proof The argument is sometimes formulated as an indirect proof by replacing it with the assumption 'Suppose q,... q are all the primes'. However, since this assumption isn't even used in the proof, the reformulation is pointless."