Fall 2002

MW, 17:30 - 18:45 am.

PS-100

San Diego State University

Other times: by appointment or good fortune (I will normally be in my office and available).

SCHEDULE | COMPUTER EXPERIMENTS (pdf) | |

ASSIGNMENTS | ||

First Maple Worksheet | Second Maple Worksheet |

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. 3) and congruences (Ch. 4, Ch. 6 and parts of Ch. 9). Weaved in with these topics will be several applications of congruences: hashing functions (Sec. 5.4), used by computers to store data; check digits (Sec. 5.5), used for passport and ISBN numbers to protect against typographical erorrs; and cryptography (Secs. 8.4, 10.2), used for internet security.

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.

SECTIONS | TOPICS | TIME |

§1.1-4 | Induction, Fibonacci numbers, divisibility | 2 classes |

§2.1 | Base representations of integers r |
2 classes |

§3.1-4,6; §13.1-2 | Primes, greatest common divisor, Euclidean algorithm. | 6 classes |

Unique factorization, Diophantine equations. | ||

§4.1-3,5 | Congruences, the ring
. Z/n |
5 classes |

Solving linear and quadratic congruences and linear systems. | ||

Chinese remainder theorem. | ||

§5.1,3-5 §8.3, §8.4 | Applications: divisibility rules, tournament scheduling, | 2 classes |

hash functions, check digits, | ||

§6.1, §6.3 | Fermat's little theorem, Euler's theorem | 2 classes |

§8.1-4; §10.2 | Cryptography: linear cryptosystems, RSA, El Gamal | 3 classes |

§7.1-2; §9.1-4 | Multiplicative functions: Euler phi, sum and number of divisors. | 5 classes |

Primitive elements in .
Z/n |

We will have weekly assignments, two midterms and a final exam. Computer projects (see above) may be done for extra credit up to a total of 100 pts.

Weekly work | 350 |

Test 1 | 150 |

Test 2 | 150 |

Final | 350 |

Total | 1000 |

For the exams, I will write a list of subject matter and exercises to guide you in your study (link above). These form the material that you are expected to understand upon completion of this course. You can safely ignore material that is not included.

The first exam is tentatively Wed. Oct. 2.

The second exam is tentatively Mon. Nov. 18.

The final is Sat. Dec. 21, 8:00-10:00.