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).
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.
Calculators can be used to solve homework problems.
No calculators, books or notes will not be allowed on the exams.
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.