An Experimental Introduction to Number Theory (Pure and Applied Undergraduate Texts) (Pure and Applied Undergraduate Texts, 31)

This book presents material suitable for an undergraduate course in elementary number theory from a computational perspective. It seeks to not only introduce students to the standard topics in elementary number theory, such as prime factorization and modular arithmetic, but also to develop their ability to formulate and test precise conjectures from experimental data. Each topic is motivated by a question to be answered, followed by some experimental data, and, finally, the statement and proof of a theorem. There are numerous opportunities throughout the chapters and exercises for the students to engage in (guided) open-ended exploration. At the end of a course using this book, the students will understand how mathematics is developed from asking questions to gathering data to formulating and proving theorems. The mathematical prerequisites for this book are few. Early chapters contain topics such as integer divisibility, modular arithmetic, and applications to cryptography, while later chapters contain more specialized topics, such as Diophantine approximation, number theory of dynamical systems, and number theory with polynomials. Students of all levels will be drawn in by the patterns and relationships of number theory uncovered through data driven exploration. Cover......Page 1 Title page......Page 4 Contents......Page 6 Note to the Instructor......Page 10 Organization......Page 11 Acknowledgments......Page 12 Introduction......Page 14 1. The Integers and the Well Ordering Property......Page 18 2. Divisors and the Division Algorithm......Page 19 3. Greatest Common Divisor and the Euclidean Algorithm......Page 23 4. Prime Numbers and Unique Factorization......Page 33 Exercises......Page 41 1. Basic Arithmetic......Page 52 2. Inverses and Fermat’s Little Theorem......Page 57 3. Linear Congruences and the Chinese Remainder Theorem......Page 64 Exercises......Page 70 1. Quadratic Reciprocity......Page 78 2. Computing th Roots Modulo ......Page 89 3. Existence of Primitive Roots......Page 94 Exercises......Page 98 Chapter 4. Secrets......Page 104 1. Basic Ciphers......Page 105 2. Symmetric Ciphers......Page 108 3. Diffie–Hellman Key Exchange......Page 110 4. Public Key Cryptography (RSA)......Page 111 5. Hash Functions and Check Digits......Page 114 6. Secret Sharing......Page 117 Exercises......Page 118 1. Euler Totient Function......Page 122 2. Möbius Function......Page 126 3. Functions on Divisors......Page 134 4. Partitions......Page 143 Exercises......Page 147 1. Algebraic or Transcendental......Page 156 2. Quadratic Number Fields and Norms......Page 158 3. Integers, Divisibility, Primes, and Irreducibles......Page 161 4. Application: Sums of Two Squares......Page 165 Exercises......Page 166 1. Diophantine Approximation......Page 170 2. Height of a Rational Number......Page 172 3. Heights and Approximations......Page 175 4. Continued Fractions......Page 179 5. Approximating Irrational Numbers with Convergents......Page 184 Exercises......Page 193 1. Introduction and Examples......Page 200 2. Working Modulo Primes......Page 202 3. Pythagorean Triples......Page 211 4. Fermat’s Last Theorem......Page 213 5. Pell’s Equation and Fundamental Units......Page 215 6. Waring Problem......Page 221 Exercises......Page 225 1. Introduction......Page 234 2. Addition of Points......Page 237 3. Points of Finite Order......Page 242 4. Integer Points and the Nagel–Lutz Theorem......Page 243 5. Mordell–Weil Group and Points of Infinite Order......Page 249 6. Application: Congruent Numbers......Page 250 Exercises......Page 253 1. Discrete Dynamical Systems......Page 260 2. Dynatomic Polynomials......Page 267 3. Resultant and Reduction Modulo Primes......Page 271 4. Periods Modulo Primes......Page 275 5. Algorithms for Rational Periodic and Preperiodic Points......Page 279 Exercises......Page 281 1. Introduction to Polynomials......Page 288 2. Factorization and the Euclidean Algorithm......Page 291 3. Modular Arithmetic for Polynomials......Page 295 4. Diophantine Equations for Polynomials......Page 301 Exercises......Page 306 Bibliography......Page 312 List of Algorithms......Page 316 List of Notation......Page 318 Index......Page 320 Back Cover......Page 329 Cover 1 Title page 4 Contents 6 Preface 10 Note to the Instructor 10 Organization 11 Acknowledgments 12 Introduction 14 Chapter 1. Integers 18 1. The Integers and the Well Ordering Property 18 2. Divisors and the Division Algorithm 19 3. Greatest Common Divisor and the Euclidean Algorithm 23 4. Prime Numbers and Unique Factorization 33 Exercises 41 Chapter 2. Modular Arithmetic 52 1. Basic Arithmetic 52 2. Inverses and Fermat’s Little Theorem 57 3. Linear Congruences and the Chinese Remainder Theorem 64 Exercises 70 Chapter 3. Quadratic Reciprocity and Primitive Roots 78 1. Quadratic Reciprocity 78 2. Computing mth Roots Modulo n 89 3. Existence of Primitive Roots 94 Exercises 98 Chapter 4. Secrets 104 1. Basic Ciphers 105 2. Symmetric Ciphers 108 3. Diffie–Hellman Key Exchange 110 4. Public Key Cryptography (RSA) 111 5. Hash Functions and Check Digits 114 6. Secret Sharing 117 Exercises 118 Chapter 5. Arithmetic Functions 122 1. Euler Totient Function 122 2. Möbius Function 126 3. Functions on Divisors 134 4. Partitions 143 Exercises 147 Chapter 6. Algebraic Numbers 156 1. Algebraic or Transcendental 156 2. Quadratic Number Fields and Norms 158 3. Integers, Divisibility, Primes, and Irreducibles 161 4. Application: Sums of Two Squares 165 Exercises 166 Chapter 7. Rational and Irrational Numbers 170 1. Diophantine Approximation 170 2. Height of a Rational Number 172 3. Heights and Approximations 175 4. Continued Fractions 179 5. Approximating Irrational Numbers with Convergents 184 Exercises 193 Chapter 8. Diophantine Equations 200 1. Introduction and Examples 200 2. Working Modulo Primes 202 3. Pythagorean Triples 211 4. Fermat’s Last Theorem 213 5. Pell’s Equation and Fundamental Units 215 6. Waring Problem 221 Exercises 225 Chapter 9. Elliptic Curves 234 1. Introduction 234 2. Addition of Points 237 3. Points of Finite Order 242 4. Integer Points and the Nagel–Lutz Theorem 243 5. Mordell–Weil Group and Points of Infinite Order 249 6. Application: Congruent Numbers 250 Exercises 253 Chapter 10. Dynamical Systems 260 1. Discrete Dynamical Systems 260 2. Dynatomic Polynomials 267 3. Resultant and Reduction Modulo Primes 271 4. Periods Modulo Primes 275 5. Algorithms for Rational Periodic and Preperiodic Points 279 Exercises 281 Chapter 11. Polynomials 288 1. Introduction to Polynomials 288 2. Factorization and the Euclidean Algorithm 291 3. Modular Arithmetic for Polynomials 295 4. Diophantine Equations for Polynomials 301 Exercises 306 Bibliography 312 List of Algorithms 316 List of Notation 318 Index 320 Back Cover 329