## Prime Pursuits

Ivars Peterson

#### PRIME PROPERTIES

The study of prime numbers has long been a central part of number theory, a field traditionally pursued for its own sake and for the beauty of its results. Once thought to be the purest of pure mathematics, this ancient pastime now figures prominently in modern computer science. The security of modern cryptosystems depends very strongly on the twin questions of how easy it is to identify primes and how hard it is to factor a large, random number. Neither question has a clear answer yet.

Divisible evenly only by themselves and the number 1, the primes stand at the center of number theory. Like chemical elements in chemistry or fundamental particles in physics, they are building blocks in the mathematics of whole numbers. All other whole numbers, known as composites, can be written as the product of smaller prime numbers. In fact, according to the fundamental theorem of arithmetic, each composite number has a unique set of prime factors. Hence, the composite number 20 can be broken down into the prime factors 2, 2, and 5. No other composite number has the same set of factors. The number 1 is considered to be neither prime nor composite.

Whereas chemists have only a hundred or so elements to play with, mathematicians interested in number theory must deal with an endless supply of primes. More than 2,000 years ago, Euclid proved that there is an infinite number of primes, and mathematicians ever since have been caught up in the never-ending pursuit of primes. Euclid's argument is instructive. His proof relies on establishing a result that contradicts his initial assumption. The proof begins with the idea of a finite number of primes, with some largest prime, p. If all the primes are multiplied together and 1 is added to this gigantic product, a new number, N, emerges that is larger than p. If the initial assumption is correct, then N can't be prime because otherwise it would be the largest prime. It must be a composite and divisible by at least one smaller prime number. However, because of the way N was put together, all known primes, when divided into N, would leave a remainder of 1. Therefore, N must be a prime that is larger than p. This contradicts the starting assumption and forces the conclusion that there can be no largest prime. There are, instead, infinitely many primes.

With such a vast array of numbers to work with, finding primes shouldn't be difficult. However, because prime numbers behave perversely and are scattered among the whole numbers in seemingly unpredictable ways, special nets are needed to catch them. Euclid's proof suggests one potential method for constructing prime numbers: multiply together all primes up to a certain value, then add 1.Is the result always a prime number? A simple experiment is revealing: 2 + 1 = 3;
2 x 3 + 1 = 7;
2 x 3 x 5 + 1 = 31;
2 x 3 x 5 x 7 + 1 = 211;
2 x 3 x 5 x 7 x 11 + 1 = 2,311.
It looks promising. But 2 x 3 x 5 x 7 x 11 x 13 +1= 30,031 =59 x 509
In fact,the next four instances prove to be composites. Further explorations show that Euclid's construction often but not always produces a prime.

In prime-number theory, simple, reasonable questions are remarkably easy to ask, yet many of these questions are surprisingly difficult or even impossible to answer. Is there a general formula that reliably generates prime numbers? Given a prime number, how far is it to the next one? Are there infinitely many twin primes, or consecutive pairs, such as 3 and 5, 41 and 43, and so on? No one knows yet. And there are dozens of similar conjectures waiting for proofs.

