Number Theory: Math 522, Fall 2001
Schedule and Assignments


Schedule

I will try to keep to this schedule but will update it as needed.
Day Topics Preparation
Wed. 9/5 Introduction .
Fri. 9/7 Fibonacci numbers, divisibility Sec. 1.1-3
Mon. 9/10 Divisiblity, greatest integer function Sec. 1.4
Wed. 9/12 Base r representations and arithmetic Secs. 2.1-2
Fri. 9/14 Base r arithmetic, big O Secs. 2.2,3
Mon. 9/17 Prime numbers Sec. 3.1
Wed. 9/19 Conjectures on primes, greatest common divisor Sec. 3.1,2
Fri. 9/21 Euclidean algorithm Sec 3.3
Mon. 9/24 Matrix version of Euclidean algorithm, least common multiple 3.3
Wed. 9/26 Least common multiple, preparation for unique factorization Sec. 3.4
Fri. 9/28 Unique factorization,
application to primes in arithmetic prgression 		Sec. 3.4
Mon. 10/1 Linear Diophantine equations Sec. 3.6
Wed. 10/3 Linear Diophantine equations in several variables Sec. 3.6
Fri. 10/5 Nonlinear Diophantine equations: Pythagorean triples Sec. 13.1
Mon. 10/8 Nonlinear Diophantine equations: Fermat's last theorem Sec. 13.2
Wed. 10/10 Gaussian integers p. 98; 3.4 problems 19-24
Fri. 10/12 Quadratic extensions of Z p. 98; v3.4 problems 19-24
Mon. 10/15 EXAM Secs. 1.1-4; 2.1-2; 3.1-4; 3.6; 13.1, 13.2.
Wed. 10/17 A Non-unique factorization domain Z[sqrt(-5)]
Modular arithmetic 		Sec. 4.1
Fri. 10/19 Units and zero-divisors in Z/m Sec. 4.1
Mon. 10/22 Solution of equations Secs. 4.2, 11.1, pp. 376-7
Wed. 10/24 Quadratic equations, divisiblity tests Secs. 11.1, 5.1
Fri. 10/26 More on divisibility. tournament scheduling Sec. 5.3
Mon. 10/29 Chinese remainder theorem and extensions Sec. 4.3
Wed. 10/31 Hash functions, check digits Secs. 5.4-5
Fri. 11/2 Exercises Secs. 4.1-3
Mon. 11/5 Systems of linear congruences Sec. 4.5
Wed. 11/7 Fermat's little theorem Sec. 6.1
Fri. 11/9 Euler's theorem Sec. 6.3
Mon. 11/12 Linear cryptosystems Sec. 8.1-2
Wed. 11/14 Exponentiation cryptosystems Sec. 8.3
Fri. 11/16 The RSA cipher Sec. 8.4
Mon. 11/19 EXAM .
Wed. 11/21 RSA cipher Sec. 8.4
Mon. 11/26 The Euler phi function Sec. 7.1
Wed. 11/28 Multiplicative functions,
number of divisors, sum of divisors 		Sec 7.2
Fri. 11/30 Order in Z/m
primitive elements 		Sec. 9.1
Mon. 12/3 Polynomials over Z/p Secs. 9.2
Wed. 12/5 Polynomials over Z/p Secs. 9.2
Fri. 12/7 Primitive elements in Z/p
index Arithmetic 		Sec. 9.4
Mon. 12/10 El Gamal cryptosystem Sec. 10.2
Wed. 12/12 Review, course evaluation. .
Fri. 12/14 Finite fields, the abc conjecture .




Assigned exercises in Rosen, Elementary Number Theory and Its Applications 4th ed.

Assignments


Here are some computer assignments, most taken from Rosen's book, that you can do for extra credit.
postscript file
pdf file
Due dates may change depending on schedule.
Due Date Section Problems
Wed. 9/12 1.1 8 (find an explicit formula), 24, 28, 32
. 1.2 4, 8, 14
Wed. 9/19 1.3 8, 24, 25, 26, 30
. 1.4 16, 22, 30 (reduce to 0 < x < 1), 40, 46
Wed. 9/26 1.4 48, 50, 53
. 2.1 6, 14, 20, 24, 26
. 2.2 8, 10, 14
Wed. 10/3 3.1 10, 16, 24
. 3.2 14, 16, 22
. 3.3 8b, 14
Wed. 10/10 3.3 10, 20
. 3.4 4d, 12, 16, 36
. 3.6 8,16
Mon. 10/22 3.4 24, 45, 60
. 13.1 2, 12
Mon. 10/29 4.1 18, 24, 28, 34
. 4.2 6, 14, 16
. 11.1 6 (partially), 12
. 5.1 10, 20, 22
Wed. 11/7 4.3 9, 12, 16a
. 5.3 2
. 5.5 8, 10, 20
. 13.1 3
Wed. 11/14 4.5 3, 8c, 10a
. 6.1 20, 22, 24 (p is odd), 28, 40
. 6.3 1d, 2, 4, 10, 11c
Wed. 11/28 8.1 6
. 8.2 8 (write it as a matrix), 20
. 8.3 4, 6
. 8.4 2, 6 (use 11 not 7 and find d )
Wed. 12/5 7.1 6, 8, 28, 30
. 7.2 8, 10
. 9.1 8, 10, 14, 16
Wed. 12/12 9.2 2, 6, 8, 10
. 9.3 2, 4, 8
. 10.2 4, 6


I recommend that you at least read the following problems and solve as many as you can. These recommended problems form the material that you are expected to understand upon completion of this course. You can safely ignore the problems that are not listed here. The midterms and the final exam will be based on the material in these problems, but will not necessarily be identical to them.
Section Recommended Problems
1.1 2-9, 13-15, 23-27,29
1.2 2-9, 11-14, 25-29
1.3 1-22, 30, 31, 35
1.4 All
2.1 1-7, 14-17
2.2 1-11, 13-15,
3.1 1-16, 20, 24, 25
3.2 1-25
3.3 1-10, 14, 15, 20
3.4 1-24, 30-41, 44, 45, 52-54, 60
3.6 1-9, 11-16
13.1 1-6, 7(read only), 12
13.2 1, 2, 4, 5, 9, 10
4.1 1-19, 24-28, 33-35
4.2 1-13, 15, 16, 18
4.3 1-13, 15-19
4.5 1-10
5.1 1-10
5.3 1-3
5.4 1-2
5.5 1-20
6.1 1-25, 28-31, 33, 39, 40
6.3 1-11, 15-17
7.1 1-8, 11-13
7.2 1-12
9.1 1-16
9.2 1-10, 12
9.4 1-9
10.2 1-6
8.1 1-6
8.2 5-8, 18-20
8.3 1-6
8.4 1-2, 5-8
11.1 1, 2, 6, 12, 13
13.1 2-4