Pages: 5

Carl Friedrich Gauss, whom many people consider the greatest mathematician who ever lived, once described number theory as the “Queen of Mathematics”. Indeed, the integers (“whole numbers”), and the patterns they exhibit, have been the subject of fascination and study for literally thousands of years. Fermat’s Last Theorem and Hilbert’s Tenth Problem are at least mathematical problems that were eventually solved. There are other problems in number theory that remain unsolved to this date. A number of them are also easy to state. In mathematics, if a problem proves very difficult, it is fairly common to look at a related but simpler problem. Goldbach’s conjecture, if true, has an immediate consequence: every positive odd integer greater than 5 can be written as the sum of three primes.

Pages: 23

In this chapter, we introduce the most basic idea of number theory, divisibility. This in turn leads naturally to a discussion of primes, the “building blocks” of the positive integers. As discussed in Chapter 0, the prime numbers have fascinated people for centuries, and even today their patterns and distribution remain objects of intense scrutiny. Before getting to these topics, however, we need to introduce two principles of number theory that will be used repeatedly throughout this book.

Pages: 23

Let us begin with a simple motivating problem: If today is Monday, what day will it be 200 days from now? At first glance this seems like a cumbersome problem to answer, until we recognize a simple trick: 7 days from now, it will be Monday again. It will also be Monday 14 days from now, 21 days from now, etc. In particular, it will be Monday 196 days from now, because 196 is a multiple of 7. So, since we “reset the clock” at day 196, the original question posed is equivalent to asking what day it will be 4 days from now, and the answer to that is obvious: Friday.

Pages: 9

One of the more striking “real world” applications of number theory is the study of cryptography, which concerns itself with secret communications. The ability to decipher such communications can have striking global consequences; the decipherment of the famous Zimmerman telegram (a 1917 communication from the German Foreign Office to the German ambassador in Mexico), for example, played a significant role in the decision of the United States to enter World War I. This chapter gives an introduction to this area of mathematics, emphasizing the role that number theory plays in it. The idea of “wrapping around” to the beginning of the alphabet suggests modular arithmetic, and indeed it is easy to see how to formalize this mathematically. Essentially, the RSA method depends for its validity on this rule of thumb: multiplying is easy, factoring is hard.

Pages: 6

The subject matter of this chapter, perfect numbers, has ancient roots, dating back to the time of Euclid, where they are discussed in Book IX of his monumental treatise The Elements. Interestingly, however, only four specific perfect numbers were actually known to the Greeks. Now we know many more, but as we will see there are still several long-standing open questions concerning them.

Pages: 12

The subject matter of this chapter has strong algebraic content and is, in fact, largely a special case of basic group theory in abstract algebra. Of course, abstract algebra is not a prerequisite for this text, so the material will be developed from scratch in a number-theoretic setting. However, since it would be a pity not to understand this material in its proper context, occasional references to group theory will be made. These references can be ignored by people who are not interested in these algebraic connections. In proving the various facts quoted, the only properties of the real numbers that are used is the fact that they can be added, subtracted, multiplied and divided, and that the various standard rules of arithmetic hold. This chapter looks at a special kind of prime number that, on its face, seems to have nothing to do with perfect numbers, but which ultimately play an important role in their classification.

Pages: 14

In this chapter, we consider integers that are congruent, modulo a prime p, to the square of another integer. This is equivalent to considering when an element of https://www.w3.org/1998/Math/MathML" display="inline"> ℤ https://www.w3.org/1999/xlink" xlink:href="https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781003318712/0a8d6242-fb38-4fc0-af6c-0a4803a1cbee/content/C006_equ_0001.tif"/> p can be written as the square of another element of https://www.w3.org/1998/Math/MathML" display="inline"> ℤ https://www.w3.org/1999/xlink" xlink:href="https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781003318712/0a8d6242-fb38-4fc0-af6c-0a4803a1cbee/content/C006_equ_0002.tif"/> p. For example, in https://www.w3.org/1998/Math/MathML" display="inline"> ℤ https://www.w3.org/1999/xlink" xlink:href="https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781003318712/0a8d6242-fb38-4fc0-af6c-0a4803a1cbee/content/C006_equ_0003.tif"/> 11, [3] is a square, because [3] = [5]2. Our ultimate objective is a discussion of one of the most famous theorems of elementary number theory, the Law of Quadratic Reciprocity.

Pages: 29

Up to now, we have been studying the set https://www.w3.org/1998/Math/MathML" display="inline"> ℤ https://www.w3.org/1999/xlink" xlink:href="https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781003318712/0a8d6242-fb38-4fc0-af6c-0a4803a1cbee/content/C007_equ_0001.tif"/> integers. In this chapter, however, we expand our horizons and study other number systems that have features in common with https://www.w3.org/1998/Math/MathML" display="inline"> ℤ https://www.w3.org/1999/xlink" xlink:href="https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781003318712/0a8d6242-fb38-4fc0-af6c-0a4803a1cbee/content/C007_equ_0001.tif"/> , but also some differences as well. We study them for several reasons. First, we can use these systems to actually prove things about the integers, and second, their study helps shed some light on unique factorization into primes, which turns out to be a subtler idea than one might expect at first.