Lectures: MWF 11:0012:00 in LSK 460
Office hours: MW 9:5010: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 10.1
Announcements  updated 11.28
Assignments  updated 12.2
Exams  updated 12.2
Schedule  updated 11.28
Assignments are due on Wednesdays at 11am in class, except for HW 6 which is due on Friday, Oct. 17 and HW 12 which is due on Friday, Nov. 28. 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  5 pts each for #3, #5, #7 5 pts for completeness 
Solutions to HW 2 
3  9.24  Homework 3  9 pts for #5, 6 pts for #7 5 pts for completeness 
Solutions to HW 3 
4  10.1  Homework 4  5 pts each for #2, #8, #11 5 pts for completeness 
Solutions to HW 4 
5  10.8  Homework 5  6 pts for #2, 9 pts for #7 5 pts for completeness 
Solutions to HW 5 
6  10.17 (!!)  Homework 6  6 pts for #1, 5 pts for #2 9 pts for #3 
Solutions to HW 6 
7  10.22  Homework 7  6 pts for #3, 3 pts for #6 6 pts for #7, 5 pts for completeness 
Solutions to HW 7 
8  10.29  Homework 8  9 pts for #3, 6 pts for #9 5 pts for completeness 
Solutions to HW 8 
9  11.5  Homework 9  5 pts each for #4, #5, #8 5 pts for completeness 
Solutions to HW 9 
10  11.12  Homework 10  5 pts each for #1, #3, #4 5 pts for completeness 
Solutions to HW 10 
11  11.19  Homework 11  5 pts each for (a), (e), (j) 5 pts for completeness 
Solutions to HW 11 
12  11.28 (!!)  Homework 12 
5 pts each for #2, #5, #9 5 pts for completeness 
Solutions to HW 12 
Exam info  Solutions 

