Read an Excerpt
Fundamentals of Number Theory
By William J. LeVeque Dover Publications, Inc.
Copyright © 1977 William J. LeVeque
All rights reserved.
ISBN: 978-0-486-14150-3
CHAPTER 1
Introduction
1.1 WHAT IS NUMBER THEORY?
This could serve as a first attempt at a definition: it is the study of the set of integers 0, ±1, ±2, ..., or some of its subsets or extensions, proceeding on the assumption that integers are interesting objects in and of themselves, and disregarding their utilitarian role in measuring. This definition might seem to include elementary arithmetic, and in fact it does, except that the concern now is to be with more advanced and more subtle aspects of the subject. A quick review of elementary properties of the integers is incorporated with some other material, which may or may not be new to the reader, in Sections 1.2 and 1.3.
To get some idea of what the subject comprises, let us go back to the seventeenth century, when the modern epoch opened with the work of Pierre de Fermat [fairmati]. One of Fermat's most beautiful theorems is that every positive integer can be represented as the sum of the squares of four integers, for example,
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].
He announced this theorem in 1636, but the first published proof of it was given by Joseph-Louis Lagrange in 1770. It could serve as the ideal example of a theorem in number theory: it is elegant and immediately comprehensible; it reveals a subtle and unexpected relationship among the integers; it is the best theorem of its kind (7 cannot be represented with fewer than four squares); and it says something about an infinite class of integers. The last is an important qualification, as it distinguishes between theorems and numerical facts. It is a fact, and perhaps even an interesting one, that 1729 is the smallest positive integer having two distinct representations as the sum of two cubes (103 + 93 and 123 + 13), but this would hardly be called a theorem since it can be verified by examining the finite set 1, 2, 3, ..., 1729. On the other hand, the assertion that there are only finitely many integers having two or more such representations is deceptive; it seems to say something about a finite set, but in fact it cannot be proved by examining any specific finite set, nor can it be disproved in this way. Thus it would be a significant theorem if it were true. (It is not; that, too, is a significant theorem.)
Pierre de Fermat (1601–65)
Fermat was a lawyer by profession, well versed in ancient languages and steeped in classical culture. There were no scientific journals then, and he was not inclined to write out proofs. Instead, he communicated his results by letter, especially to Father M. Mersenne, who maintained an enormous correspondence throughout Europe. Fermat anticipated Descartes in analytic geometry and Newton and Leibniz in differential calculus, but his work was not well known because he failed to publish his books on these subjects. His fame rests chiefly on his work in number theory, where he was without peer. The groundwork that had been laid for him by the Greeks and others is discussed in the final section of this chapter.
An even more famous assertion credited to Fermat is what is sometimes called his Last Theorem, which says that if n is an integer larger than 2, then the equation xn + yn = zn has no solution in positive integers x, y, z. Fermat claimed to have proved this, but as was his habit he did not reveal the proof. This seems to be the only recorded instance in which he claimed a result that has never been verified (although he did announce an erroneous conjecture, discussed below). Lacking a proof, mathematicians today tend to call it the Fermat Problem, rather than Theorem; it is the oldest, and possibly the most famous, unsolved problem in mathematics. A single counterexample would suffice to destroy it, of course, but finding such a quadruple x, y, z, n, if there is one, might well be beyond the capacity of present or future computers, since the equation is now known to have no solution for n< 100,000, and in any case to have only solutions with one of x, y, or z larger than n2n. (The known universe would accommodate only about 10123 proton-sized objects, close-packed.)
One of the basic concepts in number theory is that of a prime number. An integer p is prime if p ≠ ±1 and the equation p = ab has no solution in integers a and b except those for which a = ±1 or a = ±p. Briefly, then, a prime is an integer ≠ ±1 which has no nontrivial divisors. Euclid already knew that the sequence of positive primes 2, 3, 5, 7, ... does not terminate (his proof is given in Section 1.3), but the pattern of occurrence is very irregular. Both Fermat and Mersenne looked for some regularity, and both guessed wrong. Fermat conjectured that all the numbers fn = 22n + 1 are prime, this being true for n = 0, 1, 2, 3, 4. It turned out that he had stopped just too soon, for Leonhard Euler [oiler] showed in 1739 that f5 has the divisor 641. In fact, no further prime value of fn has been found, for 5 ≤ n ≤ 16. This story would hardly be worth recounting, since false conjectures about the primes are very common, if it were not for the fact that the Fermat primes occurred again, almost 200 years later, in an entirely different context: Carl Friedrich Gauss settled one of the ancient Greek problems by proving that a regular polygon of m sides can be constructed with ruler and compass if and only if m factors as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where k, n1, ..., nr are some nonnegative integers and the [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are distinct Fermat primes. Thus it would be interesting to know whether there are further primes of this sort.
Although Mersenne's chief contribution to mathematics was in the dissemination of, rather than in the creation of, new results, he did himself engage in the study of primes among the numbers of the form Mn = 2n - 1. If n = rs, then Mn is divisible by Mr and Ms, so Mn can be prime only for prime values of n. In 1644 Mersenne asserted that of the 55 numbers Mp with prime index p ≤ 257, those which are prime correspond to p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, and 257. He thereby made five mistakes, by including 67 and 257 and by excluding 61, 89, and 107. What was remarkable was not that he made some mistakes but that, without even a desk calculator, he could do anything at all with numbers having up to 78 digits. We are again dealing with numerical facts and not theorems, but it must be obvious that some theorems are lurking in the background, of the form "N is prime if ..." or "N is not prime if ...", and that additional theorems of this sort would be useful. There has always been a strong interplay between facts and theorems in number theory; calculations provide the data from which to infer patterns, find counterexamples or guess at theorems, and they also bring into focus the need for constructive theorems which yield usable algorithms (i.e., systematic procedures for computations).
Carl Friedrich Gauss (1777–1855)
Gauss is considered by many to be the greatest mathematician who ever lived. He conjectured the prime number theorem when he was 15, characterized the constructible polygons at 18, proved at age 22 that a polynomial of degree n has n zeros, and published his masterpiece Disquisitiones Arithmeticae when he was 24. This book changed number theory from a collection of isolated problems to a coherent branch of mathematics. After 1801 he turned to other fields—geometry, analysis, astronomy, and physics, chiefly—except for two articles on biquadratic reciprocity. He spent his entire mature life at the University of Gottingen. His collected works fill 12 volumes.
The Fermat and Mersenne numbers are so sparse that even if they were all prime, one would know very little about the distribution of primes in general. A much more fruitful study, again empirical, was initiated by Gauss in 1792 with the help of a table of the primes less than 102,000, published by Johann Lambert a few years before. If, as is customary, π(x) denotes the number of positive primes not exceeding x, then what Gauss did was to consider how π(x) grows with x. He began by counting the primes in successive intervals of fixed length, obtaining a table of the following sort, in which Δ(x) = {π(x) - π(x 1000)}/1000:
[TABLE OMITTED]
The "frequency" Δ(x) of primes in successive intervals seemed to be slowly decreasing, on the average, so Gauss took the reciprocal of Δ(x) and compared it with various elementary functions. For the natural logarithm of x, this gives the following chart:
[TABLE OMITTED]
The strikingly good match strongly supports the guess that Δ(x) is approximately 1/log x. Since Δ(x) is the slope of a chord on the graph of y = π(x), the hypothetical approximate equality Δ(x) ≈ 1/log x should be integrated to obtain π(x) itself, and thus Gauss conjectured that
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
The integral occurring here, which happens not to be an elementary function, is commonly denoted by li(x); its values are readily calculated, and more recent calculations for π(x) yield the following comparison (where li(x) is given to the nearest integer):
[TABLE OMITTED]
What Gauss intended, then, in conjecturing that li(x) is a good approximation to π(x) for large x, was presumably not that li(x) - π(x) -> 0, nor even that
li(x) - π(x)
remains bounded, but that the relative error becomes small:
(li(x) - π(x))/π(x) -> 0,
or
(1) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].
He made this conjecture in 1793, when he was about 15 years old, but it was not proved until more than 100 years later, by J. Hadamard and C. de la Vallée Poussin (independently, in 1896). The proof is too difficult to include in this book, but it will be shown later that if the limit in (1) exists, it must have the value 1. It is not difficult to show that (1) implies and is implied by the relation
(1') [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],
as is indicated in Problem 2 at the end of this section. Because of its central position in the theory of primes, relation (1), or more traditionally (1'), is simply known as the prime number theorem.
One reason for including data in the last table above for such large values of x, for which Gauss had not computed π(x), is to emphasize the point that no amount of numerical evidence will substitute for a proof. It appears from the table that li(x) always overestimates π (x), in the sense that up to x = 1010 at least, li(x) -π(x) is positive and increasing. But this does not continue, for Littlewood [1914] has shown that li(x) - π(x) changes sign infinitely many times. No one knows when the first change of sign occurs, but Skewes [1955] proved that it happens for some x such that
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
Quite possibly, no specific value of x will ever be known for which li(x) < π(x).
There are many questions concerning primes which have resisted all assaults for two centuries and more, for example, whether there are infinitely many twin primes such as 17 and 19, or 4967 and 4969, which differ by 2, and whether every even integer larger than 4 is the sum of two odd primes. Here, for variety, is a less well-known question that was raised much more recently, and which also seems to be very difficult. Form the doubly-infinite array
[ILLUSTRATION OMITTED]
in which the first row contains the primes and each entry below is the absolute value of the difference of the two numbers above it. Is it the case that every row after the first begins with 1? The portion of the array exhibited above shows that this is true up to p = 43, and it has been verified up to p = 792, 721.
There are branches of number theory in which the integers enter much less explicitly than in the theory of primes. This is the case, for example, in questions concerning the nature of numbers such as π and e. The question of whether either of these is rational is simply the question of whether either is a solution of (that is, is defined implicitly by) a linear equation ax + b = 0 with integral coefficients a and b. The Swiss mathematician Lambert, mentioned earlier, proved in 1761 that π is not rational, and we give in Section 1.3 the much simpler proof that e is irrational. More generally, one could ask whether e or π is algebraic, that is, whether either of them satisfies a polynomial equation a0xn + a1xn - 1 + ··· + an = 0 with integral coefficients a0 ≠ 0, a1, ..., an. Again the answer turns out to be "no" in both cases, but the proofs are rather more difficult (see Section 9.7). Turning the matter around, one can study the numbers that are algebraic, and it turns out that a very elaborate theory can be constructed which is interesting in its own right and which also provides some powerful tools for the study of the integers. Too many definitions intervene to allow for examples at this point, but the interested reader may look ahead to Chapter 8.
Johann H. Lambert (1728–1777)
Lambert's family was poor, so he had to leave school at age 12, and had no further schooling. Nevertheless, he made important contributions in philosophy (epistemology and metaphysics), astronomy (existence of nebulae), physics (photometry, hygrometry and pyrometry) and cartography. In mathematics, his major work outside number theory was in geometry, where his books on the parallel postulate and on perspective foreshadowed nineteenth-century developments in noneuclidean geometry and descriptive geometry. He held a scientific position, as a colleague of Euler in the Prussian Academy of Sciences in Berlin, only during the last twelve years of his life. Earlier, he had mainly been a children's tutor in his native Switzerland.
PROBLEMS
1. Show that if n = rs, then Mr divides Mn. Why could Fermat restrict attention to the numbers fn rather than considering the more general class of numbers 2k + 1, in hunting for primes?
2. Apply l'Hôpital's rule to show that
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],
and deduce that each of (1) and (1') implies the other.
3. Making use of a logarithm table, compare li(x) and x /log x as approximations to π(x) for x = 10n, 3 ≤ n ≤ 10. What do you conclude from this?
4. For each positive integer n, let τ(n) be the number of positive integers which divide n. (For example, τ(6) = 4, since the positive divisors of 6 are 1, 2, 3, and 6.) Construct a table of values of τ(n) for 1 ≤ n ≤ 50, formulate some conjectures, and test them for other suitable values of n. In particular, can you characterize the n for which τ(n) is odd? Can you prove it? Can you find a connection between τ(m), τ(n), and τ(mn)? [Note: The Greek alphabet is to be found at the end of the book.]
1.2 ALGEBRAIC PROPERTIES OF THE SET OF INTEGERS
In this section we organize familiar arithmetic facts with the aid of three central concepts from abstract algebra, the notions of group, ring, and field. For brevity, we henceforth use Z as the name of the set of all integers, 0, ±1, ±2, ..., and Z+ for the set of positive integers, 1, 2, 3, .... As usual, the symbol "[member of]" means "belongs to, is an element of."
Let S be a set of finitely or infinitely many elements, and suppose that any two elements a and b can be combined by an operation "[??]" (think of addition or multiplication) to give a unique result, a [??] b. Then S is called a group (under the operation) if the following four conditions are satisfied:
1. If a [member of] S and b [member of] S, then a [??] b [member of] S (in words, S is closed under the operation).
2. If a, b, c [member of] S, then a [??] (b [??] c) = (a [??] b) [??] c (the associative law holds).
3. There is a unique element e [member of] S (the identity element) such that for all a [member of] S, a [??] e = e [??] a = a.
4. Each a [member of] S has an inversea-1 [member of] S such that a [??] a-1 = a-1 [??] a = e.
(Continues...)
Excerpted from Fundamentals of Number Theory by William J. LeVeque. Copyright © 1977 William J. LeVeque. Excerpted by permission of Dover Publications, Inc..
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.
