# MATH 115A (Number Theory) - Fall 2015, UC Davis

## Course description

This course is the first part of a two-quarter 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, but we will also refer to Chapters 1-3 of Stein'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

## Sage Examples

Distribution of Primes
Carmichael Numbers
RSA Algorithm
Discrete Logarithm
Combinatorics

## Problem sets

Homework 0: (voluntary) send me an email about yourself, your goal and expectations for the class or anything else you would like to share!

Homework 1: due October 2, 2015 in class: pdf

Homework 2: due October 9, 2015 in class: pdf

Homework 3: due October 16, 2015 in class: pdf

Homework 4: due October 23, 2015 in class: pdf

Midterm: October 30, 2015 in class 12:10-1:00pm.
The midterm will cover Sections 3 and 4.1-4.3 in Rosen's book and is based on Homeworks 1-4. In particular this includes prime numbers, distributions of primes, gcd, the Euclidean algorithm, the Fundamental Theorem of Arithmetic, factorization methods and Fermat numbers, linear Diophantine equations, congruences, linear congruences, and the Chinese Remainder Theorem. There might be a question asking you to state a definition or theorem/proposition. There will also be a question with True/False questions. The other questions will be similar to the homework problems, asking you to prove a particular statement or to give or work out an example. A sample midterm is posted on SmartSite under Resources. Solutions to the homeworks are also available there.
You will only need a pencil and eraser for the test.

No homework due on October 30!

Homework 5: due November 6, 2015 in class: pdf

Homework 6: due November 13, 2015 in class: pdf

Homework 7: due November 20, 2015 in class: pdf

Homework 8: due Wednesday November 25, 2015 in class: pdf

Homework 9: due December 4, 2015 in class: pdf

Final: Friday, December 11 at 8:00 am in Wellman 202.
The final will be comprehensive and cover everything we discussed in class. Information, review questions and sample problems are posted on SmartSite under Resources.