# Math 115: Introduction to Number Theory, Summer 2010

The course page is on bspace, but I'll also post materials here in case I (or somebody else) runs into problems with bspace.

Office Hours: Tuesdays 1:00-2:30 and Wednesdays 2:30-4:00 in 1044 Evans hall.

I write up very terse solutions for the grader, but you're welcome to look at them too.

Homework 1, due June 24, and solutions

Homework 2, due July 1, and solutions

Homework 3, due July 8, and solutions. Supplement on Hensel's Lemma from Niven-Montgomery-Zuckerman.

Homework 4, due July 15, and solutions.

Homework 5, due July 22, and solutions. Rousseau's proof of Quadratic Reciprocity.

Homework 6, due July 29, and solutions.

Homework 7, due August 5, and solutions. Supplement on Pell's equation from Silverman's book.

Homework 8, due August 11.

If you want to review them, here are pdfs of the Quizzes, Midterms, and solutions to the midterms.

You may also want to look at the exam archives for Math 115.

My notes about what I want to cover in class. They don't always correspond to what I actually cover, and they're often pretty sketchy. Use at your own risk: notes.pdf

Summary of what we did in class each day (I know it's not quite right, but it's close):

week 1

- M: Properties of divisibility and gcds. Induction. Division algorithm. Euclidean algorithm. GCD theorem.
- T: Rings, primes, and composites. Euclid's Lemma. Fundamental theorem of arithmetic.
- W: Linear diophantine equations. Prime number sieve. Infinitude of primes.
- T:(mentioned Dirichlet's Thm, Chebotarev density Thm, Prime number Thm, Riemann Hypothesis)

week 2

- M: Modular arithmetic.
- T: Euler's Thm. Fermat's Thm. Wilson's Thm.
- W: Chinese Remainder Thm.
- T: phi is multiplicative. computing phi, inverses, and powers. Miller-Rabin test. AKS test.

week 3

- M: Hensel's lemma
- T: Root bound. $(\mathbb Z/p)^\times$ is cyclic
- W: midterm 1
- T: $(\mathbb Z/p^k)^\times$ is cyclic when $p$ an odd prime

week 4

- M: Public key cryptography. RSA cryptosystem. Review Hensel's lemma.
- T: Diffie-Hellman. Attacking RSA given $\phi$. Fermat factorization method.
- W: Pollard $p-1$ method. Attacking RSA given decryption key.
- T: Quadratic sieve. Factoring given two numbers that square to same thing.

week 5

- M: Quadratic residues. Legendre symbol. Euler's Criterion.
- T: Guass's lemma. Quadratic reciprocity.
- W: Jacobi symbol. Jacobi version of quadratic reciprocity.
- T: Finding square roots mod $p$.

week 6

- M: Properties of Farey sequences. Existence of good rational approximations.
- T: Continued fractions. Computing convergents.
- W: midterm 2
- T: Which numbers are a sum of two squares.

week 7

- M: Periodic continued fractions are exactly quadratic irrationals
- T: Pell's equation
- W: Elliptic curves
- T: Group law on the points of an Elliptic curve.

week 8

- M: Lenstra's elliptic curve factorization method.
- T: Elliptic curve cryptography
- W: review
- T: final