**Uh-oh, it looks like your Internet Explorer is out of date.**

For a better shopping experience, please upgrade now.

Language of Mathematics: Making the Invisible Visible available in Hardcover

- ISBN-10:
- 071673379X
- ISBN-13:
- 9780716733799
- Pub. Date:
- 10/01/1998
- Publisher:
- Freeman, W. H. & Company

# Language of Mathematics: Making the Invisible Visible

## Hardcover

## Overview

###### ADVERTISEMENT

## Product Details

ISBN-13: | 9780716733799 |
---|---|

Publisher: | Freeman, W. H. & Company |

Publication date: | 10/01/1998 |

Pages: | 344 |

Product dimensions: | 6.45(w) x 9.49(h) x 1.16(d) |

## About the Author

**Keith Devlin** is Dean of the School of Science at Saint Mary's College of California and Senior Researcher at Stanford University's center for the Study of Language and Information. A key participant in the six-part PBS television series "Life by the Numbers," he is the author of *Life by Numbers*; *Goodbye, Descartes*; *Logic and Information*; *Mathematics: The New Golden Age*; and *InfoSense: Turning Information into Knowledge*.

Hometown:

Palo Alto, CaliforniaDate of Birth:

March 16, 1947Place of Birth:

Hull, EnglandEducation:

B.S., King's College, London, 1968; Ph.D., University of Bristol, 1971## Read an Excerpt

Chapter One

**Why Numbers Count**

**You can count on them**

Numbers—that is to say, whole numbers—arise from the recognition of patterns in the world around us: the pattern of 'oneness', the pattern of 'twoness', the pattern of 'threeness', and so on. To recognize the pattern that we call 'threeness' is to recognize what it is that a collection of three apples, three children, three footballs, and three rocks have in common. "Can you see a pattern?" a parent might ask a small child, showing her various collections of objects—three apples, three shoes, three gloves, and three toy trucks. The counting numbers 1, 2, 3, ... are a way of capturing and describing those patterns. The patterns captured by numbers are abstract, and so are the numbers used to describe them.

Having arrived at the number concept as an abstraction of certain patterns in the world around us, another pattern arises at once, a mathematical pattern of the numbers. The numbers are ordered 1, 2, 3, ..., each succeeding number being greater by 1 than its predecessor.

There are still deeper patterns of number to be examined by the mathematician, patterns of evenness and oddness, of being prime or composite, of being a perfect square, of satisfying various equations, and so forth. The study of number patterns of this form is known as *number theory*.

**These days, children do it before they're five**

At the age of five or less, the typical child in an educated, Western culture makes a cognitive leap that took humankind many thousands ofyears to achieve: the child acquires the concept of number. He or she comes to realize that there is something common to a collection of, say, five apples, five oranges, five children, five cookies, a rock group of five members, and so on. That common something, 'fiveness', is somehow captured or encapsulated by the number 5, an abstract entity that the child will never see, hear, feel, smell, or taste, but which will have a definite existence for the rest of his or her life. Indeed, such is the role numbers play in everyday life that for most people, the ordinary counting numbers 1, 2, 3, ... are more real, more concrete, and certainly more familiar than Mount Everest or the Taj Mahal.

The conceptual creation of the counting numbers marks the final step in the process of recognizing the *pattern* of 'number of members of a given collection'. This pattern is completely abstract—indeed, so abstract that it is virtually impossible to talk about it except in terms of the abstract numbers themselves. Try explaining what is meant by a collection of twenty-five objects without referring to the *number* 25. (With a very small collection, you can make use of your fingers: a collection of five objects can be explained by holding up the fingers of one hand and saying "This many.")

The acceptance of abstraction does not come easily to the human mind. Given the choice, people prefer the concrete over the abstract. Indeed, work in psychology and anthropology indicates that a facility with abstraction seems to be something we are not born with, but acquire, often with great difficulty, as part of our intellectual development.

