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