Fortunately, students of primes do have a systematic, though computer-consuming, way to trap primes and separate them from composites. Of course, they use a sieve for such a job. This particular sieve was discovered in the third century B.C. by Eratosthenes of Cyrene and goes by his name. The sieve of Eratosthenes generates a list of prime numbers by the process of elimination. To find all prime numbers less than, say, 100, the pursuer writes down all the integers from 2 to 100.First,2 is circled, and all multiples of 2 (4, 6, 8,... are struck from the list .That eliminates all composite numbers that have 2 as a factor. This step incidentally, also confirms that 2 is the only even prime number a rather odd result, some would say.

The next unmarked number is 3. That number is circled, and all multiples of three are crossed out. The number 4 is already crossed out, and its multiples have also been eliminated. Five is the next unmarked integer,and the procedure continues in this way until only prime numbers are left on the list. In this example, the job finishes with 7 because 8,9 and 10 are already gone, and 11 is greater than the square root of 100,the largest number in the table. All multiples of 11 less than 100 would already be crossed out. The sieve ends up trapping 25 numbers - all the primes less than 100 (see Figure 2.1).
 Figure 2.1 The sieve of Eratosthenes catches 25 primes among whole numbers less than 100.

Although some shortcuts simplify the sieving, it remains a tedious, time-consuming procedure, especially when the targets are dozens or hundreds of digits long. Sieving is a serious business for number theorists, and because they have no reliable formulas that automatically generate only prime numbers of any desired size, they use the sieve of Eratosthenes to fill in the gap. The claims of some mathematicians, both amateur and professional, to have found a magic formula for primes have invariably turned out to be false. In many cases, the formulas are merely cleverly disguised versions of the ancient sieve of Eratosthenes.

Because so many important ideas in number theory seem resistant to definitive analysis, experiment plays an important role in this field of mathematics research. Although their work differs from the experimental research associated with, say, test tubes and noxious chemicals, number theorists, like chemists and other researchers, often collect piles of data before they can begin to extract the principles that neatly account for their observations. Strict reliance on deduction-the hops, steps, and jumps from one theorem or logical truth to another that we usually associate with mathematics - isn't sufficient in number theory.

 WAV 257K

Few people outside of mathematics are aware of the field's empirical aspect. Much of the mathematics encountered by high-school and college students seems carved in stone, passed on unchanged from one generation to another. Yet even the fundamental principles of arithmetic and plane geometry were once the subjects of debate and speculation. It took centuries of constant questioning. brilliant guesses, and steady refinements to build the edifice now known as mathematics, and the structure continues to evolve. The study of prime numbers is one of the few areas still left in mathematics in which the concepts, questions and experiments are still simple enough to intrigue both amateur and professional mathematicians. In fields such as algebraic topology and differential geometry, usually only the professionals and advanced graduate students experience the thrill of the quest.

The search for patterns and trends plays an important role in the study of the distribution of prime numbers. Clearly, although Euclid proved that the list of primes goes on forever, the stretches between primes, on the average, get longer and longer (see Figure 2.2). The elimination of multiples of every new prime encountered by the sieve of Eratosthenes nicely demonstrates the increasing scarcity of primes among the larger integers.

At the same time, prime numbers appear to be scattered haphazardly throughout the whole numbers. In 1896, French mathematician Jacques Radamard and Belgian Charles de la vallee-Poussin used this idea to find an expression that precisely describes the statistical distribution of primes. The theorem that they independently proved is now known as the prime number theorem. It proposes that the average distance between two consecutive primes near the number n is close to the natural logarithm of n. When n is close to 100, for instance. the natural logarithm of n is approximately 4.6. In that range, every fifth number or so should he a prime.
 Figure 2.2 A computer-generated grid showing primes (white dots) as a spiral of integers from 1 to about 65,000.

But the prime number theorem doesn't eliminate the element of surprise. It doesn't specify exactly where a particular prime falls. That's left to the innumerable tests and experiments that make up the gathering-of-data phase of mathematics research. This data-collection operation now increasingly involves computers, which have extended the list of known primes well beyond the range of hand calculation.

Sometimes, tantalizing pattern fragments show up. The sequence 31, 331, 3331, 33331,  333331, 3333331, 33333331 looks promising: all the numbers in that sequence are primes. Alas, it fails in the next step. The number 333333331 is a composite with factors 17 and 19607843. Such accidental patterns lead nowhere.

Some simple equations can generate a surprising number of primes. The formula x2 + x + 41, for example, produces an unbroken sequence of 40 primes, starting with x=0 (see Figure 2.3). For values of x up to 10,000, the formula produces primes almost half the time. However, beyond 10,000, the proportion of primes inevitably decreases. Another simple "prime-rich" formula", x2 + x + 17, also discovered by the eighteenth-century Swiss mathematician Leonhard Euler, generates primes for all values of x from 0 through 15. However, mathematicians have proved that no polynomial formula has only prime values, so a search for general formulas similar to the ones illustrated is fruitless.

Primes often appear as pairs of consecutive odd integers: 3 and 5; 11 and 13; 41 and 43; 179 and 181; 209,267 and 209,269; and so on. These twins are spread throughout the list of known prime numbers. Statistical evidence suggests that there are infinitely many twin primes, and mathematicians have estimated that in the range close to the number n, the average distance between one pair of twin primes and the next is close to the square of the natural logarithm of n. But no one has yet proved that there is an infinite number of twin primes; it remains one of the major unsolved problems in number theory. Over the last century, numerous mathematicians have attacked the problem in a variety of ways, but all have failed. The optimists believe that it may take another century of determined assaults before anyone succeeds.

At the same time, it's relatively easy to prove that consecutive primes can be as far apart as anyone would want. The sequence of numbers n! + 2, n! +3, n! ..... . n! + n shows this conjecture must be true. The expression n! (read as n factorial) is less a statement of mathematical excitement than a shorthand way of writing the product of all whole numbers from 1 to n. The number n!, where n = 5, for example, has a value of 1 x 2 x 3 x 4 x 5, or 120. In the general case, n! + 2 is evenly divisible by 2, n! + 3 is evenly divisible by 3, and so on. Finally, n! + n is evenly divisible by n. Therefore, all the numbers in the sequence are composite. The sequence can be made arbitrarily long by picking a sufficiently large number n.
 Figure 2.3 The primes between 41 and 439 plotted on a square spiral beginning with 41 in the center.Values along the diagonal satisfy the formula x2 + x + 41

All their suggestive properties indicate that primes are not randomly scattered among the integers, yet prime numbers, in their maddening perversity, defy all attempts aimed at putting them precisely in their places. To try to prove many conjectures about prime numbers, mathematicians therefore often must devise sneaky strategems to get at their prey indirectly. They fence in the unruly conjecture, first staking out a wide swath of territory before gradually closing in on it. The pursuers then draw the net tighter, taking in corners and cutting down boundaries while scrupulously checking for loop- holes. Finally, if all goes well, the conjecture is trapped.

One such attempt is the continuing work on the Goldbach conjecture, which views prime numbers as the building blocks of other numbers. The Prussian mathematician Christian Goldbach suggested the idea in a letter to Euler in 1742. His claim, expressed in modern terms, is that every even number greater than 4 is the sum of two odd primes (that is, primes other than 2). The number 32, for instance, is the sum of 13 and 19. This proposition is now known as the "strong" Goldbach conjecture. The "weak" Goldbach conjecture holds that every odd number greater than 7 can be expressed as the sum of three odd primes. In both cases, the same prime number may be used more than once in a single sum.

Neither conjecture has yet been proved, but over the years, there have been several near misses. In 1937, the Russian mathematician Ivan M. Vinogradov, a leading number theorist, showed that all "sufficiently large" odd numbers can be expressed as the sum of three primes. Although Vinogradov couldn't state explicitly what "large enough" meant, in 1956, his student K. V. Borodzin found that 3315 works as an upper bound. That number has more than 6 million digits. If all odd numbers smaller than 3315 are the sum of three primes, then the weak Goldbach conjecture is proved.

Computer searches have verified both the strong and weak conjectures up to at least a million. Mathematicians have also proved that if the weak conjecture is false, then there are only a finite number of exceptions. Thus the trap is closing in on the weak conjecture, and many mathematicians now regard it as "essentially" proved. The strong version is somewhat more elusive, but in 1966, Chinese mathematician Chen Jing-run showed that all large enough numbers can be expressed as the sum of a prime number and a number that is either prime or the product of two primes. The net tightens.

Despite such successes, some number theorists believe that certain central questions about prime numbers may have no solutions. In 1931, a startled mathematical world had to confront and learn to live with such a possibility, not just in number theory but everywhere in mathematics. Austrian mathematician and logician Kurt Gödel proved that any collection of axioms, such as those underlying euclidean geometry or the theory of infinite sets, leads to a mathematical system containing statements that can be neither proved nor disproved on the basis of those axioms. A theorem, then, can be undecidable: adding more axioms wouldn't help because some theorems would still slip through. Furthermore, Gödel's work implies that in some cases, mathematicians wouldn't even be able to decide whether a theorem can or cannot be proved. Uncertainty strikes in mathematics!

Various guesses about prime numbers, perhaps even the strong Goldbach conjecture, may truly turn out to be undecidable. Few mathematical fields other than number theory have so high a proportion of widely believed but unproved propositions. This doesn't mean that the conjectures are all likely to be false, but it implies that for some conjectures, an airtight case might not exist, despite the steady accumulation of persuasive evidence in its favour. Mathematical proofs require more than just overwhelming evidence.

Even so, the quest isn't hopeless. Near misses and proofs that confirm special cases or parts of conjectures hint that eventually techniques may be developed to handle the problems-although it could take centuries. That is far different from saying that a conjecture can never be proved, for a single breakthrough could put such suppositions as the number of twin primes suddenly within reach. Meanwhile, with the use of computers, specific knowledge about prime numbers is growing steadily, although considering the centuries of effort put in by numerous mathematicians, the theory of prime numbers still seems meagre.