MAT 311 - Number Theory -- Spring 2003

MAT 311
Number Theory

Instructor Sorin Popescu (office: Math 4-119, tel. 632-8358, e-mail sorin@math.sunysb.edu)

Time and Place TuTh 02:20pm-03:40pm, SBU 226

Prerequisites

Either MAT 312 (Applied algebra), or MAT 313 (Abstract Algebra) or MAT 318 (Classical Algebra) are mandatory prerequisites for this class. In general basic algebra exposure is required and assumed, but I will try to keep prerequisites to a minimum.

Textbook(s)

Elementary Number Theory and Its Applications , by Kenneth Rosen, (fourth edition) Addison-Wesley 2002.

This is a very nice textbook that integrates classical (elementary) topics in number theory with lots and lots of applications to cryptology, computer science, etc. It also features a number of computer (programming) projects, mainly for Mathematica and Maple.
There are many other excellent undergraduate books on the subject. Here is a sample (all of them available in our library):

A Friendly Introduction to Number Theory, J.H. Silverman
An Introduction to the Number Theory, H.M. Stark
Number Theory, G.E. Andrews
Introduction to Analytic Number Theory, T.M. Apostol
Lectures on Number Theory, P.G.L. Dirichlet with supplements by R. Dedekind
The higher arithmetic, H. Davenport
An Introduction to the Theory of Numbers, I. Niven and H.S. Zuckerman
A Classical Introduction to Modern Number Theory, K. Ireland and M. Rosen
Fundamentals of Number Theory, W.J. LeVeque
Number theory with computer applications, R. Kumanduri and C. Romero
These are a mixture of classical texts (for example Dirichlet), modern efforts, more elementary (for example, Silverman, Kumanduri and Romero) and more advanced (for example, Ireland and Rosen), algebraic (for example, Andrews) or analytic approaches (for example, Apostol). This course will concentrate only on elementary algebraic number theory, and applications.

Course description & Homework assignments

We will cover only part of the textbook and the following schedule may/will be adjusted based on students' preparation and progress. Problems marked with an asterisk (*) are for extra credit.

Date Topic Homework Notes

Wk 1

1/23 1.1 Numbers, sequences, and sums p14/2,4,26,27; p22/5,10,16,30;
p28/4,8,22; due 02/04; solutions

Wk 2 1/28 1.2 Mathematical induction; 1.3 Fibonacci numbers Fibonacci links

1/30 1.4 Divisibility; 3.1 Prime numbers p34/4,16,28; p76/2,6,10;
p84/6,7,13,31; due 02/11; solutions Half hour pretest

Wk 3 2/4 3.2 Greatest common divisor Primes links

2/6 3.3-3.4 Euclidean algorithm, Fundamental theorem of arithmetic p94/5,7,19*; p123/2, 3, 6
p104/4, 10, 16*, 32, 35, 46;
due 02/18; solutions

Wk 4 2/11 3.6 Linear Diophantine equations

2/13 4.1-4.5: Congruences p123/4, 21;
p135/5, 22, 26, 28, 38*; p141/2, 6, 8;
due 02/25; solutions

Wk 5 2/18 p149/4a)-b), 12, 22, 24;
p159/1, 10; p167/2, 4, 8b, 14*
due 03/04; solutions

2/20 p177/12,19,22;
p195/8,12,13,16,17
due 03/11; solutions

Wk 6 2/25

2/27 5.1 Divisibility tests

Wk 7 3/4 6.1-6.2 Wilson's theorem, Fermat's little theorem, pseudoprimes p202/3, 12, 15, 20, 22, 23;
p213/2, 7
due 03/27; solutions First project due

3/6

Wk 8 3/11 Midterm [exam] [solutions]

3/13 6.3 Euler's theorem

Recess

Wk 9 3/25 7. Multiplicative functions p218/1, 6, 8, 12; p227/1, 2(c,e), 3, 5, 14, 35
due 04/3; solutions

3/27

Wk 10 4/1 p235/2(a-c), 21, 22, 23, 24, 34*, 37*
p257/1(a,b), 15,17,18,23; due 04/10; solutions

4/3 8. Cryptography

Wk 11 4/8 p267/3, 14, 15
p278/1, 3, 4*, 13, 18, 19
p290/1, 3, 4*, 6, 7, 11*; due 04/22; solutions

4/10

Wk 12 4/15 p304/1, 6, 10; p313/1, 6, 10, 18*;
due 04/29; solutions 04/16-04/18 no classes
Passover

9. Primitive roots

Wk 13 4/22 p319/3, 8, 12, 16; p337/2, 4, 9
due 05/06 Second project due

4/24

Wk 14 4/29 11. Quadratic residues

5/1

Wk 15 5/6

5/8 Review

5/20 Final exam 2:00-4:30pm (SBU 226)

5/20 Review 05/16, 4:00pm-5:30pm (Math Towers P-131)

	Date	Topic	Homework	Notes
