**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}, P_{2}, ...,
P_{M}.

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:

- None of the primes
`P`divides_{i}`N`, but - Some other prime
`Q`divides`N`.

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

`P _{1} P_{2} ... P_{M}.`

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

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

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

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

Kevin R. Coombes

Department of Biostatistics

University of Texas M.D.Anderson Cancer Center

1515 Holcombe Blvd., Box 447

Houston, TX 77030