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.
Author(s): Benjamin Hutz
Series: Pure and Applied Undergraduate Texts 31
Publisher: American Mathematical Society
Year: 2018
Language: English
Pages: 329
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
