Fundamental Number Theory with Applications

Description

An update of the most accessible introductory number theory text available, Fundamental Number Theory with Applications, Second Edition presents a mathematically rigorous yet easy-to-follow treatment of the fundamentals and applications of the subject. The substantial amount of reorganizing makes this edition clearer and more elementary in its coverage. New to the Second Edition •          Removal of all advanced material to be even more accessible in scope •          New fundamental material, including partition theory, generating functions, and combinatorial number theory •          Expanded coverage of random number generation, Diophantine analysis, and additive number theory •          More applications to cryptography, primality testing, and factoring •          An appendix on the recently discovered unconditional deterministic polynomial-time algorithm for primality testing Taking a truly elementary approach to number theory, this text supplies the essential material for a first course on the subject. Placed in highlighted boxes to reduce distraction from the main text, nearly 70 biographies focus on major contributors to the field. The presentation of over 1,300 entries in the index maximizes cross-referencing so students can find data with ease. Cover......Page 1 Title Page......Page 5 Copyright......Page 6 Contents......Page 8 Preface......Page 10 1.1 Induction......Page 12 1.2 Division......Page 27 1.3 Primes......Page 41 1.4 The Chinese Remainder Theorem......Page 51 1.5 Thue’s Theorem......Page 55 1.6 Combinatorial Number Theory......Page 60 1.7 Partitions and Generating Functions......Page 66 1.8 True Primality Tests......Page 71 1.9 Distribution of Primes......Page 76 2.1 Basic Properties......Page 84 2.2 Modular Perspective......Page 95 2.3 Arithmetic Functions: Euler, Carmichael, and Mobius......Page 101 2.4 Number and Sums of Divisors......Page 113 2.5 The Floor and the Ceiling......Page 119 2.6 Polynomial Congruences......Page 124 2.7 Primality Testing......Page 130 2.8 Cryptology......Page 138 3.1 Order......Page 150 3.2 Existence......Page 156 3.3 Indices......Page 164 3.4 Random Number Generation......Page 171 3.5 Public-Key Cryptography......Page 177 4.1 The Legendre Symbol......Page 188 4.2 The Quadratic Reciprocity Law......Page 200 4.3 Factoring......Page 212 5.1 Infinite Simple Continued Fractions......Page 220 5.2 Periodic Simple Continued Fractions......Page 232 5.3 Pell’s Equation and Surds......Page 243 5.4 Continued Fractions and Factoring......Page 251 6.1 Sums of Two Squares......Page 254 6.2 Sums of Three Squares......Page 263 6.3 Sums of Four Squares......Page 265 6.4 Sums of Cubes......Page 270 7.1 Norm-Form Equations......Page 276 7.2 The Equation ax² + by² + cz² = 0......Page 285 7.3 Bachet’s Equation......Page 288 7.4 Fermat’s Last Theorem......Page 292 Appendix A: Fundamental Facts......Page 296 Appendix B: Complexity......Page 322 Appendix C: Primes < 9547 and Least Primitive Roots......Page 324 Appendix D: Indices......Page 329 Appendix E: The ABC Conjecture......Page 330 Appendix F: Primes is in P......Page 331 Solutions to Odd-Numbered Exercises......Page 334 Bibliography......Page 362 List of Symbols......Page 366 Index......Page 367 About the Author......Page 380