For instance, according to the work of cognitive psychologist Jean Piaget, the abstract concept of volume is not innate, but is learned at an early age. Young children are not able to recognize that a tall, thin glass and a short, stout one can contain the same volume of liquid, even if they see the one poured into the other. For a considerable time, they will maintain that the quantity of liquid changes, that the tall glass contains more than the short one.

The concept of abstract number also appears to be learned. Small children seem to acquire this concept after they have learned to count. Evidence that the concept of number is not innate comes from the study of cultures that have evolved in isolation from modern society.

For instance, when a member of the Vedda tribe of Sri Lanka wants to count coconuts, he collects a heap of sticks and assigns one to each coconut. Each time he adds a new stick, he says, "That is one." But if asked to say how many coconuts he possesses, he simply points to the pile of sticks and says, "That many." The tribesman thus has a type of counting system, but far from using abstract numbers, he 'counts' in terms of decidedly concrete sticks.

The Vedda tribesman employs a system of counting that dates back to very early times, that of using one collection of objects—say, sticks or pebbles—to 'count' the members of another collection, by pairing off the sticks or pebbles with the objects to be 'counted'.

**A token advance**

The earliest known human-made artifacts believed to be connected with counting are notched bones, some of which date back to around 35,000 B.C. At least in some cases, these bones seem to have been used as lunar calendars, with each notch representing one sighting of the moon. Similar instances of counting by means of a one-to-one correspondence ap- pear again and again in preliterate societies: pebbles and shells were used in the census in early African kingdoms, and cacao beans and kernels maize, wheat, and rice were used as counters in the New World.

Of course, any such system suffers from an obvious lack of specificity. A collection of notches, pebbles, or shells indicates a quantity, but not the kinds of items being' quantified, and hence cannot serve as a means of storing information for long periods. The first known enumeration system that solved this problem was devised in what is now the Middle East, in the region known as the Fertile Crescent, stretching from present-day Syria to Iran.

During the 1970s and early 1980s, anthropologist Denise Schmandt-Besserat of the University of Texas at Austin carried out a detailed study of clay artifacts found in archaeological digs at various locations in the Middle East. At every site, among the usual assortment of clay pots, bricks, and figurines, Schmandt-Besserat noticed the presence of collections of small, carefully crafted clay shapes, each measuring between and 3 centimeters across: spheres, disks, cones, tetrahedrons, ovoids cylinders, triangles, rectangles, and the like (see Figure 1.1). The earliest such objects dated back to around 8000 B.C., some time after people had started to develop agriculture and would have first needed to plan harvests and lay down stores of grain for later use.

An organized agriculture requires a means of keeping track of a person's stock, and a means to plan and to barter. The clay shapes examined by Schmandt-Besserat appear to have been developed to fulfill this role, with the various shapes being used as tokens to represent the kind of object being counted. For example, there is evidence that a cylinder stood for an animal, cones and spheres stood for two common measures of grain (approximately a peck and a bushel, respectively), and a circular disk stood for a flock. In addition to providing a convenient, physical record of a person's holdings, the clay shapes could be used in planning and bartering, by means of physical manipulation of the tokens.

By 6000 B.C., the use of clay tokens had spread throughout the region. The nature of the clay tokens remained largely unchanged until around 3000 B.C., when the increasingly more complex societal structure of the Sumerians—characterized by the growth of cities, the rise of the Sumerian temple institution, and the development of organized government—led to the development of more elaborate forms of tokens. These newer tokens had a greater variety of shapes, including rhomboids, bent coils, and parabolas, and were imprinted .with markings. Whereas the plain tokens continued to be used for agricultural accounting, these more complex tokens appear to have been introduced to represent manufactured objects such as garments, metalworks, jars of oil, and loaves of bread.

