Math 312 • Introduction to Number Theory • UBC, Fall 2014

**Lectures: ** MWF 11:00-12:00 in LSK 460

**Office hours: ** MW 9:50-10:50 and by appointment, LSK 300C

**Instructor: ** Laura Peskin, lpeskin at math dot ubc dot ca

**Grader: ** Zoe Hamel, zhamel at math dot ubc dot ca

**Textbook: ** Rosen, * Elementary Number Theory & Its Applications*, 6th ed.

Jump to:

Syllabus and Course Policies -- updated 9.2

Announcements -- updated 9.12

Assignments --updated 9.17

Schedule -- updated 9.17

- 9.12: Zoe Hamel, our TA, will be in the Math Learning Centre 5pm-7pm on Tuesdays and 2:30-4:30pm on Wednesdays.
- 9.4: The content of the 5th edition of the textbook is similar enough that it should be OK, but it's your responsibility to make sure that you are reading the correct sections.
- 9.3: If you need help with registration, please see this page for instructions.
- 9.3: If you need to arrange accommodations for a disability/difference (e.g., taking exams at the Access & Diversity Center), please let me know as soon as possible.
- 9.3: The midterm exam dates for this course are
**Thurs, Oct. 9**and**Thurs, Nov. 6**, both exams 6:30--7:30pm in 202 Macleod. Please double-check these dates against the exam dates for your other courses and let me know ASAP if you have a conflicting exam.

Grades will be calculated using the following formula: 20% weekly homeworks, 30% midterm exams (two exams, weighted equally), 50% final exam. The two lowest homework scores will be dropped. See the course syllabus for policies on collaboration, exams, and late work/absences.

Assignments are due on Wednesdays at 11am in class. No late homework will be accepted. The lowest two scores will be dropped.

# | Due date | Assignment | Grading scheme | Solutions |
---|---|---|---|---|

1 | 9.10 | Homework 1 | 5 pts each for #2, #4, #10 5 pts for completeness |
Solutions to HW 1 |

2 | 9.17 | Homework 2 | ||

3 | 9.24 | Homework 3 | ||

4 | 10.1 | |||

5 | 10.8 | |||

6 | 10.15 | |||

7 | 10.22 | |||

8 | 10.29 | |||

9 | 11.5 | |||

10 | 11.12 | |||

11 | 11.19 | |||

12 | 11.26 |

''Through'' means ''up to and including''; for example ''§3.1 through Example 3.3'' means ''§3.1 up to the end of Example 3.3.''

Week | Date | Topics | Required reading | In-class exercise | Optional reading | Comments |
---|---|---|---|---|---|---|

1 | 9.3 | Course overview & policies; survey | Course syllabus Abbreviations |
Survey | ||

