## Table of Contents

**0. SETS.**

** 1. Sets and Relations.**

** 2. Functions.**

** 3. Generalized Set Operations.**

**1. Elementary Properties of Integers.**

** 1. Introduction.**

** 2. Axioms for the Integers.**

** 3. Principle of Induction.**

** 4. Division.**

** 5. Representation.**

** 6. Congruence.**

** 7. Application: Random Keys.**

** 8. Application: Random Number Generation I.**

** 9. Application: Two's Complement.**

**2. PRIMES.**

** 1. Introduction.**

** 2. Prime Factorization.**

** 3. Distribution of the Primes.**

** 4. Elementary Algebraic Structures in Number Theory.**

** 5. Application: Pattern Matching.**

** 6. Application: Factoring by Pollard's r.**

**3. CONGRUENCES AND THE FUNCTION.**

** 1. Introduction.**

** 2. Chinese Remainder Theorem.**

** 3. Matrices and Simultaneous Equations.**

** 4. Polynomials and Solutions of Polynomial Congruences.**

** 5. Properties of the Function f**

** 6. The Order of an Integer.**

** 7. Primitive Roots.**

** 8. Indices.**

** 9. Quadratic Residues and the Law of Reciprocity.**

**10. Jacobi Symbol.**

**11. Application: Unit Orthogonal Matrices.**

**12. Application: Random Number Generation II.**

**13. Application: Hashing Functions.**

**14. Application: Indices.**

**15. Application: Cryptography.**

**16. Application: Primality Testing.**

**4. ARITHMETIC FUNCTIONS.**

** 1. Introduction.**

** 2. Multiplicative Functions.**

** 3. The Möbius Function.**

** 4. Generalized Möbius Function.**

** 5. Application: Inversions in Physics.**

**5. CONTINUED FRACTIONS.**

** 1. Introduction.**

** 2. Convergents.**

** 3. Simple Continued Fractions.**

** 4. Infinite Simple Continued Fractions.**

** 5. Pell's Equation.**

** 6. Application: Relative Rates.**

** 7. Application: Factoring.**

**6. BERTRAND'S POSTULATE.**

** 1. Introduction.**

** 2. Preliminaries.**

** 3. Bertrand's Postulate.**

**7. DIOPHANTINE EQUATIONS.**

** 1. Linear Diophantine Equations.**

** 2. Pythagorean triples.**

** 3. Integers as Sums of Two Squares.**

** 4. Quadratic Forms.**

** 5. Integers as Sums of Three Squares.**

** 6. Integers as Sums of Four Squares.**

** 7. The Equation ax**^{2} + by^{2} + cz = 0.

** 8. The Equation x**^{4} + y^{ 4} = z^{2}.

**APPENDIX A. LOGIC AND PROOFS.**

** 1. Axiomatic Systems.**

** 2. Propositional Calculus.**

** 3. Arguments.**

** 4. Predicate Calculus.**

** 5. Mathematical Proofs.**

**APPENDIX B. PEANO'S POSTULATES AND CONSTRUCTION OF THE INTEGERS.**

**APPENDIX C. POLYNOMIALS.**