The stage was set for the next major step toward the development of abstract numbers. During the period 3300 to 3250 B.C., as state bureaucracy grew, two means of storing clay tokens became common. The more elaborate, marked tokens were perforated and strung together on a string attached to an oblong clay frame, and the frame was marked to indicate the identity of the account in question. The plain tokens were stored in clay containers, hollow balls some 5 to 7 centimeters in diameter, and the containers were marked to show the account. Both the strings of tokens and the sealed clay envelopes of tokens thus served as accounts or contracts.

Of course, one obvious drawback of a sealed clay envelope is that the seal has to be broken open in order to examine the contents. So Sumerian accountants developed the practice of impressing the tokens on the soft exteriors of the envelopes before enclosing them, thereby leaving a visible exterior record of the contents.

But with the contents of the envelope recorded on the exterior, the tokens themselves became largely superfluous: all the requisite information was stored in the envelope's outer markings. The tokens themselves could be discarded, which is precisely what happened after a few generations. The result was the birth of the clay tablet, on which impressed marks, and those marks alone, served to record the data previously represented by the tokens. In present-day terminology, we would say that the Sumerian accountants had replaced the physical counting devices with written *numerals*.

From a cognitive viewpoint, it is interesting that the Sumerians did not immediately advance from using physical tokens sealed in a marked envelope to using markings on a single tablet. For some time, the marked clay envelopes redundantly contained the actual tokens depicted by their outer markings. The tokens were regarded as representing the quantity of grain, the number of sheep, or whatever; the envelope's outer markings were regarded as representing not the real-world quantity, but the tokens in the envelope. That it took so long to recognize the redundancy of the tokens suggests that going from physical tokens to an abstract representation was a considerable cognitive development.

Of course, the adoption of a symbolic representation of an amount of grain does not in itself amount to the explicit recognition of the number concept in the sense familiar today, in which numbers are regarded as 'things', as 'abstract objects'. Exactly when humankind achieved that feat is hard to say, just as it is not easy to pinpoint the moment when a small child makes a similar cognitive advance. What is certain is that, once the clay tokens had been abandoned, the functioning of Sumerian society relied on the notions of 'oneness', 'twoness', 'threeness', and so on, since that is what the markings on their tablets denoted.

**Symbolic progress**

Having some kind of written numbering system, and using that system to count, as the Sumerians did, is one thing; recognizing a concept of number and investigating the properties of numbers—developing a *science* of numbers—is quite another. This latter development came much later, when people first began to carry out intellectual investigations of the kind that we would now classify as science.

As an illustration of the distinction between the *use* of a mathematical device and the explicit recognition of the entities involved in that device, take the familiar observation that order is not important when a pair of counting numbers are added or multiplied. (From now on I shall generally refer to counting numbers by the present-day term *natural numbers*.) Using modern algebraic terminology, this principle can be expressed in a simple, readable fashion by the two commutative laws:

*m* + *n* = *n* + *m*, *m* x *n* = *n* x *m.*

In each of these two identities, the symbols *m* and *n* are intended to denote *any* two natural numbers. Using these symbols is quite different from writing down a particular instance of these laws, for example:

3 + 8 = 8 + 3, 3 x 8 = 8 x 3.

The second case is an observation about the addition and multiplication of two particular numbers. It requires our having the ability to handle individual abstract numbers, at the very least the abstract numbers 3 and 8, and is typical of the kind of observation that was made by the early Egyptians and Babylonians. But it does not require a well-developed *concept* of abstract number, as do the commutative laws.

By around 2000 B.C., both the Egyptians and the Babylonians had developed primitive numeral systems and made various geometric observations concerning triangles, pyramids, and the like. Certainly they 'knew' that addition and multiplication were commutative, in the sense that they were familiar with these two patterns of behavior, and undoubtedly made frequent use of commutativity in their daily calculations. But in their writings, when describing how to perform a particular kind of computation, they did not use algebraic symbols such as *m* and *n*. Instead, they always referred to *particular* numbers, although it is clear that in many cases the particular numbers chosen were presented purely as examples, and could be freely replaced by any other numbers.

