## Elementary Number Theory (110.304)

### Announcements:

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

5/17: Final exam solution posted.

5/1: Office hours for Final Exam: Wednesday May 15, 3:30-5:30pm, Krieger 412.

5/1: Reminder: The Final Exam is Thursday, May 16, 2:00--5:00pm.

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

4/15: Reminder: Midterm II is on Thursday April 18.

2/28: Extra office hours for Midterm I: Monday March 4, 2-3:30pm.

2/26: Reminder: Midterm I is next Tuesday March 5.

2/19: 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/12: School opens at 10am. No class today (Read 3.2 and 3.3).

2/4: TA's office hours: Monday 11:00am-12:00pm.

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

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

 Date Topic Sections Homework Due Date Week 1 Feb 7 Jan 29 Introduction. Mathematical Induction 1.1 1.1: 1, 8, 10, 12, 13, 15 1.2: 6, 7 2.1: 2, 4, 5 Jan 31 Basis representation theorem Euclid's division lemma 1.2, 2.1 Week 2 Feb 14 Feb 5 Divisibility 2.2 2.2: 2, 4, 10, 11, 12 2.3: 1(d), 4 2.4: 8, 10, 12 Feb 7 Linear Diophantine equations Fundamental theorem of arithmetic Permutations and combinations 2.3, 2.4, 3.1 Week 3 Feb 21 Feb 12 No class (school opens at 10am). Read 3.2 and 3.3 3.1: 3, 6, 7, 10, 13, 14 3.2: 3, 6 3.3: 2 3.4: 3, 5 Feb 14 Fermat's Theorem. Wilson's theorem Generating functions 3.2, 3.3, 3.4 Week 4 Feb 28 Feb 19 Basic properties of Congruences Residue Systems 4.1, 4.2 4.1: 6 4.2: 3 5.1: 1(b), 3 5.2: 3, 4, 6, 9, 11, 15, 21, 23 Feb 21 Solving Linear Congruences Euler's Theorem. Fermat and Wilson Theorem (using congruences). 5.1, 5.2 Week 5 Mar 7 Feb 26 Chinese remainder theorem Polynomial congruences 5.3 5.3: 2, 5, 6 5.4: 1(a), 3, 4, 5, 6 Feb 28 Review 5.4 Week 6 Mar 14 Mar 5 Midterm I 6.1: 1, 2, 4, 5, 8, 9, 10, 11, 13 Mar 7 Combinatorial study of φ(n) 6.1 Week 7 Mar 28 Mar 12 Formulae for d(n) and σ(n) Multiplicative arithmetic functions 6.2, 6.3 6.2: 2, 5, 9, 15 6.3: 1 6.4: 2, 4, 5, 7, 10, 11, 12 Mar 14 Möbius inversion formula 6.4 Week 8 Mar 19 No Class (spring break) Mar 21 Week 9 Apr 4 Mar 26 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 Mar 28 Elementary properties of π(x) 8.1 Week 10 Apr 11 Apr 2 Tchebychev's theorem 8.2 8.1: 1, 2, 3, 5, 6, 7, 10, 13, 16 8.2: 1 Apr 4 Quadratic Residues. Legendre Symbol 9.1, 9.2 Week 11 Apr 18 Apr 9 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 Apr 11 Applications of quadratic reciprocity law 9.3, 9.4 Week 12 Apr 25 (Last HW Due) Apr 16 Consecutive residues and non-residues Review 10.1 10.1: 3, 4, 5, 6, 7 Apr 18 Midterm II Week 13 Not Due Apr 23 Consecutive triples of quadratic residues 10.2 10.2: 2 11.1: 1 11.2: 9 Apr 25 Sum of two squares 11.1 Week 14 Apr 30 Sum of four squares 11.2 May 2 Review

Midterm I solution

Midterm II solution

Final Exam solution