Number Theory

George E. Andrews

• Publisher: Dover Publications
• Year: 2012
• ISBN:
  9780486135106
• Topic: Mathematics
• Subtopic: Number Theory
• Index: Mathematics

Although mathematics majors are usually conversant with number theory by the time they have completed a course in abstract algebra, other undergraduates, especially those in education and the liberal arts, often need a more basic introduction to the topic.
In this book the author solves the problem of maintaining the interest of students at both levels by offering a combinatorial approach to elementary number theory. In studying number theory from such a perspective, mathematics majors are spared repetition and provided with new insights, while other students benefit from the consequent simplicity of the proofs for many theorems.
Among the topics covered in this accessible, carefully designed introduction are multiplicativity-divisibility, including the fundamental theorem of arithmetic, combinatorial and computational number theory, congruences, arithmetic functions, primitive roots and prime numbers. Later chapters offer lucid treatments of quadratic congruences, additivity (including partition theory) and geometric number theory.
Of particular importance in this text is the author's emphasis on the value of numerical examples in number theory and the role of computers in obtaining such examples. Exercises provide opportunities for constructing numerical tables with or without a computer. Students can then derive conjectures from such numerical tables, after which relevant theorems will seem natural and well-motivated..

PART I

---

MULTIPLICATIVITY-DIVISIBILITY

Part I is devoted to multiplicative problems; these are sometimes called divisibility problems, since division is the inverse of multiplication.

The knowledge of divisibility that we gain in the first two chapters leads us to our first goal, the fundamental theorem of arithmetic, which discloses the important role of primes in multiplicative number theory. Chapter 3 introduces combinatorial techniques for solving important divisibility problems and answering other number-theoretic questions. In order that we can study divisibility problems in greater depth, Chapters 4 and 5 develop the theory of congruences. Chapter 6 discusses some of the important functions related to multiplication and division, for example the number d(n) of divisors of n and the sum σ(n) of the divisors of n. Our results on congruences are extended in Chapter 7. The final chapter of Part I is concerned with the distribution of primes.

CHAPTER 1

---

BASIS REPRESENTATION

Our objective in this chapter is to prove the basis representation theorem (Theorem 1–3). First we need to understand the principle of mathematical induction, a tool indispensable in number theory.

1–1 PRINCIPLE OF MATHEMATICAL INDUCTION

Let us try to answer the following question: What is the sum of all integers from one through n, for any positive integer n? If n = 1, the sum equals 1 because 1 is the only summand. The answer we seek is a formula that will enable us to determine this sum for each value of n without having to add the summands.

Table 1–1 lists the sum S_n of the first n consecutive positive integers for values of n from 1 through 10. Notice that in each case S_n equals one-half the product of n and the next integer; that is,

for n = 1, 2, 3, …, 10. Although this formula gives the corr...