For example, in the so-called Moscow Papyrus, an Egyptian document written in 1850 B.C., appear the following instructions for computing the volume of a certain truncated square pyramid (one with its top chopped off by a plane parallel to the base—see Figure 1.2):

If you are told: a truncated pyramid of 6 for the vertical height by 4 on the base by 2 on the top. You are to square this 4, result 16. You are to double 4, result 8. You are to square 2, result 4. You are to add the 16, the 8, and the 4, result 28. You are to take a third of 6, result 2. You are to take 28 twice, result 56. See, it is 56. You will find it right.

Though these instructions are given in terms of particular dimensions, they clearly make sense as a set of instructions only if the reader is free to replace these numbers with any other appropriate values. In modern notation, the result would be expressed by means of an algebraic formula: if the truncated pyramid has a base of sides equal to *a*, a top of sides equal to *b*, and a height *h*, then its volume is given by the formula

V = 1/3*h*(*a*² + *ab* + *b*²).

Being aware of, and utilizing, a certain pattern is not the same as formalizing that pattern and subjecting it to a scientific analysis. The commutative laws, for example, express certain patterns in the way the natural numbers behave under addition and multiplication, and moreover, they express these patterns in an explicit fashion. By formulating the laws using algebraic indeterminates such as *m* and *n*, entities that denote *arbitrary* natural numbers, we place the focus very definitely on the pattern, not the addition or the multiplication itself.

The general concept of abstract number was not recognized, nor were behavioral rules such as those concerning addition and multiplication formulated, until the era of Greek mathematics began around 600 B.C.

**For a long time it was all Greek**

It is not possible to say exactly when abstract mathematics first appeared, but if a time and place had to be set, it would most likely be the sixth century B.C. in Greece, when Thales of Miletus carried out his investigations of geometry. Thales' travels as a merchant undoubtedly exposed him to the known geometric ideas involved in measurement, but it was apparently not until his own contributions that any attempt was made to regard those geometric ideas as a subject for systematic investigation in their own right,

Thales took known observations such as:

*A circle is bisected by any of its diameters. *

* The sides of similar triangles are in proportion.*

and showed how to deduce them from other, supposedly more 'basic', observations concerning the nature of length and area. The idea of mathematical proof thereby introduced was to become the bedrock of much of mathematics to follow.

One of the most famous early adherents to the concept of mathematical proof was the Greek scholar Pythagoras, who lived sometime around 570 to 500 B.C. Few details of his life are known, since both he and his followers shrouded themselves in mystery, regarding their mathematical studies as something of a black art. He is believed to have been born between 580 and 560 B.C. on the Aegean island of Samos, and to have studied in both Egypt and Babylonia. After several years of wandering, he appears to have settled in Croton, a prosperous Greek settlement in southern Italy. The school he founded there concentrated on the study of *arithmetica* (number theory), *harmonia* (music), *geometria* (geometry), and *astrologia* (astronomy), a fourfold division of knowledge that in the Middle Ages became known as the *quadrivium*. Together with the *trivium* of logic, grammar, and rhetoric, the *quadrivium* made up the seven 'liberal arts' that were regarded as constituting a necessary course of study for an educated person.

Mixed up with the Pythagoreans' philosophical speculations and mystical numerology was some genuinely rigorous mathematics, including the famous Pythagorean theorem. Illustrated in Figure 1.3, the theorem states that for any right-angled triangle, the square of the length of the hypotenuse is equal to the sum of the squares of the lengths of the other two sides. This theorem is remarkable on two counts. First, the Pythagoreans were able to discern the relationship between the squares of the sides, observing that there was a regular pattern that was exhibited by *all* right-angled triangles. Second, they were able to come up with a rigorous proof that the pattern they had observed did indeed hold for all such triangles.

