Preface.

To the Student.

To the Instructor.

Acknowledgements.

**0. Prologue.**

**1. Numbers, Rational and Irrational.**

(Historical figures: Pythagoras and Hypatia).

1.1 Numbers and the Greeks.

1.2 Numbers you know.

1.3 A First Look at Proofs.

1.4 Irrationality of he square root of 2.

1.5 Using Quantifiers.

**2. Mathematical Induction.**

(Historical figure: Noether).

2.1.The Principle of Mathematical Induction.

2.2 Strong Induction and the Well Ordering Principle.

2.3 The Fibonacci Sequence and the Golden Ratio.

2.4 The Legend of the Golden Ratio.

**3. Divisibility and Primes.**

(Historical figure: Eratosthenes).

3.1 Basic Properties of Divisibility.

3.2 Prime and Composite Numbers.

3.3 Patterns in the Primes.

3.4 Common Divisors and Common Multiples.

3.5 The Division Theorem.

3.6 Applications of gcd and lcm.

**4.The Euclidean Algorithm.**

(Historical figure: Euclid).

4.1 The Euclidean Algorithm.

4.2 Finding the Greatest Common Divisor.

4.3 A Greeker Argument that the square root of 2 is Irrational.

**5. Linear Diophantine Equations.**

(Historical figure: Diophantus).

5.1 The Equation *aX* + *bY* = 1.

5.2 Using the Euclidean Algorithm to Find a Solution.

5.3 The Diophantine Equation *aX + bY = n.*

5.4 Finding All Solutions to a Linear Diophantine Equation.

**6. The Fundamental Theorem of Arithmetic.**

(Historical figure: Mersenne).

6.1 The Fundamental Theorem.

6.2 Consequences of the Fundamental Theorem.

**7. Modular Arithmetic.**

(Historical figure: Gauss).

7.1 Congruence modulo *n.*

7.2 Arithmetic with Congruences.

7.3 Check Digit Schemes.

7.4 The Chinese Remainder Theorem.

7.5 The Gregorian Calendar.

7.6 The Mayan Calendar.

**8. Modular Number Systems.**

(Historical figure: Turing).

8.1 The Number System **Z**_{n}: an Informal View.

8.2 The Number System **Z**_{n}: Definition and Basic Properties.

8.3 Multiplicative Inverses in **Z**_{n}.

8.4 Elementary Cryptography.

8.5 Encryption Using Modular Multiplication.

**9. Exponents Modulo ***n*.

(Historical figure: Fermat).

9.1 Fermat's Little Theorem.

9.2 Reduced Residues and the Euler phi-function.

9.3 Euler's Theorem.

9.4 Exponentiation Ciphers with a Prime modulus.

9.5 The RSA Encryption Algorithm.

**10. Primitive Roots.**

(Historical figure: Lagrange).

10.1 **Z**_{n}.

10.2 Solving Polynomial Equations in **Z**_{n}.

10.3 Primitive Roots.

10.4 Applications of Primitive Roots.

**11. Quadratic Residues.**

(Historical figure: Eisenstein)

11.1 Squares Modulo *n*

11.2 Euler's Identity and the Quadratic Character of -1

11.3 The Law of Quadratic Reciprocity

11.4 Gauss's Lemma

11.5 Quadratic Residues and Lattice Points.

11.6 The Proof of Quadratic Reciprocity.

**12. Primality Testing.**

(Historical figure: Erdös).

12.1 Primality testing.

12.2 Continued Consideration of Charmichael Numbers.

12.3 The Miller-Rabin Primality test.

12.4 Two Special Polynomial Equations in *Z*_{p}.

12.5 Proof that Millar-Rabin is Effective.

12.6 Prime Certificates.

12.7 The AKS Deterministic Primality Test.

**13. Gaussian Integers.**

(Historical figure: Euler).

13.1 Definition of Gaussian Integers

13.2 Divisibility and Primes in **Z**[*i*].

13.3 The Division Theorem for the Gaussian Integers.

13.4 Unique Factorization in **Z**[*i*].

13.5 Gaussian Primes.

13.6 Fermat's Two Squares Theorem.

**14. Continued Fractions.**

(Historical figure: Ramanujan).

14.1 Expressing Rational Numbers as Continued Fractions.

14.2 Expressing Irrational Numbers as Continued Fractions.

14.3 Approximating Irrational Numbers Using Continued Fractions.

14.4 Proving that Convergents are Fantastic Approximations.

**15. Some Nonlinear Diophantine Equations.**

(Historical figure: Germain).

15.1 Pell's Equation

15.2 Fermat's Last Theorem

15.3 Proof of Fermat's Last Theorem for n = 4.

15.4 Germain's Contributions to Fermat's Last Theorem

15.5 A Geometric look at the Equation x^{4} + y^{4} = z^{2}.

**Appendix: Axioms of Number Theory.**

A.1 What is a Number System?

A.2 Order Properties of the Integers.

A.3 Building Results From Our Axioms.

A.4 The Principle of Mathematical Induction.