An Experimental Introduction to Number Theory

Description

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