Ve Rs (GINA THEORY NUMBER NUMBER THEORY |:3m The cover illustration is an artist’s representation of the so-called golden rectangle. If the largest square in a golden rectangle is cut away, then the figure remaining will also be a golden rectangle. Such rectangles are charac terized by a length to width ratio of (1+ V 5 )/2, the golden ratio. The ancient gyptians may have used this ratio in the construction of pyramids.
The ratio ecurs often in number theory; for example, lim n>* D,'(n) where D,(n) and D,'(n) are the partition functions occurring in the Rogers Ramanujan identities, and F,, is the nth Fibonacci number. cover designed by Lorraine Battista. NUMBER THEORY GEORGE E. ANDREWS Professor of Mathematics Pennsylvania State University W.
SAUNDERS COMPANY ¢ PHILADELPHIA * LONDON * TORONTO W. Saunders Company: West Washington Square Philadelphia, Pa. 19105 12 Dyott Street London, WCIA 1DB 833 Oxford Street Toronto 18, Ontario | | Number Theory ISBN 0-7916-1955-5 we © 1971 by W. Copyright under the International Copyright Union.
All rights reserved. This book is protected by copyright. No part of it may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise, without written permission from the publisher. Made in the United States of America.
Library of Congress catalog card number 74-151673. 8 9 6-5 1 ' 3 R2 To Joy and Amy PREFACE Most mathematics majors first encounter number theory in courses on abstract algebra, for which number theory provides numerous ' examples of algebraic systems, such as finite groups, rings, and fields. The instructor of undergraduate number theory thus faces a predica- ment. He must interest advanced mathematics students, who have previously studied congruences and the fundamental theorem of arithmetic, as well as other students, mostly from education and liberal arts, who usually need a careful exposition of these basic topics.
To interest a class of students whose backgrounds are so diver- gent, this text offers a combinatorial approach to elementary number theory. The rationale for this point of view is perhaps best summarized by Herbert Ryser in Combinatorial Mathematics: “. combinatorics and number theory are sister disciplines. They share a certain inter- section of common knowledge and each genuinely enriches the other.
”* In studying number theory from a combinatorial 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 (the proofs of Theorems 1-3, 3-4, 3-5, 6-1, 6-2, 6-3, 7-6, 8-4, and 9-4 rely mainly on simple com- binatorial reasoning). Number theory and combinatorics are combined in Chapters 10 through 15 to aid in the discovery and proof of theorems. Two aspects of the text require preliminary discussion. First, Section 5 of Chapter 3 is critical to the whole work.
This section illus- trates both the value of numerical examples in number theory and the role of computers in obtaining such examples. The accompanying exercises provide opportunities for constructing numerical tables, with or without a computer. Subsequent chapters may then be intro- duced to advantage by allowing students to report on conjectures they derive from relevant numerical tables. When students are thus actively involved, theorems will seem natural and well motivated., Combinatorial Mathematics (Carus Monograph No.
Mathematical Association of America, 1963. Vv vi PREFACE Second, in Chapters 12, 13, and 14, the student will encounter partitions, a topic in additive number theory. Too often, one obtains from number theory texts the impression that each topic has been thoroughly developed. The problems offered in such texts are either solved or unsolvable; at best, the student is invited to work a few peripheral problems.
In this book, Chapter 12 attempts to com- municate the excitement of the mathematical chase by devising a procedure for forming conjectures in partition theory. The exercises at the end of Chapter 12 provide the student with a number of oppor- tunities for discovering theorems himself. Chapters 13 and 14 develop techniques in the application of generating functions to partition theory so that the student can prove some of the conjectures he made in Chapter 12. In presenting Chapter 14, the instructor should assign the exercises at the end prior to beginning lectures, in order to avoid the unmotivated presentation of complicated manipulations of series and products; through this procedure, the student is led to appreciate the relation between the exercises and the steps in the proof of the Rogers-Ramanujan identities and of Schur’s Theorem.
Many people have aided me in preparing this book. I express particular thanks to the students in my class of Spring Term, 1970, at Penn State, who were taught from the completed text and who gen- erously offered valuable suggestions. Piranian read the entire manuscript and made many useful contributions. Carlos Puig and George Fleming of W.
Saunders have skillfully guided the process of publication. Finally I pay tribute to my wife, Joy, who has been the most important helper in the creation of this book; at each stage her en- couragement, intelligence, and energy have added significant value. She has been immensely creative both in writing expository material and in facilitating the communication of ideas to students. Without her aid, a mass of scribbled lecture notes would still be just that.
For certain classes where the instructor deems it wise to omit material requiring calculus, I recommend using all or part of the following: Chapters 1, 2, 3 (omit Sections 3-3 and 3-4), 4, 5, 6, 7, 8 (omit Section 8-2), 9, 10 (omit Section 10-2 except for a brief discus- sion of Corollary 10-1), 11 (omit Section 11-2 save for a summary of the results), 12, and 15 (up to Definition 15-1). Andrews CONTENTS Part | MULTIPLICATIVITY — DIVISIBILITY Chapter 1 BASIS REPRESENTATION.cccccccececscccceccscucuceccseceececceccceces 3 1-1 Principle of Mathematical Induction. 3 1-2_ The Basis Representation Theorem. 8 Chapter 2 THE FUNDAMENTAL THEOREM OF ARITHMETIC.
12 2-1 Euclid’s Division Lemma. se ceveeseceees 12 2-2_ Divisibility. HQ HH nu nhe cư. 15 2-3 The Linear Diophantine Equation.
23 2-4 The Fundamental Theorem of Arithmetic. 26 Chapter 3 COMBINATORIAL AND COMPUTATIONAL NUMBER THEORV. 30 d-l Permutations and Combinations. 30 d-2 Fermat's Little Theorem.
40 3-5 The Use of Computers in Number Theory. 44 Chapter 4 FUNDAMENTALS OF CONGRUENCEG.0cccececececccecucecucccecececcces 49 4-1 Basic Properties of Congruences. 56 Vii viii CONTENTS Chapter 5 SOLVING CONGRUENCES. SH ng nh 58 5—l Linear CongruenC©S.
58 5-2 The Theorems of Fermat and Wilson Revisited. 61 5-3 The Chinese Remainder Theorem.««+ 71 Chapter ó ARITHMETIC FUNCTIONS. 75 6-1 Combinatorial Study of QÍ(?).-- se 75 6-2 Formulae for d(n) and ơ(?}.-------=«- 82 6-3 Multiplicative Arithmetic Functions.4 85 6-4 The Möbius Inversion FormulÌa. 86 Chapter 7 PRIMITIVE RÑOOTS.-- cọ nọ HH n HH kinh km be 93 7-1 Properties of Reduced Residue Systems.
Primitive Roots ModulÌo ø.--««<«- 97 Chapter 8 PRIME NUMBERS_. c9 nh kg 100 8-1 Elementary Properties OÍ 7(%).-------<+ «<< <s- 106 8-3 Some Unsolved Problems About Primes. 111 Part Il QUADRATIC CONGRUENCES Chapter 9 QUADRATIC RESIDUES Sàn nành eee een eee ee enna ees 115. 115 9-2 The Legendre Symbol.-----------------<- 117 9-3 The Quadratic Reciprocity Law.----- 118 9-4 Applications of the Quadratic Reciprocity Law.
125 Chapter 10 DISTRIBUTION OF QUADRATIC << Ÿ*+ 128 RESIDUES.------- 10-1 Consecutive Residues and Nonresidues. 128 10-2 Consecutive Triples of Quadratic Residues. 133 CONTENTS ix Part lil ADDITIVITY Chapter 11 SUMS OF SQUARES. On HH ng nh như.
11-1 Sums of Two Squares. 11-2 S5ums of Four Squares. Chapter 12 ELEMENTARY PARTITION THEORY. 12-3 Eulers Partition Theorem.
12-4 Searching for Partition Identities. Chapter 13 PARTITION GENERATING FEUNCTIONS. 13-1 Infinite Products As Generating Functions. 13-2 Identities Between Infinite Series and Products.
Chapter 14 PARTITION IÏDENTITIES_.2 222222222 nà, 14-1 History and Introduction. 14-2 Euler’s Pentagonal Number Theorem. 14-3 The Rogers-Ramanujan Identities. 14-4 Series and Product Identities.¿ Part IV GEOMETRIC NUMBER THEORY Chapter 15 LATTICE POINTS #9 ĐO 9 9694600900009 0066900049000 00060606 0096066 0060990060606 0006990060609 906 meeeeese APPENDICES Appendix A A PROOEF THAT lim Ø(ø)!* = ].
con Tnhh n reg x CONTENTS Appendix B INFINITE SERIES AND PRODUCTS (Convergence and Rearrangement of Series and Produets). 219 Appendix C DOUBLE SERIES. --- 221 Appendix D THE [NTEGRAL TÌEST'.- ch vn 226 1/5127 › 227 SUGGESTED READING.nSằ SH nh nh ng 230 BIBLIOGRAPHY. suuuccceeessasseeeaansececsetevevaccanecesesonsiessenensess 231 HINTS AND ANSWERS TO SELECTED EXERCISES.-- 233 INDEX OF SYMBOLS.
ccccc S119 1111 cv nén 253 PART | 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 a(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 | 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, of the first n consecutive positive in- tegers for values of n from 1 through 10.
Notice that in each case S, equals one-half the product of n and the next integer; that is, _ nín + 1) Sn 2 (1-1-1) for n=1,2,3,. Although this formula gives the correct value of S,, for the first ten values of n, we cannot be sure that it holds for n greater than 10. cài SỐ To construct Table 1-1, we do not need to compute S,, each time by adding the first n positive integers. Having obtained values of S,, TABLE 1-1: SuM S, OF THE FIRST n CONSECUTIVE POSITIVE INTEGERS.
n S,, n Sn 21 WODdWe COMOND 28 WD 36 45 CUR bo 55 — 4 BASIS REPRESENTATION for n less than or equal to some integer k, we can determine S;+, simply by adding (k +1) to S;: Sroi= Si (k+ 1). This last approach suggests a way of verifying equation (1-1-1). Suppose we know that formula (1-1-1) is true for n = k, where k is a positive integer. Then we know that k(k+1 S.
The last equation is the same as equation (1-1-1) except that n is replaced by k +1. We have proved that if equation (1-1-1) holds for n = k, then it holds for n=k-+1, and we have already verified that equation (1-1-1) holds for n= 1,2,. Therefore, by the preceding argument, we conclude that equation (1-1-1) is also correct for n=11. Since it holds for n= 1,2,., 11, the same process shows that it is correct for n= 12.
Since it is true forn = 1,2, ., 12, it is true forn = 13, and so on. We can describe the principle underlying the foregoing argument in various ways. The following formulation is the most appropriate for our purposes.