Description
Book SynopsisA 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.
Trade Review"It consists of nine chapters, all including the corresponding programs along with their mathematical content. The mathematical structure is also interesting and well-formed starting from special numbers, primes and Pell equation, to Pascal's triangle, prime decomposition and modular arithmetic and finishing with number-theoretic functions, the Euler Phi-function, sums and partitions and the classical application to cryptography. It is also remarkable that the main scope of the programs is defined before their use from the reader, providing him the best orientation for his study." (Zentralblatt MATH 2016)
Table of ContentsPreface 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
Goldbach’s Conjecture 30
Exercises 31
3 Pascal’s 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 Numbers n Choose k 46
Pascal’s 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 an mth Power? 71
Twin Primes 73
Fermat Primes 73
Odd Primes Are Differences of Squares 74
When is n a Linear Combination of a and b? 75
Prime Decomposition of n! 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 Mod k 85
Laws of Modular Arithmetic 87
Modular Equations 90
Fermat’s Little Theorem 91
Fermat’s Little Theorem 92
Multiplicative Inverses 92
Wilson’s Theorem 93
Wilson’s Theorem 95
Wilson’s Theorem (2nd Version) 95
Squares and Quadratic Residues 96
Lagrange’s Theorem 98
Lagrange’s 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.
The Tau Function 111
The Sigma Function 114
Multiplicative Functions 115
Perfect Numbers Revisited 115
Mersenne Primes 116
F(n) = Σf(d) Where d is a Divisor of n 117
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.
The Phi Function 134
Euler’s Generalization of Fermat’s Little Theorem 138
Phi of a Product of m and n When gcd(m,n) > 1 139
The Order of a (mod n) 139
Primitive Roots 140
The Index of m (mod p) Relative to a 141
To Be or Not to Be a Quadratic Residue 145
The Legendre Symbol 146
Quadratic Reciprocity 147
Law of Quadratic Reciprocity 148
When Does x2 = 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.
An nth Power is the Sum of Two Squares 158
Solutions to the Diophantine Equation a2 + 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
