Elementary Number Theory with Programming

**A highly successful presentation of the fundamental concepts of number theory and computer programming** Bridging an existing gap between mathematics and programming, __Elementary Number Theory with Programming__ provides a unique introduction to elementary number theory with fundamental coverage of computer programming. Written by highly-qualified experts in the fields of computer science and mathematics, the book features accessible coverage for readers with various levels of experience and explores number theory in the context of programming without relying on advanced prerequisite knowledge and concepts in either area. __Elementary Number Theory with Programming__ features comprehensive coverage of the methodology and applications of the most well-known theorems, problems, and concepts in number theory. Using standard mathematical applications within the programming field, the book presents modular arithmetic and prime decomposition, which are the basis of the public-private key system of cryptography. In addition, the book includes: * Numerous examples, exercises, and research challenges in each chapter to encourage readers to work through the discussed concepts and ideas * Select solutions to the chapter exercises in an appendix * Plentiful sample computer programs to aid comprehension of the presented material for readers who have either never done any programming or need to improve their existing skill set * A related website with links to select exercises * An Instructor’s Solutions Manual available on a companion website __Elementary Number Theory with Programming__ is a useful textbook for undergraduate and graduate-level students majoring in mathematics or computer science, as well as an excellent supplement for teachers and students who would like to better understand and appreciate number theory and computer programming. The book is also an ideal reference for computer scientists, programmers, and researchers interested in the mathematical applications of programming. Title Page 5 Copyright Page 6 Contents 9 Preface 13 Words 15 Notation in Mathematical Writing and in Programming 17 Chapter 1 Special Numbers 21 Triangular Numbers 21 Oblong Numbers and Squares 23 Deficient, Abundant, and Perfect Numbers 24 Exercises 27 Chapter 2 Fibonacci Sequence, Primes, and the Pell Equation 33 Prime Numbers and Proof by Contradiction 33 Proof by Construction 37 Sums of Two Squares 38 Building a Proof on Prior Assertions 38 Sigma Notation 39 Some Sums 39 Finding Arithmetic Functions 40 Fibonacci Numbers 42 An Infinite Product 46 The Pell Equation 46 Goldbach ́s Conjecture 50 Exercises 51 Chapter 3 Pascal ́s Triangle 64 Factorials 64 The Combinatorial Numbers n Choose k 66 Pascal ́s Triangle 68 Binomial Coefficients 70 Exercises 70 Chapter 4 Divisors and Prime Decomposition 76 Divisors 76 Greatest Common Divisor 78 Diophantine Equations 85 Least Common Multiple 87 Prime Decomposition 88 Semiprime Numbers 90 When Is a Number an mth Power? 91 Twin Primes 93 Fermat Primes 93 Odd Primes Are Differences of Squares 94 When Is n a Linear Combination of a and b? 95 Prime Decomposition of n! 96 No Nonconstant Polynomial with Integer Coefficients Assumes Only Prime Values 97 Exercises 98 Chapter 5 Modular Arithmetic 105 Congruence Classes Mod k 105 Laws of Modular Arithmetic 107 Modular Equations 110 Fermat ́s Little Theorem 111 Fermat ́s Little Theorem 112 Multiplicative Inverses 112 Wilson ́s Theorem 113 Wilson ́s Theorem 115 Wilson’s Theorem (2nd Version) 115 Squares and Quadratic Residues 116 Lagrange ́s Theorem 118 Lagrange’s Theorem 119 Reduced Pythagorean Triples 120 Chinese Remainder Theorem 122 Chinese Remainder Theorem 123 Exercises 124 Chapter 6 Number Theoretic Functions 131 The Tau Function 131 The Sigma Function 134 Multiplicative Functions 135 Perfect Numbers Revisited 135 Mersenne Primes 136 F(n)=Sigmaf(d) Where d Is a Divisor of n 137 The Möbius Function 139 The Riemann Zeta Function 141 Exercises 144 Chapter 7 The Euler Phi Function 154 The Phi Function 154 Euler ́s Generalization of Fermat ́s Little Theorem 158 Phi of a Product of m and n When gcd(m,n)>1 159 The Order of a (mod n) 159 Primitive Roots 160 The Index of m (mod p) Relative to a 161 To Be or Not to Be a Quadratic Residue 165 The Legendre Symbol 166 Quadratic Reciprocity 167 When Does x2=a (mod n) Have a Solution? 168 Exercises 170 Chapter 8 Sums and Partitions 178 An nth Power Is the Sum of Two Squares 178 Solutions to the Diophantine Equation a2+b2+c2=d2 179 Row Sums of a Triangular Array of Consecutive Odd Numbers 180 Partitions 180 When Is a Number the Sum of Two Squares? 187 Sums of Four or Fewer Squares 190 Exercises 195 Chapter 9 Cryptography 202 Introduction and History 202 Public-Key Cryptography 207 Factoring Large Numbers 208 The Knapsack Problem 211 Superincreasing Sequences 212 Exercises 214 Answers or Hints to Selected Exercises 223 Chapter 1 223 Chapter 2 224 Chapter 3 224 Chapter 4 224 Chapter 5 225 Chapter 6 225 Chapter 7 226 Chapter 8 226 Chapter 9 226 Index 227 EULA 231 A successful presentation of the fundamental concepts of number theory and computer programming Bridging an existing gap between mathematics and programming, Elementary Number Theory with Programming provides a unique introduction to elementary number theory with fundamental coverage of computer programming. Written by highly-qualified experts in the fields of computer science and mathematics, the book features accessible coverage for readers with various levels of experience and explores number theory in the context of programming without relying on advanced prerequisite knowledge and concepts in either area. Elementary Number Theory with Programming features comprehensive coverage of the methodology and applications of the most well-known theorems, problems, and concepts in number theory. Using standard mathematical applications within the programming field, the book presents triangle numbers and prime decomposition, which are the basis of the public-private key system of cryptography. In addition, the book includes: Numerous examples, exercises, and research challenges in each chapter to encourage readers to work through the discussed concepts and ideas Select solutions to the chapter exercises in an appendix Plentiful sample computer programs to aid comprehension of the presented material for readers who have either never done any programming or need to improve their existing skill set A related website with links to select exercises An Instructor’s Solutions Manual available on a companion website Elementary Number Theory with Programming is a useful textbook for undergraduate and graduate-level students majoring in mathematics or computer science, as well as an excellent supplement for teachers and students who would like to better understand and appreciate number theory and computer programming. The book is also an ideal reference for computer scientists, programmers, and researchers interested in the mathematical applications of programming. Filling a much-needed gap in the current literature, this book expertly bridges the subjects of number theory and programming and features a multitude of examples and programming exercises in each chapter. It provides an introduction to elementary number theory with fundamental coverage of computer programming and is appropriate for students of mathematics and computer science alike who need to become acquainted with the most famous theorems, problems, and concepts of number theory. In addition, the authors provide a ..