Introduction to Proof Through Number Theory

Pure and Applied Undergraduate Texts Volume: 61; 2023; 442 pp MSC: Primary 00; 03; 05; 11; 97; Secondary 68; Lighten up about mathematics! Have fun. If you read this book, you will have to endure bad math puns and jokes and out-of-date pop culture references. You'll learn some really cool mathematics to boot. In the process, you will immerse yourself in living, thinking, and breathing logical reasoning. We like to call this proofs, which to some is a bogey word, but to us it is a boogie word. You will learn how to solve problems, real and imagined. After all, math is a game where, although the rules are pretty much set, we are left to our imaginations to create. Think of this book as blueprints, but you are the architect of what structures you want to build. Make sure you lay a good foundation, for otherwise your buildings might fall down. To help you through this, we guide you to think and plan carefully. Our playground consists of basic math, with a loving emphasis on number theory. We will encounter the known and the unknown. Ancient and modern inquirers left us with elementary-sounding mathematical puzzles that are unsolved to this day. You will learn induction, logic, set theory, arithmetic, and algebra, and you may one day solve one of these puzzles. Readership Appropriate for a course serving as a transition to advanced mathematics and for undergraduate students interested in mathematical reasoning and an introduction to proofs. Cover 1 Title page 4 Contents 6 Preface 10 Philosophy about learning and teaching 10 Content of this book 11 Style of this book 12 Problem solving 12 LaTeX 13 Origins 13 Further reading 13 Acknowledgments 14 Notations and Symbols 16 Chapter 1. Evens, Odds, and Primes: A Taste of Number Theory 22 1.1. A first excursion into prime numbers 24 1.2. Even and odd integers 33 1.3. Calculating primes and the sieve of Eratosthenes 39 1.4. Division 44 1.5. Greatest common divisor 48 1.6. Statement of prime factorization 56 1.7*. Perfect numbers 60 1.8*. One of the Mersenne conjectures 61 1.9*. Twin primes: An excursion into the unknown 63 1.10*. Goldbach’s conjecture 64 1.11. Hints and partial solutions for the exercises 66 Chapter 2. Mathematical Induction 70 2.1. Mathematical induction 71 2.2. Rates of growth of functions 83 2.3. Sums of powers of the first n positive integers 90 2.4. Strong mathematical induction 99 2.5. Fibonacci numbers 103 2.6. Recursive definitions 112 2.7. Arithmetic and algebraic equalities and inequalities 116 2.8. Hints and partial solutions for the exercises 120 Chapter 3. Logic: Implications, Contrapositives, Contradictions, and Quantifiers 128 3.1. The need for rigor 129 3.2. Statements 134 3.3. Truth teller and liar riddle: Asking the right question 136 3.4*. Logic puzzles 137 3.5. Logical connectives 141 3.6. Implications 149 3.7. Contrapositive 155 3.8. Proof by contradiction 159 3.9. Pythagorean triples 166 3.10. Quantifiers 171 3.11. Hints and partial solutions for the exercises 177 Chapter 4. The Euclidean Algorithm and Its Consequences 182 4.1. The Division Theorem 182 4.2. There are an infinite number of primes 192 4.3. The Euclidean algorithm 194 4.4. Consequences of the Division Theorem 197 4.5. Solving linear Diophantine equations 203 4.6. “Practical” applications of solving linear Diophantine equations (wink \smiley) 208 4.7*. (Polynomial) Diophantine equations 209 4.8. The Fundamental Theorem of Arithmetic 211 4.9. The least common multiple 212 4.10. Residues modulo an odd prime 214 4.11. Appendix 215 4.12. Hints and partial solutions for the exercises 217 Chapter 5. Sets and Functions 224 5.1. Basics of set theory 225 5.2. Cartesian products of sets 235 5.3. Functions and their properties 246 5.4. Types of functions: Injections, surjections, and bijections 255 5.5. Arbitrary unions, intersections, and cartesian products 265 5.6*. Universal properties of surjections and injections 267 5.7. Hints and partial solutions for the exercises 268 Chapter 6. Modular Arithmetic 276 6.1. Multiples of 3 and 9 and the digits of a number in base 10 277 6.2. Congruence modulo m 278 6.3. Inverses, coprimeness, and congruence 287 6.4. Congruence and multiplicative cancellation 288 6.5*. Fun congruence facts 290 6.6. Solving linear congruence equations 291 6.7*. The Chinese Remainder Theorem 299 6.8. Quadratic residues 301 6.9. Fermat’s Little Theorem 305 6.10*. Euler’s totient function and Euler’s Theorem 310 6.11*. An application of Fermat’s Little Theorem: The RSA algorithm 315 6.12*. The Euclid–Euler Theorem characterizing even perfect numbers 316 6.13*. Twin prime pairs 320 6.14. Chameleons roaming around in a zoo 320 6.15. Hints and partial solutions for the exercises 323 Chapter 7. Counting Finite Sets 330 7.1. The addition principle 330 7.2. Cartesian products and the multiplication principle 333 7.3. The inclusion-exclusion principle 335 7.4. Binomial coefficients and the Binomial Theorem 343 7.5. Counting functions 365 7.6. Counting problems 371 7.7*. Using the idea of a bijection 374 7.8. Hints and partial solutions for the exercises 375 Chapter 8. Congruence Class Arithmetic, Groups, and Fields 382 8.1. Congruence classes modulo m 382 8.2. Inverses of congruence classes 390 8.3. Reprise of the proof of Fermat’s Little Theorem 393 8.4. Equivalence relations, equivalence classes, and partitions 395 8.5. Elementary abstract algebra 401 8.6. Rings, principal ideal domains, and all that 418 8.7. Fields 421 8.8*. Quadratic residues and the law of quadratic reciprocity 431 8.9. Hints and partial solutions for the exercises 446 Bibliography 456 Index 458 Back Cover 465