# 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`_{1}, P_{2},..., P_{M}.

Consider the integer

`N =
P`_{1}P_{2}...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]

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