# Are There Infinitely Many Primes?

The purpose of this document is to provide an informal explanation of how one might prove the following result, which first appeared in Euclid's Elements.

Theorem: There are infinitely many prime numbers.

Let's think about the overall structure that a formal proof of this result might have. Since it's highly unlikely that we can simply write down an infinite list of primes, we'll have to proceed indirectly. One of the standard paradigms for mathematical proofs is the method of proof by contradiction. In brief, that means we start by tentatively assuming that the result is false, and try to derive a contradiction from that assumption. If we succeed, then our tentative assumption must have been incorrect.

Let's see how this method plays out in the present case. So, we need to examine the consequences of having only finitely many primes. In this situation, we could make a list of all the prime numbers, say

$P$1, P2, ..., PM.

Using only this list of primes (and the barest minimum of other information) we need to construct another prime number that is not on the list. How can we do that?

Finding an elegant proof to a mathematical theorem may require you to play a delicate game to figure out what you already know and are, therefore, allowed to use in the proof. In this case, we only have two definitions available: the definition of a prime number and the definition of what it means for one number to divide another. So, that means we have to take our finite list of primes and use it to produce a new prime, using only the idea that a prime number has very few divisors. Since it's hard to produce a prime number directly, we would be satisfied if we could construct a number N such that:

1. None of the primes Pi divides N, but
2. Some other prime Q divides N.
Then Q will give us the new prime that we need.

The remaining problem, then, is how can we produce the number N? It's easy to produce a number that is divisible by all the primes on our list; just take the product

P1 P2 ... PM.

Unfortunately, that's not what we want. We need to produce a number that is not divisible by any of the given primes. Can we change this highly divisible number into something that is highly non-divisible? Yes! Take

N = P1 P2 ... PM + 1.

Now the only problem is to check formally that this number has the desired properties.

Disclaimer: This page was last updated on 12 October 2002. It is entirely possible that the information contained herein no longer has any connection with reality (assuming it ever did). Feel free to send constructive comments or inane criticisms to:
Kevin R. Coombes
Department of Biostatistics
University of Texas M.D.Anderson Cancer Center
1515 Holcombe Blvd., Box 447
Houston, TX 77030