Contents
CHAPTER1 Counting 31
1.1 Basic Counting 31
The Sum Principle 31
Abstraction 33
Summing Consecutive Integers 33
The Product Principle 34
Two-Element Subsets 36
Important Concepts, Formulas, and Theorems 37
Problems 38
1.2 Counting Lists, Permutations, and Subsets 40
Using the Sum and Product Principles 40
Lists and Functions 42
The Bijection Principle 44
k-Element Permutations of a Set 45
Counting Subsets of a Set 46
Important Concepts, Formulas, and Theorems 48
Problems 50
1.3 Binomial Coeffiients 52
Pascal’s Triangle 52
A Proof Using the Sum Principle 54
The Binomial Theorem 56
Labeling and Trinomial Coefficient 58
Important Concepts, Formulas, and Theorems 59
Problems 60
1.4 Relations 62
What Is a Relation? 62
Functions as Relations 63
Properties of Relations 63
Equivalence Relations 66
Partial and Total Orders 69
Important Concepts, Formulas, and Theorems 71
Problems 72
1.5 Using Equivalence Relationsin Counting 73
The Symmetry Principle
Equivalence Relations 75
The Quotient Principle 76
Equivalence Class Counting 76
Multisets 78
The Bookcase Arrangement Problem 80
The Number of k-Element Multisets of an n-Element Set 81
Usingthe Quotient Principle to Explain a Quotient 82
Important Concepts, Formulas, and Theorems 83
Problems 84
CHAPTER2 Cryptography and Number Theory 89
2.1 Cryptography and Modular Arithmetic 89
Introduction to Cryptography 89
Private-Key Cryptography 90
Public-Key Cryptosystems 93
Arithmetic Modulo n 95
Cryptography Using Addition mod n 98
Cryptography Using Multiplication mod n 99
Important Concepts, Formulas, and Theorems 101
Problems 102
2.2 Inverses and Greatest Common Divisors 105
Solutions to Equations and Inverses mod n 105
Inverses mod n 106
Converting Modular Equations to Normal Equations 109
Greatest Common Divisors 110
Euclid’s Division Theorem 111
Euclid’s GCD Algorithm 114
Extended GCD Algorithm 115
Computing Inverses 118
Important Concepts, Formulas, and Theorems 119
Problems 120
2.3 The RSA Cryptosystem 123
Exponentiation mod n 123
The Rules of Exponents 123
Fermat’s Little Theorem 126
The RSA Cryptosystem 127
The Chinese Remainder Theorem 131
Important Concepts, Formulas, and Theorems 132
Problems 134
2.4 Details of the RSA Cryptosystem 136
Practical Aspects of Exponentiation mod n 136
How Long Does It Take to Use the RSA Algorithm? 139
How Hard Is Factoring? 140
Finding Large Primes 140
Important Concepts, Formulas, and Theorems 143
Problems 144
CHAPTER3 Reflectionon Logic and Proof 147
3.1 Equivalence and Implication 147
Equivalence of Statements 147
Truth Tables 150
DeMorgan’s Laws 153
Implication 155
If and Only If 156
Important Concepts, Formulas, and Theorems 159
Problems 161
3.2 Variables and Quantifier 163
Variables and Universes 163
Quantifier 164
Standard Notation for Quantificatio 166
Statements about Variables 168
Rewriting Statements to Encompass Larger Universes 168
Proving Quantifie Statements Trueor False 169
Negation of Quantifie Statements 170
Implicit Quantificatio 173
Proof of Quantifie Statements 174
Important Concepts, Formulas, and Theorems 175
Problems 177
3.3 Inference 179
Direct Inference (Modus Ponens) and Proofs 179
Rules of Inference for Direct Proofs 181
Contrapositive Ruleof Inference 183
Proof by Contradiction 185
Important Concepts, Formulas, and Theorems 188
Problems 189
CHAPTER4 Induction, Recursion, and Recurrences 191
4.1 Mathematical Induction 191
Smallest Counterexamples 191
The Principle of Mathematical Induction 195
Strong Induction 199
Induction in General 201
A Recursive Viewof Induction 203
Structural Induction 206
Important Concepts, Formulas, and Theorems 208
Problems 210
4.2 Recursion, Recurrences, and Induction 213
Recursion 213
Examples of First-Order Linear Recurrences 215
Iteratinga Recurrence 217
Geometric Series 218
First-Order Linear Recurrences 221
Important Concepts,
鄂公网安备 42010302001612号 