Introduction to Proof Through Number Theory (Paperback)

Cover
Title page
Contents
Preface
Philosophy about learning and teaching
Content of this book
Style of this book
Problem solving
LaTeX
Origins
Further reading
Acknowledgments
Notations and Symbols
Chapter 1. Evens, Odds, and Primes: A Taste of Number Theory
1.1. A first excursion into prime numbers
1.2. Even and odd integers
1.3. Calculating primes and the sieve of Eratosthenes
1.4. Division
1.5. Greatest common divisor
1.6. Statement of prime factorization
1.7*. Perfect numbers
1.8*. One of the Mersenne conjectures
1.9*. Twin primes: An excursion into the unknown
1.10*. Goldbach’s conjecture
1.11. Hints and partial solutions for the exercises
Chapter 2. Mathematical Induction
2.1. Mathematical induction
2.2. Rates of growth of functions
2.3. Sums of powers of the first ?? positive integers
2.4. Strong mathematical induction
2.5. Fibonacci numbers
2.6. Recursive definitions
2.7. Arithmetic and algebraic equalities and inequalities
2.8. Hints and partial solutions for the exercises
Chapter 3. Logic: Implications, Contrapositives, Contradictions, and Quantifiers
3.1. The need for rigor
3.2. Statements
3.3. Truth teller and liar riddle: Asking the right question
3.4*. Logic puzzles
3.5. Logical connectives
3.6. Implications
3.7. Contrapositive
3.8. Proof by contradiction
3.9. Pythagorean triples
3.10. Quantifiers
3.11. Hints and partial solutions for the exercises
Chapter 4. The Euclidean Algorithm and Its Consequences
4.1. The Division Theorem
4.2. There are an infinite number of primes
4.3. The Euclidean algorithm
4.4. Consequences of the Division Theorem
4.5. Solving linear Diophantine equations
4.6. “Practical” applications of solving linear Diophantine equations (wink \smiley)
4.7*. (Polynomial) Diophantine equations
4.8. The Fundamental Theorem of Arithmetic
4.9. The least common multiple
4.10. Residues modulo an odd prime
4.11. Appendix
4.12. Hints and partial solutions for the exercises
Chapter 5. Sets and Functions
5.1. Basics of set theory
5.2. Cartesian products of sets
5.3. Functions and their properties
5.4. Types of functions: Injections, surjections, and bijections
5.5. Arbitrary unions, intersections, and cartesian products
5.6*. Universal properties of surjections and injections
5.7. Hints and partial solutions for the exercises
Chapter 6. Modular Arithmetic
6.1. Multiples of 3 and 9 and the digits of a number in base 10
6.2. Congruence modulo ??
6.3. Inverses, coprimeness, and congruence
6.4. Congruence and multiplicative cancellation
6.5*. Fun congruence facts
6.6. Solving linear congruence equations
6.7*. The Chinese Remainder Theorem
6.8. Quadratic residues
6.9. Fermat’s Little Theorem
6.10*. Euler’s totient function and Euler’s Theorem
6.11*. An application of Fermat’s Little Theorem: The RSA algorithm
6.12*. The Euclid?Euler Theorem characterizing even perfect numbers
6.13*. Twin prime pairs
6.14. Chameleons roaming around in a zoo
6.15. Hints and partial solutions for the exercises
Chapter 7. Counting Finite Sets
7.1. The addition principle
7.2. Cartesian products and the multiplication principle
7.3. The inclusion-exclusion principle
7.4. Binomial coefficients and the Binomial Theorem
7.5. Counting functions
7.6. Counting problems
7.7*. Using the idea of a bijection
7.8. Hints and partial solutions for the exercises
Chapter 8. Congruence Class Arithmetic, Groups, and Fields
8.1. Congruence classes modulo ??
8.2. Inverses of congruence classes
8.3. Reprise of the proof of Fermat’s Little Theorem
8.4. Equivalence relations, equivalence classes, and partitions
8.5. Elementary abstract algebra
8.6. Rings, principal ideal domains, and all that
8.7. Fields
8.8*. Quadratic residues and the law of quadratic reciprocity
8.9. Hints and partial solutions for the exercises
Bibliography
Index
Back Cover