# Syllabus 115A: Theory of Numbers Fall 2003

Note: The final exam is on Saturday December 13 at 1:30-3:30pm in 118 Olson.

During finals week, I will have office hours Friday Dec. 12 at 9-10am.
Philip Sternberg our new TA has office hours Monday Dec. 8 at 11-12am, Wednesday Dec. 10 at 3-4pm, Thursday Dec. 11 at 11-12am and 2-3pm, Friday Dec. 12 11-12am.

Practice problems: ps or pdf

The final is comprehensive and will be based on everything we did in class. Here is a list of topics:
• integers, well-ordering principle, induction, Fibonacci numbers; sec 1.1 and 1.3
• divisibility; sec. 1.4
• prime numbers, distribution of primes, conjectures about primes; sec 3.1
• greatest common divisor, least common multiple; sec. 3.2
• Euclidean algorithm; sec. 3.3
• fundamental theorem of arithmetic and applications, Dirichlet progressions, irrational numbers; sec. 3.4
• Fermat factorization; sec. 3.5
• linear Diophantine equations; sec 3.6
• perfect numbers, Mersenne numbers; sec. 7.3
• congruences; sec. 4.1
• linear congruences; sec. 4.2
• Chinese remainder theorem; sec. 4.3
• Wilson's and Fermat's little theorem; sec. 6.1
• primality testing and Carmichael numbers; sec. 6.2
• Euler's theorem; sec. 6.3
• properties of the Euler Phi function; sec. 7.1
• sum and number divisors; sec. 7.2
• Moebius inversion; sec. 7.4
• Public-key cryptography, RSA encryption method, knapsack ciphers; sec. 8.4 and 8.5
• Digital signatures, Diffie-Hellman key exchange; sec. 8.6
• All homeworks

 Lectures: MWF 12:10-1:00pm, Olson 118 Instructor: Anne Schilling, Kerr Hall 578, phone: 754-9371, anne@math.ucdavis.edu Office hours: M 3:30-4:30pm, F 9-10am or by appointment New T.A.: Philip Sternberg, Kerr 565, sternberg@math.ucdavis.edu Office hours: M 11-12am, T 10-11am Text: I will mostly follow K.H. Rosen, Elementary Number Theory, Addison-Wesley, ISBN 0-201-57889-1, but I will not require students to purchase the book! Pre-requisite: MAT 21D, MAT 108 or permission by instructor Problem Sets: There will be weekly homework assignments, handed out on Wednesday, due the following Wednesday. You are encouraged to discuss the homework problems with other students. However, the homeworks that you hand in should reflect your own understanding of the material. You are NOT allowed to copy solutions from other students or other sources. If you need help with the problems, come to office hours! The best way to learn mathematics is by working with it yourself. No late homeworks will be accepted. Exams: There will be two Midterms October 20 and November 21 in class. The Final exam will be Saturday December 13 at 1:30pm. There will be no make-up exams! Grading: The final grade will be based on: Problem sets 20%, Midterms 20% each, Final 40% Web: http://www.math.ucdavis.edu/~anne/FQ2003/115A.html

## Course description

This course is the first part of a year-long introduction to Number Theory. Number theory is the study of properties of numbers in particular the integers and rational numbers. Questions in elementary number theory include divisibility properties of integers (e.g. the Euclidean algorithm), properties of primes (e.g. there are infinitely many), congruences, quadratic reciprocity and integer solutions to basic equations (e.g. Diophantine equations). Even though number theory is one of the oldest disciplines in mathematics, it has recently contributed to many practical problems such as coding theory, cryptography, hashing functions or other tools in modern information technology. These applications will also be part of this class! The class is primarily based on Chapters 1-8 of Rosen's book.

1. Prime factorization
prime numbers, Euclidean algorithm, the fundamental theorem of arithmetic, factorization methods, linear diophantine equations

2. Congruences
linear congruences, Chinese remainder theorem, Wilson's, Fermat's and Euler's theorem, Euler's Phi-function

3. Applications to Congruences (time permitting)
divisibility tests, hashing functions, public-key cryptography

## Problem sets

Homework 1: due October 8, 2003 in class: ps or pdf
Solutions: ps or pdf

Homework 2: due October 15, 2003 in class: ps or pdf
Solutions: ps or pdf

Homework 3: due October 22, 2003 in class: ps or pdf
Solutions: ps or pdf

Homework 4: due October 29, 2003 in class: ps or pdf
Solutions: ps or pdf

Homework 5: due November 5, 2003 in class: ps or pdf
Solutions: ps or pdf

Homework 6: due November 12, 2003 in class: ps or pdf
Solutions: ps or pdf

Homework 7: due November 19, 2003 in class: ps or pdf
Solutions: ps or pdf

Homework 8: (last one!) due November 26, 2003 in class: ps or pdf
Solutions: ps or pdf
anne@math.ucdavis.edu