Wk 1
1/23	1.1 Numbers, sequences, and sums	p14/2,4,26,27; p22/5,10,16,30; p28/4,8,22; due 02/04; solutions
Wk 2	1/28	1.2 Mathematical induction; 1.3 Fibonacci numbers	Fibonacci links
1/30	1.4 Divisibility; 3.1 Prime numbers	p34/4,16,28; p76/2,6,10; p84/6,7,13,31; due 02/11; solutions	Half hour pretest
Wk 3	2/4	3.2 Greatest common divisor	Primes links
2/6	3.3-3.4 Euclidean algorithm, Fundamental theorem of arithmetic	p94/5,7,19; p123/2, 3, 6 p104/4, 10, 16, 32, 35, 46; due 02/18; solutions
Wk 4	2/11	3.6 Linear Diophantine equations
2/13	4.1-4.5: Congruences	p123/4, 21; p135/5, 22, 26, 28, 38*; p141/2, 6, 8; due 02/25; solutions
Wk 5	2/18	p149/4a)-b), 12, 22, 24; p159/1, 10; p167/2, 4, 8b, 14* due 03/04; solutions
2/20	p177/12,19,22; p195/8,12,13,16,17 due 03/11; solutions
Wk 6	2/25
2/27	5.1 Divisibility tests
Wk 7	3/4	6.1-6.2 Wilson's theorem, Fermat's little theorem, pseudoprimes	p202/3, 12, 15, 20, 22, 23; p213/2, 7 due 03/27; solutions	First project due
3/6
Wk 8	3/11	Midterm [exam] [solutions]
3/13	6.3 Euler's theorem
Recess
Wk 9	3/25	7. Multiplicative functions	p218/1, 6, 8, 12; p227/1, 2(c,e), 3, 5, 14, 35 due 04/3; solutions
3/27
Wk 10	4/1	p235/2(a-c), 21, 22, 23, 24, 34, 37 p257/1(a,b), 15,17,18,23; due 04/10; solutions
4/3	8. Cryptography
Wk 11	4/8	p267/3, 14, 15 p278/1, 3, 4, 13, 18, 19 p290/1, 3, 4, 6, 7, 11*; due 04/22; solutions
4/10
Wk 12	4/15	p304/1, 6, 10; p313/1, 6, 10, 18*; due 04/29; solutions	04/16-04/18 no classes Passover
	9. Primitive roots
Wk 13	4/22	p319/3, 8, 12, 16; p337/2, 4, 9 due 05/06	Second project due
4/24
Wk 14	4/29	11. Quadratic residues
5/1
Wk 15	5/6
5/8	Review
	5/20	Final exam 2:00-4:30pm (SBU 226)
	5/20	Review 05/16, 4:00pm-5:30pm (Math Towers P-131)

Projects, Homework & Grading

Homework (see above) and projects (TBA) are an integral part of the course. Problems marked with an asterisk (*) are for extra credit. In addition you will be required to hand in 2 research/scholarship/computing projects. Projects with a nontrivial writing component may be used to satisfy the Mathematics Upper Division Writing Requirement.

Your grade will be based on the weekly homeworks (20%), two projects (15% each), midterm (20%), and the final exam (30%). The two lowest homework grades will be dropped before calculating the average.

The Math Learning Center (MLC), located in Room S-240A of the Math Tower, is an important resource. It is staffed most days and some evenings by mathematics tutors (professors and advanced students). For more information and a schedule, consult the MLC web site.

Software

Links

The following is a short list of web sites devoted to number theory or number theoretic related topics relevant for our class:

An On-Line Encyclopedia of Integer Sequences.
Fibonacci Numbers and Nature. Or Tony Phillips' "The most irrational number". Also "Who was Fibonacci?": a brief biography of Fibonacci.
Primes: Lots of interesting facts about prime numbers.
Mersenne Primes: interesting facts about Mersenne primes, perfect numbers, and related topics.
Primes is P: about a recent polynomial time deterministic algorithm to test if an input number is prime or not.
RSA: The RSA company's web page containing lots of interesting information about the RSA public key cryptosystem and cryptography in general, from both a technological and a socio-political viewpoint.

Here are a number of interesting local links:

Problem of the Month sponsored by the Stony Brook mathematics deptartment. The first two winners each month get $25!
Math Club

Special needs

If you have a physical, psychiatric, medical or learning disability that may impact on your ability to carry out assigned course work, you may contact the Disabled Student Services (DSS) office (Humanities 133, 632-6748/TDD). DSS will review your concerns and determine, with you, what accommodations may be necessary and appropriate. I will take their findings into account in deciding what alterations in course work you require. All information on and documentation of a disability condition should be supplied to me in writing at the earliest possible time AND is strictly confidential. Please act early, since I will not be able to make any retroactive course changes.

Sorin Popescu

2002-12-21