## Elementary Number Theory (110.304)

### Announcements:

12/19: Course grades posted to SIS. Happy holidays!

12/19: Final exam solutions posted.

12/8: Extra office hours for the final exam: Thursday December15, 2-5pm.

12/8: Reminder: The Final Exam is Friday December  16, 9am-12noon in Gilman 55 (the regular classroom).

10/5: Extra office hours for Midterm I: Monday October 10, 2-4pm.

10/5: Reminder: Midterm I is on Tuesday October 11.

8/26: The first meeting is on Thursday September 1.

## Lecture Schedule and Assignment (This is tentative schedule. Check here for frequent updates.)

 Date Topic Sections Homework Due Date Week 1 Sep 1 Introduction Principle of mathematical induction 1.1 No assignment Week 2 Sep 15 Sep 6 Basis representation theorem Euclid's division lemma 1.2, 2.1 1.1: 2, 7, 10, 11, 13, 15 1.2: 6, 7 2.1: 2, 4, 5, 6 Sep 8 Divisibility 2,2 Week 3 Sep 22 Sep 13 Fundamental theorem of arithmetic 2.4 2.2: 2, 10, 11, 12 2.3: 1(b), 4 2.4: 6(f), 8, 10, 12 Sep 15 Linear Diophantine equations Permutations and combinations 2.3, 3.1 Week 4 Sep 29 Sep 20 Fermat's little theorem. Wilson's theorem 3.2, 3.3 3.1: 3, 6, 7, 10, 13, 14 3.2: 3, 6 3.3: 2 3.4: 3, 5 Sep 22 Generating functions 3.4 Week 5 Oct 6 Sep 27 Basic properties of Congruences Residue Systems 4.1, 4.2 4.1: 1(b), 6 4.2: 3 5.1: 1(c) 5.2: 3, 4, 6, 9, 11, 15, 21, 22 Sep 29 Solving Linear Congruences. Euler's Theorem. Fermat and Wilson Theorem (using congruences). 5.1, 5.2 Week 6 Oct 13 Oct 4 Chinese remainder theorem 5.3 5.3: 2, 4, 6 5.4: 3, 4, 5, 6, 7 Oct 6 Polynomial congruences Review 5.4 Week 7 Oct 27 Oct 11 Midterm I 6.1: 1, 4, 5, 8, 9, 10, 11, 15 Oct 13 Combinatorial study of φ(n) 6.1 Week 8 Oct 27 Oct 18 Formulae for d(n) and σ(n) Multiplicative arithmetic functions Möbius inversion formula 6.2, 6.3, 6.4 6.2: 2, 4, 5, 9, 15 6.3: 1 6.4: 2, 4, 5, 7, 8, 11, 12 Oct 20 No Class (classes meet on Monday schedule) Week 9 Nov 3 Oct 25 More on Möbius inversion formula Properties of reduced residue systems 6.4, 7.1 7.1: 6, 7 7.2: 7, 8, 9, 10, 11, 12, 13, 14 Oct 27 Primitive roots 7.2 Week 10 Nov 10 Oct 1 Elementary properties of π(x) 8.1 8.1: 1, 2, 5, 6, 7, 9, 10, 12, 16 8.2: 1, 7 Nov 3 Tchebychev's theorem 8.2 Week 11 Nov 17 Nov 8 Euler's criterion. Legendre Symbol 9.1, 9.2 9.1: 1 9.2: 1, 2, 3 9.3: 1, 2, 5, 6 9.4: 1, 3, 4, 5 Nov 10 Quadratic reciprocity law Applications of quadratic reciprocity law 9.3, 9.4 Week 12 Nov 15 Proof of quadratic reciprocity law. Review 9.3 No Assignment Nov 17 Midterm II Week 13 Nov 22 No Class (Thanksgiving holiday) No Assignment Nov 24 Week 14 Not Due Nov 29 Consecutive residues and non-residues 10.1 10.1: 1, 2, 3, 4, 5, 6, 7 11.1: 1, 2 11.2: 9 Dec 1 Consecutive triples of quadratic residues 10.2 Week 15 Dec 6 Sum of two squares 11.1 No Assignment Dec 8 Sum of four squares. Review 11.2