Number Theory (Pure and Applied Undergraduate Texts)

Number Theory is a newly translated and revised edition of the most popular introductory textbook on the subject in Hungary. The book covers the usual topics of introductory number theory: divisibility, primes, Diophantine equations, arithmetic functions, and so on. It also introduces several more advanced topics including congruences of higher degree, algebraic number theory, combinatorial number theory, primality testing, and cryptography. The development is carefully laid out with ample illustrative examples and a treasure trove of beautiful and challenging problems. The exposition is both clear and precise. The book is suitable for both graduate and undergraduate courses with enough material to fill two or more semesters and could be used as a source for independent study and capstone projects. Freud and Gyarmati are well-known mathematicians and mathematical educators in Hungary, and the Hungarian version of this book is legendary there. The authors' personal pedagogical style as a facet of the rich Hungarian tradition shines clearly through. It will inspire and exhilarate readers. Cover 1 Title page 5 Copyright 6 Contents 7 Introduction 13 Structure of the book 13 Exercises 14 Short overview of the individual chapters 14 Technical details 16 Commemoration 16 Acknowledgements 17 Chapter 1. Basic Notions 19 1.1. Divisibility 19 Exercises 1.1 21 1.2. Division Algorithm 23 Exercises 1.2 25 1.3. Greatest Common Divisor 27 Exercises 1.3 31 1.4. Irreducible and Prime Numbers 33 Exercises 1.4 35 1.5. The Fundamental Theorem of Arithmetic 36 Exercises 1.5 39 1.6. Standard Form 40 Exercises 1.6 45 Chapter 2. Congruences 49 2.1. Elementary Properties 49 Exercises 2.1 52 2.2. Residue Systems and Residue Classes 53 Exercises 2.2 56 2.3. Euler’s Function φ 58 Exercises 2.3 61 2.4. The Euler–Fermat Theorem 62 Exercises 2.4 63 2.5. Linear Congruences 64 Exercises 2.5 69 2.6. Simultaneous Systems of Congruences 70 Exercises 2.6 76 2.7. Wilson’s Theorem 78 Exercises 2.7 79 2.8. Operations with Residue Classes 80 Exercises 2.8 82 Chapter 3. Congruences of Higher Degree 85 3.1. Number of Solutions and Reduction 85 Exercises 3.1 87 3.2. Order 88 Exercises 3.2 90 3.3. Primitive Roots 92 Exercises 3.3 96 3.4. Discrete Logarithm (Index) 98 Exercises 3.4 99 3.5. Binomial Congruences 100 Exercises 3.5 102 3.6. Chevalley’s Theorem, Kőnig–Rados Theorem 103 Exercises 3.6 107 3.7. Congruences with Prime Power Moduli 108 Exercises 3.7 110 Chapter 4. Legendre and Jacobi Symbols 113 4.1. Quadratic Congruences 113 Exercises 4.1 115 4.2. Quadratic Reciprocity 116 Exercises 4.2 120 4.3. Jacobi Symbol 121 Exercises 4.3 123 Chapter 5. Prime Numbers 125 5.1. Classical Problems 125 Exercises 5.1 129 5.2. Fermat and Mersenne Primes 130 Exercises 5.2 136 5.3. Primes in Arithmetic Progressions 137 Exercises 5.3 139 5.4. How Big Is π(x)? 140 Exercises 5.4 145 5.5. Gaps between Consecutive Primes 146 Exercises 5.5 151 5.6. The Sum of Reciprocals of Primes 152 Exercises 5.6 159 5.7. Primality Tests 161 Exercises 5.7 169 5.8. Cryptography 172 Exercises 5.8 175 Chapter 6. Arithmetic Functions 177 6.1. Multiplicative and Additive Functions 177 Exercises 6.1 179 6.2. Some Important Functions 182 Exercises 6.2 185 6.3. Perfect Numbers 187 Exercises 6.3 189 6.4. Behavior of d(n) 190 Exercises 6.4 197 6.5. Summation and Inversion Functions 198 Exercises 6.5 201 6.6. Convolution 202 Exercises 6.6 205 6.7. Mean Value 207 Exercises 6.7 218 6.8. Characterization of Additive Functions 219 Exercises 6.8 221 Chapter 7. Diophantine Equations 223 7.1. Linear Diophantine Equation 224 Exercises 7.1 226 7.2. Pythagorean Triples 227 Exercises 7.2 229 7.3. Some Elementary Methods 230 Exercises 7.3 233 7.4. Gaussian Integers 235 Exercises 7.4 241 7.5. Sums of Squares 242 Exercises 7.5 247 7.6. Waring’s Problem 248 Exercises 7.6 252 7.7. Fermat’s Last Theorem 253 Exercises 7.7 261 7.8. Pell’s Equation 263 Exercises 7.8 267 7.9. Partitions 268 Exercises 7.9 273 Chapter 8. Diophantine Approximation 275 8.1. Approximation of Irrational Numbers 275 Exercises 8.1 280 8.2. Minkowski’s Theorem 282 Exercises 8.2 286 8.3. Continued Fractions 287 Exercises 8.3 292 8.4. Distribution of Fractional Parts 293 Exercises 8.4 295 Chapter 9. Algebraic and Transcendental Numbers 297 9.1. Algebraic Numbers 297 Exercises 9.1 300 9.2. Minimal Polynomial and Degree 300 Exercises 9.2 302 9.3. Operations with Algebraic Numbers 303 Exercises 9.3 306 9.4. Approximation of Algebraic Numbers 308 Exercises 9.4 312 9.5. Transcendence of e 313 Exercises 9.5 318 9.6. Algebraic Integers 318 Exercises 9.6 320 Chapter 10. Algebraic Number Fields 323 10.1. Field Extensions 323 Exercises 10.1 326 10.2. Simple Algebraic Extensions 327 Exercises 10.2 331 10.3. Quadratic Fields 332 Exercises 10.3 342 10.4. Norm 343 Exercises 10.4 346 10.5. Integral Basis 347 Exercises 10.5 352 Chapter 11. Ideals 353 11.1. Ideals and Factor Rings 353 Exercises 11.1 357 11.2. Elementary Connections to Number Theory 359 Exercises 11.2 362 11.3. Unique Factorization, Principal Ideal Domains, and Euclidean Rings 362 Exercises 11.3 367 11.4. Divisibility of Ideals 369 Exercises 11.4 373 11.5. Dedekind Rings 375 Exercises 11.5 384 11.6. Class Number 385 Exercises 11.6 388 Chapter 12. Combinatorial Number Theory 389 12.1. All Sums Are Distinct 389 Exercises 12.1 396 12.2. Sidon Sets 398 Exercises 12.2 405 12.3. Sumsets 406 Exercises 12.3 414 12.4. Schur’s Theorem 415 Exercises 12.4 419 12.5. Covering Congruences 420 Exercises 12.5 424 12.6. Additive Complements 424 Exercises 12.6 430 Answers and Hints 433 A.1. Basic Notions 433 A.2. Congruences 443 A.3. Congruences of Higher Degree 454 A.4. Legendre and Jacobi Symbols 464 A.5. Prime Numbers 467 A.6. Arithmetic Functions 479 A.7. Diophantine Equations 495 A.8. Diophantine Approximation 513 A.9. Algebraic and Transcendental Numbers 517 A.10. Algebraic Number Fields 522 A.11. Ideals 528 A.12. Combinatorial Number Theory 533 Historical Notes 543 Tables 549 Primes 2–1733 550 Primes 1741–3907 551 Prime Factorization 552 Mersenne Numbers 553 Fermat Numbers 554 Index 555 Back Cover 563 Number Theory is a newly translated and revised edition of the most popular introductory textbook on the subject in Hungary. The book covers the usual topics of introductory number theory: divisibility, primes, Diophantine equations, arithmetic functions, and so on. It also introduces several more advanced topics including congruences of higher degree, algebraic number theory, combinatorial number theory, primality testing, and cryptography. The development is carefully laid out with ample illustrative examples and a treasure trove of beautiful and challenging problems. The exposition is both clear and precise.??The book is suitable for both graduate and undergraduate courses with enough material to fill two or more semesters and could be used as a source for independent study and capstone projects. Freud and Gyarmati are well-known mathematicians and mathematical educators in Hungary, and the Hungarian version of this book is legendary there. The authors' personal pedagogical style as a facet of the rich Hungarian tradition shines clearly through. It will inspire and exhilarate readers. publisher