# The Infinitude of Primes

One of the most elegant results in the history of mathematics is also one of the earliest. In Euclid's Elements, the following theorem appears:

Theorem: There are infinitely many prime numbers.

Proof: We proceed by contradiction. Assume that there are only finitely many primes. Let a complete list of the primes be

P1, P2,..., PM.

Consider the integer

N = P1P2...PM + 1.

None of the primes Pi can divide N, since then Pi would also divide 1, which is impossible. However,every integer N can be written as a finite product of prime factors. Any one of those prime factors is a new prime that is not on the original list. Thus, our assumption that there are only finitely many primes has been contradicted, and there must actually be infinitely many primes.

## Proof Analysis

Good mathematicians don't quit when they get to the end of a proof. Important proofs almost always give rise to new and interesting questions. In the present case, I can think of at least two illustrations of that phenomenon. First, the proof spells out a recipe for producing new primes from old ones. How good is that recipe? Second, the same basic idea can be used to prove a more general result.

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