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

P₁, P₂,..., P_M.

Consider the integer

N = P₁P₂...P_M + 1.

None of the primes P_i can divide N, since then P_i 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.

[Home Page] [Bioinformatics] [Mathematics] [Creative Efforts]

[HOME] [PREVIOUS] [NEXT] [UP] [DOWN]