Prime numbers

 What is a prime number?
A natural number is said to be prime if it is greater than 1 and cannot be written as the product of two smaller natural numbers. For example, 7 is a prime number, since it has no factors other than 7 and 1. In contrast, 12 is not a prime number, since 12 can be written, for example, as the product of 2 and 6. By trial and error one can easily check whether a number is prime, provided that the number isn’t too large. If one has a suitably programmed computer available, one can easily check that the number 1236718507534581290478731 is also prime.

Prime numbers have fascinated mathematicians for over 2000 years. Although many deep facts about prime numbers have been discovered, there remain many open problems.

 Prime numbers are the ‘building blocks’ of the integers
Prime numbers cannot be broken down into smaller multiplicative factors. Every other natural number greater than 1 can be represented as the product of two or more prime numbers. Thus 20 equals 2 times 2 times 5, and 110 equals 2 times 5 times 11. Such a product representation is unique up to the order of the factors. Making a somewhat daring analogy, if we consider the numbers 1, 2, 3, 4, … as the ‘molecules’ among the numbers, then the prime numbers are the ‘atoms’. In particular, we conclude that every natural number greater than 1 has a divisor that is a prime number.

 How many prime numbers are there?
After some exposure to the set of natural numbers one quickly comes to the conjecture that there must be infinitely many prime numbers: one can always find bigger and bigger primes. That this supposition is in fact true was proved in ancient Greece by Euclid. His proof is one of the best-known proofs in all of mathematics, and it is not particularly difficult:
The idea of the proof is that if one can produce n prime numbers, then there must be at least one more prime number. If there is indeed such a procedure for producing prime numbers, then there can be no limit on the number of primes. The procedure goes like this: if we are given n prime numbers, let us begin by giving them names; we shall call them p1, p2, …, pn. We then form the product m of all these numbers and add 1, that is, m = p1 • p2 •… • pn + 1. 

We now consider this—likely very large—number m and ask whether there is divisor of m that is prime. Of course there is; the fact that there is at least one such prime divisor was explained in the previous section. We shall call this prime divisor p. And now we come to the point: we can divide m by p with zero remainder, since p is a divisor of m. But if, on the other hand, we divide m by p1 (or by p2 or by p3 or by …), then the remainder is not zero, but 1. Thus we conclude that p cannot be one of the numbers p1, p2, …, pn, and so we have found a new prime number.

Conclusion: There are infinitely many prime numbers.

 How can we find prime numbers systematically?
The best-known procedure for finding prime numbers is the sieve of Eratosthenes, named for the Greek mathematician Eratosthenes of Cyrene, who lived in the third century BCE. Here is how he proposed that one could find all the prime numbers:

  • Write down all the natural numbers, beginning with 2, in a row: 2, 3, 4, 5, 6, 7, 8, 9, ….
  • Strike out all the integer multiples of 2 (other than 2 itself), that is, 4, 6, …:  the result is 2, 3, 4, 5, 6, 7, 8, 9, … .
  • Now strike out all the multiples of 3, that is, 6, 9, … (note that 6 was already eliminated in the previous round): 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, … .

And so on. Next come the multiples of 5, then those of 7, and so on. To be precise: In the kth round, the kth number in the list that has not been eliminated is in fact the kth prime number. Strike out all the multiples of that number, which of course are not prime.
The reason that the method works is simple: every nonprime n has a proper prime divisor p, and if p is the jth prime number, then n will be struck out during the jth round.

 How are the primes distributed?
It is plausible that as the integers get larger and larger, there should be fewer and fewer primes scattered among them, since for large values of n, many more numbers have the chance to be a divisor of n. It thus seems certain that a smaller percentage of the integers between 1 and 1000 will be prime than between 1 and 100. But what is the exact situation?

To make it easier to speak about the problem, let P(m) denote the number of primes that are less than or equal to m. (For example, P(10) = 4, since there are four prime numbers below 10, namely 2, 3, 5, and 7.)

How large is P(m) for large m? Or to ask the question more precisely: how large is the ratio of P(m) to m? Gauss devoted much thought and computation to this question and conjectured the correct relationship. However, it was not until the end of the nineteenth century that a proof was found. Gauss’s conjecture, now called the prime number theorem, was proved independently by Hadamard and de la Vallée-Poussin.

Here is the relationship: Let ln(m) denote the natural logarithm of m. Then the ratio of P(m) to m is well approximated, at least for ‘large’ values of m, by 1/ln(m).
For those unfamiliar with the natural logarithm, here is another formulation. Take any positive integer r, for example r = 10, and compute m = 2.718r. In our example, since r = 10, we have m = 2.71810, which is very close to 22012.

Then the following is true: the proportion of prime numbers less than or equal to m in 1,...,m is approximately 1/r. In our example, we conclude that about 1/10 of the numbers less than 22012 are prime.


 Primality tests
Even with the aid of a computer, it can be very tedious to tell whether a very large number m is prime by testing every number less than m, asking in each case, is n a factor of m? However, it can easily be seen that one need test only up to the square root of m, since if n is a divisor of m, then so is m/n, and both n and m/n cannot be greater than the square root of m.

