## Elementary Number Theory (110.304)

### Announcements:

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

12/18: Final exam solutions posted.

12/4: Reminder: Final Exam is Monday, December 17, 2-5pm, Maryland 202.

12/4: Office hours for Final Exam: Friday December 14, 2:30-5:30pm, Krieger 412.

12/4: Reminder: TA's office hour this week was held on Monday (from email last week). There is no office hour for TA this Thursday.

11/13: Office hours for Midterm II: Wednesday November 14, 2:00-4:00pm, Krieger 412.

11/6: Reminder: Midterm II is next Thursday, November 15.

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

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

9/24: 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/17: Office hour change (this week only): This week's office hours will be Tuesday 9/18 (tomorrow) 2:00-3:30pm. There will be no office hours this Wednesday.

9/8: TA's office hour: Thursday 4:00-5:00pm in Krieger 211. Please note that the TA will also be in math Helproom Wednesday 5:00-7:00pm.

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

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

Midterm I Solution

Midterm II Solution

Final Exam Solution