The abstract patterns of principal interest to the Greek mathematicians were geometric ones—patterns of shape, angle, length, and area. Indeed, apart from the natural numbers, the Greek notion of number was essentially based on geometry, with numbers being thought of as measurements of length and area. All their results concerning angles, lengths, and areas—results that would nowadays be expressed in terms of whole numbers and fractions—were given by the Greeks in the form of comparisons of one angle, length, or area with another. It was this concentration on *ratios* that gave rise to the modern term *rational number* for a number that can be expressed as the quotient of one whole number by another.

The Greeks discovered various algebraic identities familiar to present-day students of mathematics, such as:

(*a* + *b*)² = *a*² + 2*ab* + *b*²,

(*a* - *b*)² = *a*² - 2*ab* + *b*².

Again, these were thought of in geometric terms, as observations about adding and subtracting areas. For example, in Euclid's *Elements* (of which more follows), the first of these algebraic identities is stated as follows:

Proposition II.4. If a straight line be cut at random, the square on the whole is equal to the squares on the segments and twice the rectangle contained by the segments.

This proposition is illustrated by the left-hand diagram in Figure 1.4.

In the diagram, the area of the large square = (*a* + *b*)² = the area of square *A* plus the area of square *B* plus the area of rectangle C plus the area of rectangle *D* = *a*² + *b*² + *ab + ab* = *a*² + 2*ab* + *b*². The second identity is derived from the diagram on the right in Figure 1.4, in which the sides are labeled differently. In this figure, the area of square *A* = (*a* - *b*)² = the area of the large square minus the area of the rectangle comprising regions *C* and *B* minus the area of rectangles comprising *D* and *B* plus the area of square *B* (added on since this area has been subtracted twice, once as part of each rectangle) = *a*² - *ab* - *ab* + *b*².

Incidentally, the Greek number system did not include negative numbers. Indeed, negative numbers did not come into widespread use until as recently as the eighteenth century.

The Pythagorean theorem can nowadays be expressed by means of the algebraic identity

*h*² = *a*² + *b*²,

where *h* is the length of the hypotenuse of a given right-angled triangle and *a, b* are the lengths of the other two sides. The Greeks, however, understood and proved the theorem in purely geometric terms, as a result about the areas of square figures drawn along the three sides of a given triangle, as illustrated in Figure 1.5.

**A fatal flaw is discovered**

In formulating their results as comparisons of figures, the Greeks were making an assumption that turned out to be far less innocuous than it must have appeared. In modern terminology, they were assuming that any length or area is rational. The eventual discovery that this particular belief was mistaken came as an immense shock from which Greek mathematics never fully recovered.

The discovery is generally credited to a young mathematician in the Pythagorean school by the name of Hippasus. He showed that the diagonal of a square cannot be compared to the length of its sides—in modern terminology, the diagonal of a square having rational sides does not have a rational length. Ironically, the proof depends on the Pythagorean theorem.

Suppose that a square has sides 1 unit in length; then, by the Pythagorean theorem, the diagonal has length [square root of 2] (the square root of 2). But, by means of a fairly simple, and extremely elegant, piece of logical reasoning, it can be demonstrated that there are no whole numbers *p* and *q* for which *p/q* is equal to [square root of 2]. The number [square root of 2] is what mathematicians nowadays refer to as an *irrational number*. Here is the simple, yet elegant, proof.

Start out by supposing that, contrary to what I said above, there were natural numbers *p* and *q* for which *p/q* = [square root of 2]. If *p* and *q* have any common factors, we can cancel them out, so we may as well assume this has already been done, and that *p* and *q* have no common factors.

Squaring the identity [square root of 2] = *p/q* gives 2 = *p*²/ *q*², which rearranges to give *p*² = 2*q*². This equation tells us that *p*² is an even number. Now, the square of any even number is even, and the square of any odd number is odd. So, as *p*² is even, it must be the case that *p* is even. Consequently, *p* is of the form *p* = 2*r*, for some natural number *r*. Substituting *p* = 2*r* into the identity *p*² = 2*q*² gives 4*r*² = 2*q*², which simplifies to 2*r*² = *q*². This equation tells us that *q*² is an even number. It follows, as in the case of *p*, that *q* is itself even.