Midterm 1 info  Midterm 1 solutions 
Midterm 2 info, Midterm 2 review questions, Solutions to review questions  Midterm 2 solutions 
Final exam info, Final review questions 
Week  Date  Topics  Required reading  Inclass 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 WellOrdering 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 Graph of π(x) with scaled and unscaled axes 
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 "inclass 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 inclass exercise from 9.17 for examples. 
Here is a scan of a 1910 English translation by Thomas Heath of Diophantus's Arithmetica. (With commentary; text begins on p.129.) Offered mainly for historical value; it's pretty hard to read!  
9.17  gcd of > 2 numbers; linear Diophantine equations in > 2 variables 
gcd of > 2 numbers: §3.3, p.98end Linear equations in > 2 variables: §3.7, Thm. 3.24end 
Solving linear Diophantine equations in 2 variables  We have an algorithmic way to tell whether any linear Diophantine equation has an integer solution: just find the gcd of the coefficients (e.g. using Euclid's algorithm) and check if this gcd divides the constant term. But it's impossible to construct an algorithm to decide whether a general Diophantine equation has an integer solution: this impossibility was proved by Matiyasevich in 1970, answering a question posed by Hilbert in 1900. Here (log in through UBC library) is a paper by Martin Davis explaining the proof. 
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. (We'll finish the uniqueness part of the FTA on Monday. We won't do Lemma 3.7 in class but please read it.) 

4  9.22  Uniqueness part of the Fund. Thm. of Arith; Congruences: definition, existence, and basic properties 
Proof of uniqueness part of FTA: Thm. 3.15 in §3.5. Congruences: §4.1 Defn. of congruence modulo m (p. 145), defn. of complete system of representatives/residues mod m (p. 148) 

9.24  Arithmetic with congruences; Representing integers with respect to a base; modular exponentiation 
Arithmetic with congruences: §4.1 Thms. 4.2, 4.4, and 4.8. Representations of integers: §2.1 (though we used a different method for finding binary representations; see "inclass exercise"). 
Binary and hexadecimal  HW 3 due  
9.26  Arithmetic with congruences  §4.1 Thms. 4.4, 4.6, and 4.8.  Finish binary/hex exercise (posted above)  
5  9.29  Modular exponentiation; division with congruences; solvability criterion for linear congruences  Modular exponentiation: final section of §4.1 (omit Thm. 4.10), and two more examples Division with congruences: §4.1 Thm. 4.5 Solvability of linear congruences: §4.2 intro + Thm. 4.11 

10.1  Proof of solvability criterion for linear congruences (Thm. 4.11); modular inverses  §4.2  Solving linear congruences: Problems, Solutions  HW 4 due  
10.3  Solving systems of congruences, part 1: Chinese Remainder Theorem  § 4.3 through Example 4.16; proof of Thm. 4.13 will be done on Monday. You just need to know the process for the exam.  Look at Example 4.17 for another way of solving systems of linear congruences (probably similar to the method you used to solve systems of linear equations in high school). The Chinese Remainder Theorem is going to be important when we learn about the RSA cryptosytem (p. 323329 in the text). In particular, we'll look at systems of two congruences, where the two moduli are distinct primes. 

6  10.6  Proof of uniqueness (mod M) in the Chinese Remainder Theorem  §4.3 proof of Thm. 4.13  
10.8  CRT with nonrelatively prime moduli; Review Q & A; Prime Number Theorem  Notes on CRT not assuming moduli are relatively prime  HW 5 due  
10.9  Midterm Exam 1  Material of Sept 5 through Oct 3, info here.  6:307:30pm  202 Macleod  
10.10  Polynomial congruences  §4.4 through case (1) of Hensel's Lemma  
7  10.13  No lecture (Thanksgiving)  
10.15  Hensel's Lemma: statement, proof sketch, and examples; recursive formula in Case 1  §4.4 from Thm. 4.15end. (Focus on the examples rather than the proof of HL. The statement of Cor. 4.15.1 is useful: it is a recursive formula for the unique lifts of a Case 1 solution to the congruence mod p.)  
10.17  More examples of lifting polynomial congruences; Wilson's theorem 
Wilson's Theorem: §6.1 through the proof of Thm. 6.1.  HW 6 due  
8  10.20  Converse of Wilson's theorem; Fermat's Little Theorem; pseudoprimes and Carmichael numbers  Converse of Wilson's theorem: §6.1, Thm. 6.2 and Example 6.3. Fermat's Little Theorem and applications: §6.1, Thm. 6.3 through Cor. 6.5.1. Pseudoprimes and Carmichael numbers: §6.2 through Example 6.12. (No need to spend a lot of time on this section now; we will come back to it.) 

10.22  Euler's theorem; calculating values of Euler's φfunction 
§6.3 (just the statement of Euler's Theorem and the examples)  HW 7 due  
10.24  Proof of Euler's Theorem; examples and applications  Proof of Euler's Theorem: §6.3, proofs of Thm. 6.13 and 6.18.  Applications of FLT and Euler's Theorem: Problems, Solutions  
9  10.27  Order of an integer; Primitive roots (definition, examples, nonexamples)  §9.1: Thm. 9.1 through the statement of Thm. 9.3, omitting Thm. 9.2  
10.29  More examples of primitive roots; generating all primitive roots from one  §9.1: Thm. 9.2 and Thm. 9.3, statement of Thm. 9.4, and Corollary 9.4.1.  HW 8 due  
10.31  Existence/nonexistence of integers with certain order (mod n); criterion for existence of primitive root; Lagrange's Theorem  §9.2: Lagrange's Theorem on the number of roots (mod p) of a degreen polynomial  
10  11.3  Finish proof that every prime number has a primitive root; observations about orders (mod 13)  §9.2, and these notes about orders (mod 13) (may be useful for HW 9!)  Review problems handed out (solutions below)  
11.5  Solutions to review problems  See 11.3 entry for problem list  Solutions to review problems  HW 9 due  
11.6  Midterm Exam 2  Material of Oct 6 through Nov 3, info here.  6:307:30pm  202 Macleod  
11.7  Quadratic residues and nonresidues: Euler's criterion and Quadratic Reciprocity  Quadratic residues and Euler's criterion: §11.1 Thms. 11.1, 11.2, 11.3, and 11.4, though with different proofs (most of which you've written yourself on HW!) using primitive roots. Law of Quadratic Reciprocity: §11.2 Thm. 11.7 (just the statement) 
There are over 200 different proofs of the Law of Quadratic Reciprocity (so far), using incredibly various techniques. Here's a list of 246 proofs, starting with Legendre's incomplete 1788 proof, continuing with 6 different complete proofs by Gauss in 18011818, and with at least one new proof in almost every year since.  
11  11.10  Supplements to the Law of Quadratic Reciprocity; examples  §11.1 Thm. 11.5 and 11.6 (just the statements); §11.2 Example 11.10  
11.12  Diophantine equations: the technique of descent, proof of the twosquare theorem  Lecture notes are here. As a first example of Fermat's technique of descent, we proved that 2 has no rational square root. Then we used the descent technique (plus our knowledge of when 1 is a square modulo a prime p) to prove the classic "twosquare theorem": a prime p can be written as a sum of two integer squares if and only if p = 2 or p is congruent to 1 (mod 4). This proof uses Fermat's ideas, but is somewhat different: I learned it from the article linked in today's "Optional reading".  You can read much more about descent in this article by Keith Conrad. The twosquare theorem we proved can be generalized to say, for any positive integer n (not necessarily prime), whether the equation x^2 + y^2 = n has an integer solution. (The answer is: if any prime congruent to 3 (mod 4) appears with an odd exponent in the prime factorization of n, then there's no solution. Otherwise, a solution exists.) See Thm. 13.6 in the text for a proof! 
HW 10 due  
11.14  Quadratic forms and the HasseMinkowski Theorem  Lecture notes to be posted. As noted before, there is no general algorithm which decided whether a nonlinear Diophantine equation has a solution. Back when we started looking at congruences, I told you that we'd use congruences to solve that problem for certain kinds of equations. You soon learned how to use congruences to show that some equations have no integer solutions; in this class and the previous one, we use congruences to show that some equations do have integer solutions. This is our last classic theorem in pure number theory before we dive in to applications!  
12  11.17  BigO notation, bit operations, complexity of arithmetic operations  Onotation: §2.3 through Example 2.12 Bit operations: §2.2 Complexity: §2.3 from Example 2.13end. 

11.19  Fermat pseudoprimes and Carmichael numbers; inefficiency of trial division; idea of probabilistic primality testing  §6.2 through Example 6.13  HW 11 due  
11.21  MillerRabin probabilistic primality test  §6.2, Example 6.14end. You can try out the code used in lecture here:

Demo with code (to the left). Highlights: the Carmichael number 561 is declared composite; numbers with >700 binary digits can be tested in a fraction of a second.  Pomerance, Selfridge, and Wagstaff computed a list of composite numbers (up to 25*10^9) which pass the MillerRabin test for certain values of a. This is enough to turn the MillerRabin test into a deterministic test, as long as the number you're testing is smaller than 25*10^9. See the introduction and then p.1021 of their paper for details. (The paper is from 1980 and various improvements have been found since.)  
13  11.24  Pollard Rho factorization algorithm  The idea of the algorithm is explained in §4.6. You can try out the code from lecture here. To load and run it, follow the same instructions as for the previous demo just above.


11.26  The RSA cryptosystem  §8.4, omitting the final section (Rabin cryptosystem)  The original RSA paper by Rivest, Shamir, and Adleman.  
11.28  Security of RSA  Proof that knowledge of RSA private exponent allows one to efficiently factor the modulus. RSA key generation example. Also includes a simulation of the SSL/TLS key exchange protocol, which is what's happening when you see this. The link above is to a noninteractive record of what we did in class. Here's the same code as a Sage worksheet which you can download and play with. 
A classic paper on the security of RSA: 20 years of attacks on the RSA cryptosystem by Dan Boneh. 
HW 12 due  
12.8  Review session  Let me know which topics you'd most like to cover in this session.  11am1pm  460 LSK  
12.8  Office hours  By appointment  300C LSK  
12.9  Office hours  11am1:30pm  300C LSK  
12.10  Final exam  Cumulative with a few exceptions, info here.  3:306:30pm  201 LSK 