Section4.1To Infinity and Beyond

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

The handout is a particularly cute proof which appeared in the MAA Monthly a few years back. As usual, Joyce's web version of the original is a great resource. There are many proofs of this theorem, and we may see some unusual ones later.

Here is a slightly modernized version of Euclid's proof. We aim to prove there is no upper bound on the size of the collection of prime numbers.

  • Suppose that we have found exactly \(n>0\) prime numbers, \(p_1,p_2,\ldots,p_n\).
  • Take the least common multiple of these, and call it \(N\). We will consider the status of \(N+1\).
  • Then \(N+1\) is either prime, or it is not. ("ὁ δὴ ΕΖ ἤτοι πρῶτός ἐστιν ἢ οὔ.")
  • If it is prime, then it is certainly different from the others, so we have increased the size of the set of primes.
  • If it is not prime, then it has some prime divisor \(p\). (This actually does require proof, and is Euclid's Book 7, Proposition 31. See below.)
  • We claim \(p\) is not one of the \(p_i\) already known. For if it were, then if is a divisor of both \(N\) and \(N+1\), which means it is a divisor of \(1\).
  • This is absurd (“ἄτοπον”). (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.
Joyce points out that Euclid doesn't bother to mention that \(N\) is in fact the product of the primes in question. We don't need this, and furthermore it shows that 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.

Subsection4.1.1The Sieve of Eratosthenes

Much later in the course we will talk some about efficient ways to tell if a number is prime, or to get prime numbers. For now, all we will use is something usually known as the 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\). If both \(d,e>\sqrt{n}\), then \[n=de>\left(\sqrt{n}\right)^2=n\; ,\] a contradiction.

This is nice, because to get all numbers up through 100 it suffices to remove any numbers divisible by \(2,3,5\), or \(7\). By the way, 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. (This also puts the lie to those who would claim everyone thought the earth was flat until Columbus.)