## Mathematics 312, Introduction to number theory, Section 101, Fall 2015, MWF 11-11:50, Leonard S. Klinck (LSK) Building.

• Instructor : Zinovy Reichstein
Office: 1105 Math Annex
Office hours: Tu 3-4:30, We 3-4:40
Phone: 822-3929
E-mail: reichst at math.ubc.ca

• Textbook : K. Rosen, Elementary Number Theory, 6th edition.
• Course syllabus : This course is intended as an introduction to the basic concepts of number theory, such as prime numbers, factorization, and congruences, as well as some of their applications, particularly to cryptography. Proofs are integral to the subject, they will be given in class and problems involving proofs will appear on the homework and on the tests. Regular reading and working through problems from the text are an essential part of the course.

Wednesday, September 9. Lecture 1. A brief history of number theory. The well-ordering principle and mathematical induction. Slides from Lecture 1.

Friday, September 11. Lecture 2. Strong mathematical induction (section 1.3). Divisibility (section 1.5). Slides from Lecture 2.

• Monday, September 14. Lecture 3. Divisibility (section 1.5), prime numbers (section 3.1), greatest common divisor (section 3.3). Notes from Lecture 3 by Prof. Vatsal

Wednesday, September 16. Lecture 4. Greatest common divisor (section 3.3), the Euclidean algorithm (section 3.4) Slides from Lecture 4

Friday, September 18. Lecture 5. The Euclidean algorithm (section 3.4), fundamental theorem of arithmetic (section 3.5). Slides from Lecture 5

Monday, September 21. Lecture 6. Linear diophantian equations (section 3.7). Slides from Lecture 6

Wednesday, September 23. Lecture 7. Conguences (section 4.1). Notes from Lecture 7 by Prof. Vatsal

Friday, September 25. Lecture 8. "Unfinished business" on linear diophantian equations (section 3.7), congruences (section 4.1). Notes from Lecture 8

Monday, September 28. Lecture 9. Representation of integers (section 2.1), repeated squaring (section 4.1). Notes from Lecture 9

Wednesday, September 30. Lecture 10. Linear congruences (section 4.2). Notes from Lecture 10

Friday, October 2. Lecture 11. Inverses mod m (section 4.2), Chinese remainder theorem (section 4.3). Notes from Lecture 11

Monday, October 5. Lecture 12. Chinese remainder theorem continued (section 4.3).

Wednesday, October 7. Lecture 13. More on Chinese remainder theorem (section 4.3). Notes from Lectures 12 and 13

Friday, October 9. Lecture 14. Divisibility tests (section 5.1).

Friday, October 16. Lecture 15. The ISBN code (section 5.5), start on Wilson's Theorem and Fermat's Little Theorem (section 6.1). Notes from Lecture 15

Monday, October 19. Lecture 16. Corollaries of Fermat's Little Theorem. Pollard's p-1 factorization method (section 6.1). Notes from Lecture 16

Wednesday, October 21. Lecture 17. Primality testing and pseudo-primes: Fermat's test and Carmichael numbers (section 6.2).

Friday, October 23. Lecture 18. Primality testing and pseudo-primes continued: Miller's test (section 6.2). Notes from Lectures 17 and 18.

Monday, October 26. Lecture 19. The Euler phi-function and Euler's Theorem (sections 6.3 and 7.1) Notes from Lecture 19.

Wednesday, October 28. Lecture 20. A formula for the Euler phi-function (section 7.1) Notes from Lecture 20.

Friday, October 30. Lecture 21. Multiplicative functions (section 7.2) Notes from Lecture 21.

Monday, November 2. Lecture 22. Perfect numbers and Mersenne primes (section 7.3) Notes from Lecture 22.

Wednesday, November 4. Lecture 23. Introduction to cryptography. Shift and affice ciphers (section 8.1). Notes from Lecture 23.

Friday, November 6. Lecture 24. More on affice ciphers (section 8.1). Notes from Lecture 24.

Monday, November 9. Lecture 25. Exponentiation ciphers (section 8.3), public key cryptography, the RSA cryptosystem (section 8.4). Notes from Lecture 25.

Friday, November 13. Midterm 2 review

Wednesday, November 18. Lecture 26. Attacks on the RSA cryptosystem (section 8.4), Fermat factorization (section 3.6), digital signatures (section 8.6). Notes from Lecture 26.

Friday, November 20. Lecture 27. The order of an integer and primitive roots (section 9.1). Notes from Lecture 27.

Monday, November 23. Lecture 28. Which integers n have primitive roots mod n? (section 9.1 - 9.3). Notes from Lecture 28.

Wednesday, November 25. Lecture 29. Primitive roots for primes (section 9.2). Notes from Lecture 29.

