# MATH 115A (Number Theory) - Fall 2010, 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 6, 2010 in class: pdf
Solution: pdf
Homework 2: due October 13, 2010 in class: pdf
Solution: pdf
Homework 3: due October 20, 2010 in class: pdf
Solution: pdf
Homework 4: due October 27, 2010 in class: pdf
Solution: pdf
Midterm: October 27, 2010
Solution: pdf
Homework 5: due November 3, 2010 in class: pdf
Solution: pdf
Homework 6: due November 10, 2010 in class: pdf
Solution: pdf
Homework 7: due November 17, 2010 in class: pdf
Solution: pdf
Take Home: due November 19, 2010 in class: pdf
Homework 8: due December 1, 2010 in class: pdf
Solution: pdf
Review and Practice Problems: discussed in discussion session November 30: pdf