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 Programmingprovides 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 Programmingfeatures 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:

Elementary Number Theory with Programmingis 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.

Marty Lewinter, PhD, is Professor Emeritus of Mathematics at the State University of New York, Purchase College. The author of three books and more than 80 articles, he is Executive Director of Mathematics at American Digital University Services.

Jeanine Meyer, PhD, is Professor of Mathematics/Computer Science at the State University of New York, Purchase College. She is the author of six books as well as numerous journal articles.

Preface xi

Words xiii

Notation in Mathematical Writing and in Programming xv

1 Special Numbers: Triangular, Oblong, Perfect, Deficient, and Abundant 1
The programs include one for factoring numbers and one to test a conjecture up to a fixed limit.

Triangular Numbers 1

Oblong Numbers and Squares 3

Deficient, Abundant, and Perfect Numbers 4

Exercises 7

2 Fibonacci Sequence, Primes, and the Pell Equation 13
The programs include examples that count steps to compare two different approaches.

Prime Numbers and Proof by Contradiction 13

Proof by Construction 17

Sums of Two Squares 18

Building a Proof on Prior Assertions 18

Sigma Notation 19

Some Sums 19

Finding Arithmetic Functions 20

Fibonacci Numbers 22

An Infinite Product 26

The Pell Equation 26

Goldbachs Conjecture 30

Exercises 31

3 Pascals Triangle 44
The programs include examples that generate factorial using iteration and using recursion and thus demonstrate and compare important techniques in programming.

Factorials 44

The Combinatorial NumbersnChoosek46

Pascals Triangle 48

Binomial Coefficients 50

Exercises 50

4 Divisors and Prime Decomposition 56
The programs include one that uses the algorithm to produce the GCD of a pair of numbers and a program to produce the prime decomposition of a number.

Divisors 56

Greatest Common Divisor 58

Diophantine Equations 65

Least Common Multiple 67

Prime Decomposition 68

Semiprime Numbers 70

When is a Number anmth Power? 71

Twin Primes 73

Fermat Primes 73

Odd Primes Are Differences of Squares 74

When isna Linear Combination ofaandb? 75

Prime Decomposition ofn! 76

No Nonconstant Polynomial with Integer Coefficients Assumes Only Prime Values 77

Exercises 78

5 Modular Arithmetic 85
One program checks if a mod equation is true, and another determines the solvability of a mod equation and then solves an equation that is solvable by a brute-force approach.

Congruence Classes Modk85

Laws of Modular Arithmetic 87

Modular Equations 90

Fermats Little Theorem 91

Fermats Little Theorem 92

Multiplicative Inverses 92

Wilsons Theorem 93

Wilsons Theorem 95

Wilsons Theorem (2nd Version) 95

Squares and Quadratic Residues 96

Lagranges Theorem 98

Lagranges Theorem 99

Reduced Pythagorean Triples 100

Chinese Remainder Theorem 102

Chinese Remainder Theorem 103

Exercises 104

6 Number Theoretic Functions 111
The programs include two distinct approaches to calculating the tau function.

TheTauFunction 111

TheSigmaFunction 114

Multiplicative Functions 115

Perfect Numbers Revisited 115

Mersenne Primes 116

F(n) = f(d) Wheredis a Divisor ofn117

The Möbius Function 119

The Riemann Zeta Function 121

Exercises 124

7 The Euler Phi Function 134
The programs demonstrate two approaches to calculating the phi function.

ThePhiFunction 134

Eulers Generalization of Fermats Little Theorem 138

Phi of a Product ofmandnWhengcd(m,n)> 1 139

The Order ofa(mod n) 139

Primitive Roots 140

The Index ofm(mod p) Relative toa141

To Be or Not to Be a Quadratic Residue 145

The Legendre Symbol 146

Quadratic Reciprocity 147

Law of Quadratic Reciprocity 148

When Doesx2 =a(mod n) Have a Solution? 148

Exercises 150

8 Sums and Partitions 158
The exposition explains the central role of binary representation in computing and the programs produce the binary partition using a built-in function.

Annth Power is the Sum of Two Squares 158

Solutions to the Diophantine Equationa2 +b2 +c2 =d2 159

Row Sums of a Triangular Array of Consecutive Odd Numbers 160

Partitions 160

When is a Number the Sum of Two Squares? 167

Sums of Four or Fewer Squares 170

Exercises 175

9 Cryptography 182
The programs include different ways to generate counts of letters and also Fermat factoring.

Introduction and History 182

Public-Key Cryptography 187

Factoring Large Numbers 188

The Knapsack Problem 191

Superincreasing Sequences 192

Exercises 194

Answers or Hints to Selected Exercises 203

Index 207