## Syllabus

The following is a tentative syllabus for the course.

Week Lectures Sections in Text Brief Description Suggested Practice
1 9/16 1.1 Introduction, Division and Euclidean Algorithms Prove divisibility facts 5, 7, and 9.
Read over the proof of Thm 1.1 in the text, and note any questions you have.
9/18 1.2, 1.3 Bezout's identity, least common multiples Write gcd(1485, 1745) in the form 1485u+1745v. Find lcm(1485, 1745).
Show that c|a and c|b iff c|gcd(a,b).
9/20 1.3, 1.4 LCMs, Linear Diophantine Equations Find the general solution to 1066x+1492y=8.
Exercise 1.25 on p. 17 of the text.
2 9/23 2.1, 2.2 Fundamental Theorem of Arithmetic, Distribution of primes Prove the following: if a positive integer n is not a perfect square, then the square root of n is an irrational number.
9/24 (x-hour) Appendix A Induction practice Solutions to practice problems
9/25 2.2, 2.4 Distribution of primes, primality testing Exercise 2.7 on p.29 of the text.
Use the Sieve of Eratosthenes to find all the primes less than 100.
9/27 3.1 Modular arithmetic Find the least absolute and least non-negative residues of 19*14 mod (23). // Prove the divisibility rule for 5.
3 9/30 3.2 Linear Congruences (Clarification) Exercise 3.7 on p.52 of the text.
10/1 (x-hour) 10 ways Proof techniques Solutions to practice problems
10/2 3.3, 3.4 Chinese Remainder Theorem Exercises 3.9, 3.11, and 3.12 on p.55-57 of the text.
10/4 No class today
4 10/7 3.4, 4.1 CRT, arithmetic modulo p Exercises 3.18 and 3.20 on p.63 of the text.
Exercise 4.1 on p.67 of the text.
10/9 Exam 1 in-class portion Material through Section 3.4. Take home portion due 10/11.
10/11 4.1, 4.2 Pseudoprimes and Carmichael Numbers Exercises 4.4 and 4.5 on p. 73 of the text.
5 10/14 5.1, Appendix B Units and groups
10/15 (x-hour) 5.2, class notes Euler's function, intro to cryptography Try out some examples with p=5 and q=7.
10/16 class notes More cryptography, RSA Exercise 5.7 on p.90 of the text.
10/18 6.1, 6.2 The group of units and primitive roots Exercise 6.26(b) on p.118 of the text.
Exercise 6.5 on p.101 of the text.
6 10/21 6.3-6.5 Primitive roots for composite moduli Read the proof of Theorem 6.7.
Exercise 6.10 on p. 106 of the text.
10/23 6.6 Applications of primitive roots Exercise 6.16 on p. 112 of the text.
10/25 7.1, 7.2 Quadratic residues Exercise 7.4 on p. 121 of the text.
Find the set of quadratic residues mod 60.
7 10/28 7.3 The Legendre symbol and properties Determine if  is a quadratic residue mod 41.
Determine if [-2] is a quadratic residue mod 29.
10/30 Exam 2 in-class portion Material through Section 6.6. Take home portion due 11/1.
11/1 7.3 Gauss's Lemma Exercise 7.10 on p.129 of the text.
8 11/4 7.4 Quadratic reciprocity Exercise 7.12 on p.132 of the text.
Read the proof of Theorem 7.11 on p.133 of the text.
11/5 (x-hour) 8.1, 8.2 Arithmetic functions Exercise 8.1 on p. 144 of the text.
Exercise 8.5 on p. 147 of the text.
11/6 8.3-8.5 The Mobius function Exercise 8.15 on p. 156 of the text.
11/8 8.6, 9.1, class notes The Dirichlet product, the Riemann Zeta function Note: This material is not covered on the final exam.
9 11/11 11.1-11.5 Fermat's last theorem and Pythagorean triples Exercises on p.220 of the text.