Reasoning: An Introduction to Logic, Sets, and Functions

Subsection 8.3.5 There is No Largest Prime Number

We’ll now prove another important result using a proof by contradiction. We’ll prove that there exists no largest prime number.

Consider the claim that there is no largest prime number. Following Euclid, we prove this claim by assuming, to the contrary, that the set P of prime numbers does contain some largest element. So there exists some value of n such that there are exactly n prime numbers and

\(P = {p_1, p_2, p_3, \cdots p_n}. \)

Let q be the product of all of those primes, plus 1. So we have:

q = (p1p2p3 … pn) + 1.

Since q is greater than each pi, it is not on the list of primes. So it must be composite. In that case, it must have at least one prime factor, which must then be an element of P. Suppose that factor is pk, for some k  n. Then q must have at least one other factor, some integer i such that:

\begin{align*} q \amp = ipk. But \ q was defined to be (p_1 p_2 p_3 \cdots pn) + 1. So we have: \\ (p_1 p_2 p_3 \cdots p_n) + 1 \amp = ipk. Subtracting ipk and 1 from both sides, we get: \\ (p1p2p3 … pn) - ipk = -1. \end{align*}

Now observe that pk evenly divides both terms on the left since it is prime and so must be in the set {p1, p2, p3, … pn}. Factoring it out, we get the following (where we list all the primes up to pk, then we skip it, and list all the ones after it):

pk(p1p2pk-1 pk+1… pn - i) = -1. Dividing by (p1p2pk-1 pk+1… pn - i), we get:

pk = (-1)/(p_1 p_2 p_(k-1) p_(k+1) … p_n - i)

But, since the denominator (p1p2pk-1pk+1 … pn - i) is an integer, this means that |pk| < 1 (for the same reason that ½ and ¼ are less than 1). But that cannot be true since pk is prime and thus greater than 1. Contradiction. Recall that pk was chosen to be some arbitrary prime factor of q. We now know that that arbitrary value is not in fact a prime number. So no other value can be a prime factor of q either. (Notice the way we have used Existential Instantiation and Generalization.) So q is not composite. Since q is greater than 1 and not composite, it must be prime, contradicting the assumption that all primes are in the set {p1, p2, p3, … pn}.

Notice that the proof we just did, in addition to being a proof by contradiction, is constructive. It exhibits a specific example that contradicts the initial assumption. We’ll soon see more uses of this proof by construction technique.