But even so, that can still amount to a large number of tests. For example, if m has 100 digits, then the square root has 50 digits. If a computer can test one million values of n per second (test: is n a factor of m?), then the computer would have to work longer than the current age of the universe.

There are, however, better tests. Here is the best-known of them:
The starting point is a fact that was discovered by Fermat. It is necessary first to know what is meant by ‘a modulo b’ for two integers a and b: by a modulo b we mean the remainder when a is divided by b. (For example, 15 modulo 2 equals 1, and 139 modulo 4 equals 3.)
Fermat was able to show that if you take a prime number p and an integer a between 1 and p – 1 and then compute ap – 1 modulo p, the result is 1.

Let us test this for p = 5 und a = 3. First, 34 equals 81, and if we calculate 81 modulo 5, we indeed get 1.

So what makes this a primality test? If we wish to test whether m is prime, we can choose a number a smaller than m and check whether am – 1 modulo m is equal to 1. Computers can do this calculation in a flash, even for very large numbers. If the result is a number different from 1, then we may be certain that m is not a prime number, even though we do not know a single factor of m.
With this test one can generally quickly identify a composite number (that is, a number that is not prime), since for such a number a few random choices of a will generally yield a value different from 1, proving that the number is composite.

On the other hand, if we run the test on a number m with several different values of a and get 1 every time, we may conclude that m is probably prime.

However, this test has a big flaw: there exist composite numbers, called Carmichael numbers, that always produce the value 1, even though they are not prime. The smallest Carmichael number is 561. Since 1992 it has been known that there are infinitely many such ‘duds’. However, they are sparsely distributed among the integers. Fortunately there are other tests, too complicated to describe here, that always work.


 Some special prime numbers
For numbers with a particularly simple structure there are primality tests that are much more effective, allowing much larger candidates for primality to be investigated than can be done with the usual tests. A well-known class of such numbers is the Mersenne primes, which are prime numbers of the form 2r – 1. For example, 7 (= 23 – 1) and 31 (= 25 – 1) are Mersenne primes. Note, however, that 2r-1 is not a prime for every choice of r. For example, with r = 4, the result is 24 – 1 = 15, which is surely not prime.

Whether a number 2r-1 is prime for quite large values of r can be determined relatively quickly with the help of a computer. Thus it is no wonder that all the prime records of recent years have been captured by Mersenne primes (see below).

There are also primes of the form 2r + 1, and these are called Fermat primes. Simple examples are 5 and 17; it is unknown whether there are infinitely many such primes. Surprisingly, these numbers are important in geometry: a regular n-gon can be constructed with straightedge and compass if and only if n is the product of distinct Fermat primes and a power of 2. Thus a 17-gon can be constructed (17 = 17 • 20), as can an 80-gon (80 = 5 • 24). However, a 7-gon is not constructible. (We mention that the 19-year-old Gauss was the first to prove this fact.)

 Prime numbers are useful!
Prime numbers play an important role in public key cryptography. The idea is this: One finds two large prime numbers p and q (here ‘large’ means several hundred digits). These numbers are kept secret. Then one computes the product of p and q, which we shall call n. The number n is made public to anyone who wants it. Knowing the value of n allows one to encrypt messages that can be decrypted only by someone who knows the values of p and q. The point is this: With today’s methods it is essentially impossible, given the product of p and q of size several hundred digits, to figure out what p and q are, while it is relatively easy to find prime numbers of this size. Of course, such a system will not work with small numbers. If the product is, say, 77, you can easily figure out that the prime divisors are 7 and 11. But what if I give you the number
78457630683971672300324001194081223769 ?

You may not get very far with pencil and paper, though a computer factorization program will find the factors in less than a second. But even a computer will be unable to factor a 400-digit product of two prime numbers.
The security of many cryptographic systems relies on the difficulty of factoring large numbers, and thus considerable excitement was generated when the idea of quantum computing was developed, which offers the possibility of factoring very large numbers very quickly. However, at present quantum computers exist only on paper. (How quantum computing could revolutionize cryptography is described more fully in the book Mathematics Everywhere, by Martin Aigner and Ehrhard Behrends, American Mathematical Society 2010.)

 The largest prime number known
As of September 2010, the largest known prime is 243112609 – 1.

It is, as can be seen, a Mersenne prime. There are no similar tests for other types of prime numbers of this size. This record-holder has 12,978,189 digits. If you wanted to print it in a book, you would have quite a thick volume! More information on prime records can be found at the Internet site for Mersenne primes.

 The Goldbach conjecture
Prime numbers are defined by a multiplicative property, and it can be difficult to determine answers to questions about prime numbers related to addition. The most famous problem in this area is doubtless the Goldbach conjecture, named after the eighteenth-century mathematician Christian Goldbach:
Is it true that every even number greater than 2 can be written as the sum of two prime numbers?
(For example, we have  4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7, …; does this always work?)

This appears to be a very difficult problem; many prominent mathematicians have sought a proof in vain. 
Anyone who solves this problem will achieve instant fame and fortune.

(Ehrhard Behrends, Freie Universität Berlin)