NTIC To Infinity and Beyond

Section 6.2 To Infinity and Beyond

Subsection 6.2.1 Infinite primes

At this point it's a good idea to mention that the search for 100, or 1000, or however many prime numbers is not hopeless! That is the content of Euclid's famous theorem on the infinitude of the primes (Elements Proposition IX.20).

🔗

Strictly speaking, he proves that no matter what

n

is, there is always a bigger prime

p > n .

This is not the same as proving there is an actual “infinitely large set of primes” in the sense of Cantor's infinite cardinalities! 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 [E.7.22], which we will mention again in Section 21.1 (see also Exercise 21.5.3). One notable proof by Furstenberg uses point-set topology, though this has been interpreted in a non-topological way as well. There is even a proof using regular languages/expressions ([E.7.39]) suitable for use in an upper-level computer science course on computational models.

So many that it is hopeless to keep up with all of them. I have a stack of recent proofs in my office I originally intended to occasionally add to the references, but it quickly grew out of proportion to other topics in the book!

🔗

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

🔗

Theorem 6.2.1. Infinitude of Primes.

There is no upper bound on the size of the collection of prime numbers.

🔗

Proof.

Suppose that we have found exactly $n>0$ prime numbers, $p_1,p_2,\ldots,p_n\text{.}$ Find the smallest positive integer $N$ which is a multiple of all of these simultaneously (we know at least one such number exists, since you could multiply them all together).

Then either $N+1$ is prime, or it is not⁴. If $N+1$ is prime, then it is certainly different from the others, so we have increased the size of the set of primes.

Euclid used line segments to indicate magnitudes, including integer ones like what we call $N+1\text{.}$ So this claim looks like ὁ δὴ ΕΖ ἤτοι πρῶτός ἐστιν ἢ οὔ in the original, where EZ is the line segment.

If on the other hand $N+1$ is not prime, then it has some nontrivial factor; in fact, it has a prime divisor $p\text{.}$ (This distinction does actually require proof, and is Euclid's Book 7, Proposition 31, but we will let it follow immediately from Theorem 6.3.2 instead.) We claim $p$ is not one of the $p_i$ already known.

If it were, then if $p$ is a divisor of both $N$ and $N+1\text{,}$ which means it is a divisor of $1$ (see Exercise 2.5.7). This is absurd (ἄτοπον, literally ‘out of place’). Can you recall why?

So $p$ is not one of the original list, and is prime, so we have found a larger list than before.

🔗

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. If one didn't have the concept of primality, and instead started with a set of mutually coprime positive integers (recall Definition 2.4.9) then an analogous proof would show the (weaker but still interesting) result that there is no upper bound on the size of such a set.

🔗

Secondly, as is typical, Euclid only proves this with a small

n,

rather than with some modern stand-in for infinity like ellipses. See Figure 6.2.2 ⁵. Those interested in math history will be interested in how Wallis used this to his advantage in the Hobbes-Wallis controversy.

See the Clay Math Institute website for more images from this manuscript, held at the Bodleian, which is well over a millennium old.

🔗
Figure 6.2.2. Part of proof of Euclid IX.20 (Image courtesy of the Clay Mathematics Institute. No commercial use allowed.)

🔗

Subsection 6.2.2 The sieve of Eratosthenes

🔗

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

🔗

Algorithm 6.2.3. Sieve of Eratosthenes.

To check whether a number $n > 1$ is composite or prime, it suffices to divide by all primes $p \leq \sqrt{n} .$ Anything that isn't divisible by these is prime.

🔗

Proof.

If $n$ is not prime (composite), we can write $n=de$ for integers $d$ and $e$ both strictly between $1$ and $n\text{.}$ If both $d,e\gt \sqrt{n}\text{,}$ then

\begin{equation*} n=de\gt \left(\sqrt{n}\right)^2=n\text{,} \end{equation*}

a contradiction.

🔗

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

🔗

Example 6.2.4.

To get all prime numbers up through 100, it suffices to remove any numbers divisible by $2, 3, 5,$ or $7,$ as $\sqrt{100} < 11 .$

🔗

Historical remark 6.2.5. Eratosthenes.

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.)

🔗

Finding tighter results, like the smallest prime above a certain number, requires more advanced techniques like the ones in Section 12.2. An interesting, but completely impractical, fact (see [E.7.34]) is that the smallest prime exceeding

n

is the smallest nontrivial divisor of

n!^{n!^{n!}} - 1 .