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