Friday, November 27. Lecture 30. Discrete logarithms (section 9.4). Notes from Lecture 30.

Monday, November 30. Lecture 31. Primitive roots for non-prime integers (from section 9.2). Notes from Lecture 31.

Wednesday, December 2. Lecture 32. The ElGamal cryptosystem (section 10.2). Notes from Lecture 32.

Friday, December 4. Lecture 33. Review of orders and indices. Partial solutions to Problem Set 9.

• Homework : Homework assignments will be collected in class on Fridays, usually on a weekly schedule. Homework problems will ask students to apply theorems from class to carry out calculations, and also to write their own proofs. While homework assignments only count for a relatively small percentage of the total course mark, they are, arguably the most important part of the course. You need to do them in a regular basis to practice, absorb and internalize the material in a way that cannot be replicated by just listening to the lectures or last-minute cramming for exams. Please allow yourself plenty of time to carefully work through each homework assignment, and don't get behind!
A portion of each assignment will be graded by the course marker. Late homework will not be accepted. Students are allowed to consult one another concerning the homework problems. However, your submitted solutions must be written by you in your own words.
• Evaluation : Course marks will be based on one of the two marking schemes: (1) homework (10%), midterm 1 (20%), midterm 2 (20%), final exam (50%) or (2) homework (10%), best midterm (20%), final exam (70%). I will compute the total course mark both ways and use the higher of the two marks.

Midterm 1 will be given in class Wednesday, October 14. It will cover material from Sections 1.3, 1.5, 2.1, 3.1, 3.3, 3.4, 3.5, 3.7, 4.1, 4.2, and 4.3.

Review problems for Midterm 1 This is the actual first midterm exam from UBC's Math 312 class taught by Laura Peskin in the summer of 2015. Please ignore Problems 1e and 8b.
Solutions to review problems for Midterm 1
Midterm 1 problems and solutions.
Midterm 1 average: 14.8 out of 20.

Midterm 2 will be given Monday, November 16. It will cover material from Sections 5.1, 5.5, 6.1, 6.2, 6.3, 7.1, 7.2, 7.3, 8.1, and 8.3.

Review problems for Midterm 2
Solutions to review problems for Midterm 2
Midterm 2 problems and solutions.
Midterm 2 average: 11.8 out of 20. I will add 2 bonus points to the Midterm 2 mark for every student who took Midterm 2.

The final exam will be held at 7pm on Wednesday, December 9, 2015 in LSK 201. It will cover material the entire course syllabus (see below).

Office hours during Exam Period: Tuesday, december 8, 13-14:30, in Math Annex 1105 and/or Math Annex 1102. (Check both rooms.)

Practice Final Exam This is the actual final exam from the Math 312 class I taught in the Fall of 2010. Other actual Math 312 final exams can be found here.
Solutions to the Practice Final Exam

Calculators can be used to solve homework problems. No calculators, books or notes will not be allowed on the exams.

• Missed exam policy : There will be no make-up or alternate exams in this class. If you miss a midterm, your score will be recorded as 0, unless you have a serious documented reason (an illness, a death in the family, etc.), in which case you should discuss your circumstances with me as soon as possible.
Missed finals are not handled by me or the Mathematics Department. Students with legitimate reasons for missing the final exam should request a ``Standing Deferred" status through their faculty.
• Sections in the book to be covered. Some changes during the term are possible.

1. The Integers
1.3. Mathematical induction 1.3
1.5. Divisibility 1.5

2. Integers representations and operations
2.1. Representations of integers.

3. Primes and Greatest Common Divisors
3.1. Prime numbers
3.2. The distribution of primes
3.3. Greatest common divisors
3.4. The Euclidean algorithm
3.5. The fundamental theorem of arithmetic
3.6. Fermat Factorization only.

3.7. Linear Diophantine equations

4. Congruences.
4.1. Introduction to congruences
4.2. Linear congruences
4.3. The Chinese Remainder Theorem

5. Applications of Congruences
5.1. Divisibility tests
5.5. Check digits (ISBN code only)

6. Some Special Congruences
6.1. Wilson's Theorem and Fermat's Little Theorem
6.2. Pseudoprimes
6.3. Euler's Theorem

7. Multiplicative Functions
7.1. The Euler phi-function
7.2. The sum and number of divisors
7.3. Perfect numbers and Mersenne primes

8. Cryptology.
8.1. Character ciphers
8.3. Exponentiation ciphers
8.4. Public key cryptography
8.6. Cryptographic protocols and applications (digital signatures only)

9. Primitive roots.
9.1. The order of an integer and primitive roots.
9.2. Primitive roots for primes.
9.3. The existence of primitive roots.
9.4. Discrete logarithms and index arithmetic.

10.2 The ElGamal cryptosystem.