But now we have shown that both *p* and *q* are even, which is contrary our assumption at the start that *p* and *q* have no common factors. This contradiction implies that our original assumption that such natural numbers as *p* and *q* exist must have been false. In other words, there are no such *p* and *q*.

And that's the proof!

Such is the power of proof in mathematics that there was no question of ignoring the new result, even though some popular accounts maintain that Hippasus was thrown from a ship and drowned in order to prevent the terrible news from breaking out.

Unfortunately, instead of provoking a search for a system of numbers richer than the rationals—a step that was to come only much later in history, with the development of the 'real numbers'—Hippasus' discovery was regarded as a fundamental impasse. From then on, the Greeks tended to regard the study of number as distinct from the study of geometry, and their most impressive discoveries about numbers were largely concerned not with measurements of length or area, but with the natural numbers. The first systematic investigation of the natural numbers is generally identified with Euclid, who lived sometime in the period from 350 to 300 B.C.

**Here's looking at Euclid**

In between the time of Thales and Pythagoras and the arrival of Euclid on the scene, Greek mathematics made considerable advances with the work of Socrates, Plato, Aristotle, and Eudoxus. It was at the Athens Academy, founded by Plato, that Eudoxus worked. There he developed, among other things, a 'theory of proportions' that enabled the Greeks to circumvent, in part, some of the problems created by Hippasus' discovery. Euclid, too, is reputed to have studied at Plato's Academy before settling in the new intellectual center of Alexandria, sometime around 330 B.C.

While working in Alexandria at the great Library, the forerunner of today's universities, Euclid produced his mammoth, thirteen-volume work *Elements*. It was a compendium of practically all of Greek mathematics up to the time, containing some 465 propositions from plane and solid geometry and from number theory. Though some of the results were Euclid's own, for the most part his great contribution was the systematic manner in which the mathematics was presented.

Over the centuries since it was written, more than two thousand editions of *Elements* have been published, and though it contains a number of logical flaws, it remains an excellent example of what we call the mathematical method, in which we commence with a precise statement of the basic assumptions and thereafter accept as facts only those results proved from those assumptions.

Books I to VI of *Elements* concentrate on plane geometry and Books XI to XIII deal with solid geometry, both of which are covered in Chapter 4 of this book. Book X presents an investigation of so-called 'incommensurable magnitudes'. Translated into modern terminology, this volume would be a study of the irrational numbers. It is in Books VII to IX that Euclid presents his treatment of what is now known as number theory, the study of the natural numbers. An obvious pattern exhibited by the natural numbers is that they are ordered one after the other. Number theory examines deeper mathematical patterns found in the natural numbers.

**Numbers in prime condition**

Euclid begins Book VII of *Elements* with a list of some twenty-two basic definitions, among which are the following: An *even* number is one that is divisible into two equal whole-number parts, and an *odd* number is one that is not. Somewhat more significantly, a *prime* number is (in modern terminology) one that has no whole-number divisors other than 1 and the number itself. For example, among the numbers 1 to 20, the numbers 2, 3, 5, 7, 11, 13, 17, and 19 are primes. A number greater than 1 that is not prime is said to be *composite*. Thus, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, and 20 are the composite numbers in the range 1 to 20.

Among the fundamental results Euclid proved about the primes are the following:

* If a prime numberpdivides a productmn, thenpdivides at least one of the two numbersm, n.

* Every natural number is either prime or else can be expressed as a product of primes in a way that is unique apart from the order in which they are written.

* There are infinitely many primes.

The second of these results is of such importance that it is generally referred to as the *fundamental theorem of arithmetic*. Taken together, the first two results tell us that the primes are very much like the physicist's atoms, in that they are the fundamental building blocks out of which all other natural numbers can be built, in this case through the process of multiplication. For example:

