At this point it's a good idea to mention that the search for 100, or 1000, or how every many prime numbers is not hopeless; that is the content of Euclid's famous theorem on the infinitude of the primes.

Strictly speaking, he proves that no matter what \(n\) is, there is always a bigger prime \(p\gt n\), which isn't exactly the same thing as a Cantoresque “infinite set of primes”! But we still say there are infinitely many prime numbers.

As usual, Joyce's web version of the original is a great resource. There are many proofs of this theorem, some of which would be corollaries of theorems later in this text. Most use some form of proof by contradiction, but there are exceptions, such as Saidak's proof from the American Math Monthly, which we will mention again in Section 21.1. One notable proof by Furstenberg even uses point-set topology, though this has been interpreted in a non-topological way as well.

Here is a slightly modernized version of Euclid's proof.

There are two things worth pointing out about this proof. First, Joyce points out that Euclid doesn't bother to mention that \(N\) is in fact the product of the primes in question. It's not necessary to mention, but using this characterization, the same proof would show the (weaker but also interesting) conclusion that there is no upper bound on the size of a set of mutually coprime positive integers. Secondly, as is typical, Euclid only proves this with a small \(n\), rather than with some modern stand-in like ellipses; those interested in math history will be interested in how Wallis used this to his advantage in the Hobbes-Wallis controversy.

Much later in the text we will talk some about efficient ways to tell if a number is prime, or to get prime numbers (see Chapter 12, for example). For now, all we will use is something usually known as the Sieve of Eratosthenes.

This is indeed an algorithm, because it provides a specific procedure to identify primes up to a specific limit.

Eratosthenes was a contemporary of Archimedes, and no slouch. He is best known for estimating the size of the Earth fairly accurately, amazingly so for the time. (Along the way, that puts the lie to those who would claim everyone thought the earth was flat until Columbus.)