Are There Infinitely Many Primes?

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$₁, P₂, ..., 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:

1. None of the primes P_i divides N, but
2. 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₁ P₂ ... 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₁ P₂ ... 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]