## Elementary Number Theory (110.304)

### Announcements:

15/17: Course grades posted to SIS. Have a great summer!

5/17: Final exam solution posted.

5/1: Office hours for Final Exam: Tuesday May 15, 1:00-4:00pm, Krieger 412.

5/1: Reminder: The Final Exam is Wednesday, May 16, 9:00 am -12:00 noon, Maryland 104.

4/17: Office hours for Midterm II:  Wednesday April 18 2-4:30pm.

4/10: Reminder: Midterm II is on Thursday April 19.

3/6: Office hours change for Wednesday 3/7 only: 12-1pm.

2/28: Reminder: Midterm I is on Tuesday March 6.

2/20: 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.

2/7: TA's office hours: Tuesday 1-2pm. Krieger 211.

1/16: The first meeting of this class is on Tuesday January 30.

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

 Date Topic Sections Homework Due Date Week 1 Feb 8 Jan 30 Introduction. Mathematical Induction 1.1 1.1: 1, 7, 10, 11, 13, 15 1.2: 6, 7 2.1: 2, 4, 5 Feb 1 Basis representation theorem Euclid's division lemma 1.2, 2.1 Week 2 Feb 15 Feb 6 Divisibility 2.2 2.2: 2, 10, 11, 12 2.3: 1(d), 4 2.4: 6(f), 8, 10, 12 Feb 8 Linear Diophantine equations Fundamental theorem of arithmetic 2.3, 2.4 Week 3 Feb 22 Feb 13 Permutations and combinations Fermat's Theorem 3.1, 3.2 3.1: 3, 6, 7, 13, 14 3.2: 3, 6 3.3: 1, 2 3.4: 3, 5 Feb 15 Wilson's theorem Generating functions 3,3, 3.4 Week 4 Mar 1 Feb 20 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, 5, 9, 11, 15, 21, 23 Feb 22 Solving Linear Congruences Euler's Theorem. Fermat and Wilson Theorem (using congruences). 5.1, 5.2 Week 5 Mar 8 Feb 27 Chinese remainder theorem 5.3 5.3: 2, 4, 6 5.4: 3, 4, 5, 6, 7 Mar 1 Polynomial congruences Review 5.4 Week 6 Mar 15 Mar 6 Midterm I 6.1: 1, 4, 5, 8, 9, 10, 11, 13 Mar 8 Combinatorial study of φ(n) 6.1 Week 7 Mar 29 Mar 13 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, 11, 12 Mar 15 Möbius inversion formula 6.4 Week 8 Mar 20 No Class (spring break) Mar 22 Week 9 Apr 5 Mar 27 Properties of reduced residue systems 7.1 7.1: 6, 7 7.2: 7, 8, 9, 10, 11, 12, 13, 14 Mar 29 Primitive Roots 7.2 Week 10 Apr 12 Apr 3 Elementary properties of π(x) 8.1 8.1: 1, 2, 5, 6, 7, 10, 12, 16 8.2: 1, 7 Apr 5 Tchebychev's theorem Quadratic Residues 8.2, 9.1 Week 11 Apr 19 Apr 10 Legendre Symbol. Gauss's Lemma Quadratic reciprocity law 9.2, 9.3 9.1: 1 9.2: 1, 2, 3 9.3: 5, 6 9.4: 1, 3, 4, 5 Apr 12 Applications of quadratic reciprocity law 9.4 Week 12 Apr 26 (Last HW Due) Apr 17 Proof of quadratic reciprocity law Review 9.3 10.1: 3, 4, 5, 6, 7 Apr 19 Midterm II Week 13 Not Due Apr 24 Consecutive residues and non-residues 10.1 10.2: 2 11.1: 1, 2 11.2: 9 Apr 26 Consecutive triples of quadratic residues 10.2 Week 14 May 1 Sum of two squares 11.1 May 3 Sum of four squares Review 11.2

Midterm I Solution

Midterm 2 Solution

Final Exam Solution