328,152 = 2 x 2 x 2 x 3 x 11 x 11 x 113.

Each of the numbers 2, 3, 11, 113 is prime; they are called the *prime factors* of 328,152. The product 2 x 2 x 2 x 3 x 11 x 11 x 113 is called the *prime decomposition* of 328,152. As with atomic structure, a knowledge of the prime decomposition of a given number can enable the mathematician to say a great deal about the mathematical properties of that number.

The third result, the infinitude of the primes, might come as a surprise to anyone who has spent time enumerating prime numbers. Though primes seem to be in great abundance among the first hundred or so natural numbers, they start to thin out as you proceed up through the numbers, and it is not at all clear from the observational evidence whether or not they eventually peter out altogether. For instance, there are eight primes between 2 and 20, but only four between 102 and 120. Going further, of the hundred numbers between 2,101 and 2,200, only ten are prime, and of the hundred between 10,000,001 and 10,000,100, only two are prime.

**Prime order**

One way to get a precise sense of how the primes thin out is to look at what is called the *prime density function*, which gives the proportion of numbers below a given number that are primes. To obtain the prime density for a given number *N*, you take the number of primes less than *N*, call it π(*N*), and divide it by *N*. In the case of *N* = 100, for example, the answer is 0.168, which tells you that about 1 in 6 of the numbers below 100 are primes. For *N* = 1,000,000, however, the proportion drops to 0.078, which is about 1 in 13, and for *N* = 100,000,000 it is 0.058, or about 1 in 17. As *N* increases, this fall continues.

N | π(N) | π(N)/N |
---|---|---|

1,000 | 168 | 0.168 |

10,000 | 1,229 | 0.123 |

100,000 | 9,592 | 0.095 |

1,000,000 | 78,498 | 0.078 |

10,000,000 | 664,5790 | 0.066 |

100,000,000 | 5,761,455 | 0.058 |

But for all of this steady fall in the ratio π*(N)/N*, the primes never peter out completely. Euclid's proof of this fact remains to this day a marvelous example of logical elegance. Here it is.

The idea is to demonstrate that if you start to list the primes as a sequence *p*_{1}, *p*_{2}, *p*_{3}, ..., this list continues forever. To prove this, you show that if you have listed all the primes up to some prime [*p*.sub.n], then you can always find another prime to add to the list: the list never stops.

Euclid's ingenious idea was to look at the number

*P* = *p*_{1} x *p*_{2} x ... x *p*_{n} + 1,

where *p*_{1}, ..., *p*_{n} are all the primes enumerated so far. If *P* happens to be prime, then *P* is a prime bigger than all the primes *p*_{1}, ..., *p*_{n}, so the list may be continued. (*P* might not be the *next* prime after *p*_{n}, in which case you will not take *P* to be *p*_{n+1}. But if *P* is prime, then you know for sure that *there is* a next prime beyond *p*_{n}.)

On the other hand, if *P* is not prime, then *P* must be evenly divisible by a prime. But none of the primes *p*_{1}, ..., *p*_{n} divides *P*; if you try to carry out such a division, you will end up with a remainder of 1—that '1' that was added on to give *P* in the first place. So, if *P* is not prime, it must be evenly divisible by some prime different from (and hence bigger than) all of *p*_{1}, ..., *p*_{n}. In particular, there *must be* a prime bigger than all of *p*_{1}, ..., *p*_{n}, so again, the sequence can be continued.

It is interesting to observe that, when you look at the number

*P* = *p*_{1} x *p*_{2} x ... x *p*_{n} + 1

used in Euclid's proof, you don't actually know whether *P* is itself prime or not. The proof uses two arguments, one that works when *P* is prime, one that works when it is not. An obvious question to ask is whether it is always one or the other.

The first few values of *P* look like this:

*P*_{1} = 2 + 1 = 3

*P*_{2} = 2 x 3 + 1 = 7

*P*_{3} = 2 x 3 x 5 + 1 = 31

