## Elementary Number Theory (110.304)

### Announcements:

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

12/19: Final exam solutions posted.

12/6: Reminder: The Final Exam is Wednesday, December 20, 2:00-5:00pm, Hodson 315.

12/6: Office hours for Final Exam: Tuesday December 19, 1:00-4:00pm, Krieger 412.

11/13: Reminder: Midterm II is Thursday, November 16.

11/13: Office hours for Midterm II: Wednesday November 15, 2:00-4:30pm, Krieger 412 (usual time but long hours).

10/4: Room change (tomorrow only): The classroom for tomorrow (October 5) will be Gilman 313, per registrar office.

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

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

9/26: 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/19: Office hours change: for tomorrow (9/20) only, office hours will be 3:00-4:30pm.

9/18: TA's office hours: Wednesday 6:00 -- 7:00 pm. Krieger 211

9/1: Room change: Please note the new classroom for 110.304 Fall 2017 is Hodson 315, effective from first meeting on Tuesday September 5.

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

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

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