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


the Euler phi function


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


Announcements


Syllabus and Course Policies

This course is an introduction to the multiplicative structure of the integers. We will cover classical theorems such as the Fundamental Theorem of Arithmetic, the Chinese Remainder Theorem, and the Law of Quadratic Reciprocity, as well as a variety of modern applications. At the same time, we'll build skill in mathematical reasoning and proof-writing. For a detailed list of topics, see the
course syllabus or the day-by-day schedule.

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

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      

Course Schedule

All chapter/section references are to the textbook Elementary Number Theory and Its Applications (6th ed).
''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