Number Theory



Math 522
Fall 2000
Meeting Tues., Thurs. 15:30-16:45
Bus. Adm./Math Building #255
San Diego State University


Professor: Mike O'Sullivan
Email: m.osullivan@math.sdsu.edu
Office: Bus. Adm./Math Building #217, ext. 594-6697
Office Hours: T Th: 9:30-12:00, 14:00-16:00.
                             MWF: by appointment (I will normally be in my office and available).

Text

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

Course Description

Number theory is one of the oldest and richest subjects in mathematics. One aspect of the subject that delights mathematicians is that a problem that is very easy to pose can require very difficult and profound mathematical structures to solve. Number theory is also considered to be one of the purest and most beautiful areas of mathematics. Yet in the last few decades it has become an important applied subject as well; for example, the security of internet communications depends on an application of number theory. We are using an excellent text book in this course. It gives a good introduction to the fundamentals of number theory, includes several practical applications and has interesting discussions of some important unsolved problems and historical topics. The core material of the course is primes and divisors (Ch. 4) and congruences (Ch. 4 and Ch. 6). Weaved in with these topics will be several applications of congruences: hashing functions (Sec 5.4), used by computesrs to store data; check digits (Sec 5.5), used for passport and ISBN numbers to protect against typographical erorrs; and RSA cryptography (Sec 8.4), used for internet security. We will also look at Mersenne and Fermat numbers and the worldwide collaborative effort to factor them (you can help!). If time permits, we will cover continued fractions which have an interesting relationship with the Euclidean algorithm and Fibonacci numbers and are used in factoring algorithms and approximation of real numbers. I hope that you will appreciate the beauty of number theory and acquire a taste for pursuing applications of the subject. I'd like to entice you into the cryptography course (Math 626) offered this Spring or to the new Master of Science program, Mathematical Theory of Communication Systems.

Schedule

Here is a rough idea of the amount of time I expect to spend on each topic. I am also open to suggestions if the class would like to spend more time on certain topics or cover items not listed here. Here is a rough idea of the amount of time I expect to spend on each topic. I am also open to suggestions if the class would like to spend more time on certain topics or cover items not listed here.

SECTIONS TOPICS TIME
§1.1-4, §2.1 review, Fibonacci numbers, base b representations 3 lectures
§3.1-6 primes, divisors, Euclidean algorithm, 5 lectures
unique factorization, Fermat numbers,
solving linear Diophantine equations
§4.1-5 congruences, Chinese remainder theorem, the ring Z/n , 5 lectures
solving polynomial congruences and linear systems
§5.4, §5.5, §8.3, §8.4 applications: hash functions, check digits, 3 lectures
linear cryptosystems, RSA cryptosystem
§6.1, §6.3 Fermat's little theorem, Euler's theorem 2 lectures
§7.1-4 multiplicative functions, Mersenne numbers, 5 lectures
Dirichlet product, Möbius inversion

Grading

We will have weekly assignments, two midterms and a final exam. For the weekly assignments, there will be a small number of problems (10 or so) which you should write up carefully. I will either collect these and grade them or give a short quiz with some selection of the problems.

There will be a much larger number of problems assigned to do, but not to write up formally. These form the material that you are expected to understand upon completion of this course. You can safely ignore the problems that are not assigned. The midterms and the final exam will be based on the material in the assigned problems, but will not necessarily be identical to something assigned.

Weekly work 350
Test 1 150
Test 2 150
Final 350
Total 1000

The first exam is Thurs. Oct. 12.

The second exam is Tues. Nov 21.

Assignments

First assignment sheet.
Second assignment sheet.
 Third assignment sheet.
 Fourth assignment sheet.