*P*_{4} = 2 x 3 x 5 x 7 + 1 = 211

*P*_{5} = 2 x 3 x 5 x 7 x 11 + 1 = 2,311

These are all prime numbers. But the next three values are not prime:

*P*_{6} = 59 x 509

*P*_{7} = 19 x 97 x 277

*P*_{8} = 347 x 27,953

It is not known whether the number *P _{n}* is prime for infinitely many values of

*n*. Nor is it known if infinitely many of the numbers P

_{n}are composite. (Of course, at least one of these two alternatives must be true. Most mathematicians would guess that both are in fact true.)

Returning to the prime density function π*(N)/N*, one obvious question is whether there is a *pattern* to the way the density decreases as *N* gets bigger.

There is certainly no simple pattern. No matter how high up through the numbers you go, you keep finding groups of two or more primes clustered closely together, as well as long stretches that are barren of primes altogether. Moreover, these clusters and barren regions seem to occur in a random fashion.

In fact, the distribution of primes is not completely chaotic. But nothing was known for certain until well into the nineteenth century. In 1850, the Russian mathematician Pafnuti Chebychef managed to prove that between any number *N* and its double 2*N*, you can always find at least one prime. So there is *some* order to the way the primes are distributed.

As it turns out, there is considerable order, but you have to look hard to find it. In 1896, the French mathematicians Jacques Hadamard and Charles de la Vallée Poussin independently proved the remarkable result that, as *N* gets bigger, the prime density π*(N)/N* gets closer and closer to the quantity 1/ln*N* (where 1n is the natural logarithm function, discussed in Chapter 3). This result is nowadays referred to as the *prime number theorem*. It provides a remarkable connection between the natural numbers, which are the fundamental fabric of counting and arithmetic, and the natural logarithm function, which has to do with real numbers and calculus (see Chapter 3).

Over a century before it was proved, the prime number theorem had been suspected by the fourteen-year-old mathematical child prodigy Karl Friedrich Gauss. So great were Gauss's achievements that he deserves an entire section all to himself.

**The child genius**

Born in Brunswick, Germany, in 1777, Karl Friedrich Gauss (Figure 1.6) displayed immense mathematical talent from a very early age. Stories tell of him being able to maintain his father's business accounts at age three. In elementary school, he confounded his teacher by observing a pattern that enabled him to avoid a decidedly tedious calculation.

Gauss's teacher had asked the class to add together all the numbers from 1 to 100. Presumably the teacher's aim was to keep the students occupied for a time while he was engaged in something else. Unfortunately for the teacher, Gauss quickly spotted the following shortcut to the solution.

You write down the sum twice, once in ascending order, then in descending order, like this:

1 + 2 + 3 + ... + 98 + 99 + 100

100 + 99 + 98 + ... + 3 + 2 + 1

Now you add the two sums, column by column, to give

101 + 101 + 101 + ... + 101 + 101 + 101

There are exactly 100 copies of the number 101 in this sum, so its value is 100 x 101 = 10,100. Since this product represents twice the answer to the original sum, if you halve it, you obtain the answer Gauss's teacher was looking for, namely, 5,050.

Gauss's trick works for any number *n*, not just 100. In the general case, when you write the sum from 1 to *n* in both ascending and descending order and then add the two sums column by column, you end up with *n* copies of the number *n* + 1, which is a total of *n*(*n* + 1). Halving this total gives the answer:

1 + 2 + 3 + ... + *n* = *n*(*n* + 1)/2.

This formula gives the general pattern of which Gauss's observation was a special case.

It is interesting to note that the formula on the right-hand side of the above identity also captures a geometric pattern. Numbers of the form *n*(*n* + 1)/2 are called *triangular numbers*, since they are exactly the numbers you can obtain by arranging dots in an equilateral triangle. The first five triangular numbers, 1, 3, 6, 10, 15, are shown in Figure 1.7.

*(Continues...)*