Vignette 2
How many Prime Numbers are There?

The branch of mathematics known as number theory studies the integers and their properties.  Much of number theory is concerned with divisibility relationships among integers.  Since we have all studied these ideas since the early grades of school, many of the problems of number theory can be understood by intelligent people with little advanced mathematical background, and so this area of mathematics has attracted many amateur mathematicians through the years.  The area of number theory also holds many results that are hundreds, and even thousands, of years old--yet it is rich enough to be a fertile ground for research in mathematics today.

Prime Numbers

The concept of a prime number is one with which you have been familiar for a number of years.  A positive integer greater than 1 is called prime if its only positive divisors are 1 and the number itself.  Thus, the prime numbers: 2, 3, 5, 7, 11, 13, 17, ... serve as building blocks for other integers.  Indeed, it is known that every positive integer greater than 1 can be expressed uniquely (except for rearrangement of order) as a product of prime numbers.  (The prime numbers used in factoring a given number are unique, but the order, of course, is not.)  The process of finding the primes involved in the factorization of a positive integer is one that you no doubt studied in school.

How Many Primes are There?

We will now consider the question of how many prime numbers there are.  The following investigation of this question is over two thousand years old, and is attributed to Euclid.

Two possible answers to the question are that there are either finitely many primes, or there are infinitely many of them.  We will show that the first answer is not possible, and therefore there are infinitely many primes.  (This approach is referred to as "proof by contradiction."  In general, proof by contradiction works like this: we know that there are only two possible answers to a question; we assume that the first answer is the correct one, and then discover that this leads to an inconsistency; and so we conclude that it is actually the second of the two answers that is correct.)

Euclid's Proof

So let's suppose that there are only finitely many primes, say n of them.  We could then make a list of these n primes, say p1, p2, ..., pn.  Then consider the integer

obtained by multiplying all of the primes, and then adding 1.  This new number m is either prime or it is not.  But m is clearly larger than all of p1, p2, ..., pn so it cannot be one of the primes.  So m is not prime, and therefore must be evenly divisible by some prime.  But we are supposing that the only primes are p1 through pn--and none of these primes divides m evenly, for when m is divided by one of these primes, the remainder is 1.  This contradiction shows that the supposition that p1, p2, ..., pn is a complete list of all primes must be false.  Our conclusion is that there are not finitely many primes; there are infinitely many.

Can We Generate all Primes?

We now know that there are infinitely many prime numbers.  But what are these numbers?  It is certainly possible to begin a process that will generate prime numbers indefinitely.  All we have to do is start with the number 2, which we know is the first prime.  We will keep a list of new primes as they are discovered, as we examine each positive integer in turn.  When we come to another integer, we test to see if it is divisible by any of the primes in our list.  If it is, then the new number is not prime; if it is not, then it is prime, and we add it to our list of primes. But of course, this process will never end, so there are always prime numbers (very large numbers) that have not yet been discovered.  Every now and then, you will see a little paragraph in the newspapers when someone discovers a new prime number.

But is there a formula by which we can generate all of the primes?  That is, can we determine the nth prime, for any value of n?  The short answer is "No,"  although there are a few tantalizing pattern fragments.  For example, the numbers 31, 331, 3331, 33331, 333331, 3333331, and 33333331 are all prime numbers.  But the pattern is broken with the next number in this sequence: 333333331 is not prime; it can be factored as 17 times 19607843.  As another example, the formula , when used with n = 0, 1, 2, ..., 40, produces prime numbers; however, the formula fails at n = 41.  It is actually known that there is no polynomial formula that produces only prime numbers as values.

Further Exploration