Elementary Number Theory - 2nd Ed.

1 Elementary Number Theory Second Edition V nderwood Dudley DePauw University rn w. H. FREEMAN AND COMPANY New York Section 1 Section 2 Section 3 Section 4 Section 5 Section 6 Section 7 Section 8 Section 9 Section 10 Section 11 Preface vii Integers 1 Contents Unique Factorization 10 Linear Diophantine Equations 20 Congruences 27 Linear Congruences 34 Fermat's and Wilson's Theorems 42 The Divisors of an Integer 50 Perfect Numbers 57. Euler's Theorem and Function 63 Primitive Roots 73 Quadratic Congruences 83 v vi Contents Section 12 Section 13 Section 14 Section 15 Section 16 Section 17 Section 18 Section 19 Section 20 Section 21 Section 22 Section 23 Appendix A Appendix B Appendix C Quadratic Reciprocity 94 Numbers in Other Bases 106 Duodecimals 114 Decimals 119 Pythagorean Triangles 127 Infinite Descent and Fermat's Conjecture 135 Sums of Tw o Squares 141 Sums of Four Squares 149 Xl -Ny::!

2 = 1 155 Bounds for mx) 163 Formulas for Primes 172 Additional Problems 182 Proof by Induction 205 Computer Problems 210 Factor Table for Integers Less Than 10,000 217 References 225 Answers to Selected Exercises 227 Answers to Selected Odd-Numbered Problems 231 Comments on Selected Odd-Numbered Problems 238 Index 247 Preface Mathematics exists mainly to give us power and control over the phys ical world, but it has always been so fascinating that it was studied for its own sake. Number Theory is that sort of mathematics: it is of no use in building bridges, and civilization would carryon much as usual if all of its theorems were to disappear, nevertheless it has been studied and valued since the time of Pythagoras.

3 That greatest of mathe maticians Carl Friedrich Gauss called it "The Queen of Mathematics," and "Everybody's Mathematics" is what the contemporary mathe matician Ivan Niven calls it. The reason for its appeal is that the subject matter-numbers-is part of everyone's experience, and the things that can be found out about them are interesting, curious, or surprising, and the ways they are found can be delightful: clean lines of logic, with sustained tension and satisfying resolutions. a course in Number Theory can do several things for a student. It can acquaint him or her with ideas no student of mathematics should be ignorant of. More important, it is an example of the mathematical style of thinking-problem, deduction, solution-in a system where the problems are not unnatural or artificial.

4 Most important, it can help to diminish the feeling that many students have, consciously or not, that mathematics is a collection of formulas and that to solve a problem you need only find the appropriate formula. VII viii Prefa ce This text has been designed for a one-semester or one-quarter course in Number Theory , with minimal prerequisites. The reader is not re quired to know any mathematics except Elementary algebra and the properties of the real numbers. Nevertheless, the average student does not find Number Theory easy because it involves understanding new ideas and the proofs of theorems. I have -tried to make the proofs detailed enough to be clear, and I have included numerical examples, not only to illustrate the ideas, but to show the fascination of playing with numbers, which is how many of the ideas originated.

5 I have included an introduction to most of the topics of Elementary Number Theory . In Sections 1 through 5 the fundamental properties of the integers and congruences are developed, and in Section 6 proofs of Fermat's and Wilson's theorems are given. The Number theoretic functions d, cr, and 1> are introduced in Sections 7 to 9. Sections 10 to 12 culminate in the quadratic reciprocity theorem. There follow three more or less independent blocks of material: the representation of numbers (Sections 13 to 15), diophantine equations (16 to 20), and primes (21 and 22). Because I think that problems are especially im portant and interesting in Number Theory , Section 23 consists of 260 additional problems, some classified by section and some arranged without regard to topic.

6 ' There are three appendixes. Appendix A, Proof by Induction, should be read when and if necessary. Because computers integrate naturally with Number Theory , Appendix B presents problems for which it com puter can be programmed. Appendix C contains a table that makes it easy to factor any positive integer less than 10,000. Because I believe that the best way to learn mathematics is to try to solve problems, the text includes almost a thousand exercises and problems. I attribute the success of the first edition not to the exposition-after all, the proofs were already known-but to the prob lems, and the problem lists have been revised, deleting unsuccessful problems and including new ones that may be mOre successful.

7 The exercises interrupt the text and can be used in several ways: the stu dent may do them as he reads the material for the first time; he may return to them later to check on his understanding of material already studied; or the instructor may include them in his exposition. Some of the exercises and problems are computational and some classical, but many are more or less original, and a few, I think, are startling. Number Theory pr?blems can be difficult because inspiration is some times necessary to find a solution, and inspiration cannot be had to Preface ix order. A student should not expect to be able to conquer all of the problems and should not feel discouraged if some are baffling.

8 There is benefit in trying to solve prOblems whether a solution is found or not. I. A. Barnett has written [1] "To discover mathematical talent, there is no better course in Elementary mathematics than Number Theory . Any student who can work the exercises in a modern text in Number Theory should be encouraged to pursue a mathematical career." Answers are provided where appropriate for exercises and odd numbered problems-those marked with an asterisk. Comments are given for those problems marked with a dagger. Although there are more problems than a student could solve in one semester, they should be treated as part of the text, to be read even if not solved. Some times they may be more interesting than the material on which they are based.

9 The first edition contained many errors, and I want to thank the many people who pointed them out and suggested improvements. These errors have all been removed, but inevitably new ones have been added. I hope that when the reader finds one, he will feel pleased with his acuteness rather than annoyed with the author. Corrections will be welcomed. Underwood Dudley May 1978 Elementary Number Theory Section 1 Integers The subject matter of Number Theory is numbers, and a large part of Number Theory is devoted to studying the properties of the integers that is, the numbers .. , -2, -1,0,1,2, .. Usually the integers are used merely to convey information (3 apples, $32, 17x2 + 9) , with no consideration of their properties.

10 When counting apples, dollars, or X2'S, it is immaterial how many divisors 3 has, whether 32 is prime or not, or that 17 can be written as the sum of the squares of two integers. But the integers are so basic a part of mathematics that they have been thought worthy of study for their own sake. The same situation arises elsewhere: the Number theorist is coinparable to the linguist, who studies words and their properties, independent of their meaning. There are many replies to the question, "Why study numbers?" Here are some that have been given: Because teacher says you must. Because you won't graduate if you don't.. Because you have to take something. Because it gives your mind valuable training in thinking logically.