Course number: 21475

Fall 2005

MWF, 12:00 -12:50.

GMCS 325

San Diego State University

Final Exam: Wed. Dec. 21, 10:30-12:30

Other times: by appointment.

FIRST EXAM INFO | ||

SECOND EXAM INFO | ||

FINAL EXAM INFO | ||

SCHEDULE | COMPUTER EXPERIMENTS (pdf) | |

ASSIGNMENTS | ||

My tutorials page for Maple and Magma. |

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 complex and profound mathematical structures to solve. Number theory is considered to be one of the purest and most beautiful areas of mathematics. Over 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.1-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 courses on cryptography (Math 626) and coding theory (Math 525 and 625) and to the Master of Science program in the Mathematical Theory of Communication Systems.

- The main prerequisite is Discrete Mathematics, Math 245. It will be worthwhile to review the fundamentals of logic ("and", "or", "implies", "for all", "there exists", and negation). We will use a variety of proof methods in this course: direct proof, proof by contradiction, and mathematical induction. We use equivalence relations.
- I advise taking this course after or concurrently with Abstract Algebra, 521A.

SECTIONS | TOPICS | TIME |

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

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

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

Unique factorization, Diophantine equations. | ||

§4.1-3,5 | Congruences, the ring
. Z/n |
7 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, | 3 classes |

hash functions, check digits, | ||

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

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

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

Primitive elements in .
Z/n |

There will be 10 problem set assignments, two midterms, a computer project and a final exam.

Written assignments should be carefully and neatly presented. Computer exercises should have explanatory comments and be well organized. The relative weights of the work are given below.

Weekly work | 250 |

Computer Project | 100 |

Tests | 300 |

Final | 350 |

Total | 1000 |

I dont assign assign

For undergraduates an A is above 800, B above 700, C above 600.

For graduate students an A is above 850, B above 750, C above 650.