9.5 | Review of induction; Division algorithm |
Induction: §1.3, focusing on the first principle of induction. Extra example: proving the Binomial Theorem by induction. Divisibility: §1.5. (We didn't get to the final part of §1.5, "Greatest common divisors," and will begin there on Monday.) |
To see a true "division algorithm" which produces q and r given a dividend a and divisor b, look here. Both the principle of induction and the division algorithm can be justified using the Well-Ordering Property of the natural numbers. Read p.6 of the text, then proofs of Thm 1.5 (p.25) and of Thm. 1.10 (p.37). |
|||

2 | 9.8 | Greatest common divisor; Prime numbers: definition, Euclid's proof of infinitude, sieving |
GCD: last page of §1.5.Primes and sieves: §3.1 through Example 3.3 |
Sieve of Eratosthenes | Here is an animation of the Sieve of Eratosthenes on the integers up to 121. The sieve "meshes" are 2, 3, 5, 7, and 11 = sqrt(121). | |

9.10 | Finish up Sieve of Eratosthenes; Properties of gcd: Bezout's theorem, linear combinations. |
§3.3 through Theorem 3.9. (The main topics of lecture were Thm. 3.8 and Thm. 3.9.) | HW 1 due | |||

9.12 | Euclidean algorithm (calculating gcd, part 1), Solving linear equations with the Extended Euclidean algorithm |
§3.4, also see "in-class exercise" notes for several examples | Euclidean algorithm | |||

3 | 9.15 | Linear Diophantine equations: no solution vs. infinitely many |
§3.7 through Example 3.29. The main topic was Thm. 3.23. To prove it, we needed (and proved) Lemma 3.4 (p.113) and Thm. 3.6 (p.94). Also see the in-class exercise from 9.17 for examples. |
|||

9.17 | gcd of > 2 numbers; linear Diophantine equations in > 2 variables |
gcd of > 2 numbers: §3.3, p.98-end Linear equations in > 2 variables: §3.7, Thm. 3.24-end |
Solving linear Diophantine equations in 2 variables | HW 2 due | ||

9.19 | Finish up Diophantine equations; Fundamental Theorem of Arithmetic |
Diophantine equations: Finish proof of Thm. 3.24 in §3.7 Fundamental Thm of Arithmetic: §3.5 through Lemma 3.7 |
||||

4 | 9.22 | Congruences: definition, existence, and basic properties |
§4.1 through Cor. 4.9.1 | |||

9.24 | Representing integers with respect to a base; modular exponentiation |
§2.1; also §4.1 ``Fast modular exponentiation'' (omit Thm. 4.10) |
Modular exponentiation | HW 3 due | ||

9.26 | Solvability criterion for linear congruences; modular inverses |
§4.2 | Solving linear congruences | |||

5 | 9.29 | Solving systems of congruences, part 1: Chinese Remainder Theorem |
§4.3 | Chinese Remainder Theorem | ||

10.1 | Solving systems of congruences, part 2: polynomial congruences, Hensel's Lemma |
§4.4 | HW 4 due | |||

10.3 | Solving systems of congruences, part 3: linear systems |
§ 4.5 | Solving systems of congruences | |||

6 | 10.6 | Applications of congruences, part 1: divisibility tests |
§5.1 | |||

10.8 | Applications of congruences, part 2: Character ciphers; checksums |
§8.1 §5.4 |
Character ciphers | HW 5 due | ||

10.9 | Midterm Exam 1 | Material of Sept 5 through Oct 3 | 6:30-7:30pm | 202 Macleod | ||

10.10 | Special congruences mod primes: Wilson's Thm; Fermat's Little Thm |
§6.1 through Cor. 6.5.1 | ||||

7 | 10.13 | No lecture (Thanksgiving) | ||||

10.15 | Quadratic residues, part 1: Euler's criterion, Gauss's lemma |
§11.1 (omit Thm. 11.2) | HW 6 due | |||

10.17 | Quadratic residues, part 2: Quadratic reciprocity |
§11.2 | ||||

8 | 10.20 | Quadratic residues, part 3: Jacobi symbols |
§ 11.3 | |||

10.22 | Euler's theorem; multiplicativity of Euler's φ-function |
§6.3 §7.1 through Thm. 7.4 |
HW 7 due | |||

10.24 | Calculating φ(n); definition of multiplicative order |
§ 7.1 §9.1 through Example 9.1 |
||||

9 | 10.27 | Primitive roots: definition, examples, nonexamples |
§9.1: Thm. 9.1--end | |||

10.29 | Primitive roots modulo primes: Lagrange's theorem |
§9.2 | HW 8 due | |||

10.31 | Existence criterion for primitive roots | §9.3 | ||||

10 | 11.3 | Discrete logarithms and index arithmetic | §9.4 | |||

11.5 | Review day: Reciprocity revisited |
TBA | HW 9 due | |||

11.6 | Midterm Exam 2 | Material of Oct 10 through Nov 3 | 6:30-7:30pm | 202 Macleod | ||

11.7 | Toolkit for applied number theory: algorithmic efficiency, benchmarks |
§2.2 | ||||

11 | 11.10 | Primality testing, part 1: using FLT and Euler's criterion |
§6.2 §11.4 |
|||

11.12 | Primality testing, part 2: using orders and primitive roots |
§9.5 | HW 10 due | |||

11.14 | Factorization techniques, part 1: Pollard Rho, Pollard p - 1 |
§4.6 §6.1: p. 221--end |
||||

12 | 11.17 | Factorization techniques, part 2: state of the art |
TBA | |||

11.19 | Public key crypto, part 1: protocols, textbook RSA |
§8.4 | HW 11 due | |||

11.21 | Public key crypto, part 2: attacks on RSA |
§8.4 | ||||

13 | 11.24 | Public key crypto, part 3: Diffie-Hellman key exchange |
§8.6 | |||

11.26 | Public key crypto, part 4: Hash functions, digital signatures |
TBA | HW 12 due | |||

11.28 | Choice of: pseudorandom numbers, ElGamal, elliptic curve crypto |
TBA | ||||

TBA | Review session | |||||

TBA | Final exam | Cumulative |