## Elementary Number Theory (110.304)

### Announcements:

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

12/18: Final exam solutions posted.

12/3: Reminder: Final Exam is Tuesday December 17 at 6-9pm (note the night exam time).

12/3: Extra office hours for Final Exam: Monday December 16, 4:00-6:00pm, Krieger 412.

11/5: Reminder: Midterm II is next Thursday, November 14.

10/1: Extra office hours for Midterm I: Monday October 8, 2:00-3:30pm, Krieger 412.

10/1: Reminder: Midterm I is next Tuesday, October 9.

9/30: TA's new hours in Math Helproom will be Thursday 7-9pm. Also you can usually find him in his office (Krieger 201) Tuesday 3-4pm.

9/23: For homework problem #14 in 3.1, here is a (3-part) help video if you use induction. Note that there are other ways without using induction.

9/6: TA's office hours: Thursday 4-5pm, Krieger 201. TA also will be in Math Helproom Tuesday 3-5pm.

8/16: Please note that on the first class day August 29, classes meet according to Monday schedule. The first meeting of this class is on Tuesday September 3.

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

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