Here's a copy of the midterm and here are my solutions.
Problem Set 1 due Wednesday, September 29. Solutions thanks to our CA Seungki.
Problem Set 2 due Wednesday, October 6. Solutions thanks to our CA Seungki.
Problem Set 3 due Wednesday, October 13. Solutions thanks to our CA Seungki.
Problem Set 4 due Wednesday, October 20. Solutions thanks to our CA Seungki.
Problem Set 5 due Wednesday, October 27. Solutions thanks to our CA Seungki.
Problem Set 6 due Wednesday, November 3. Solutions thanks to our CA Seungki.
Problem Set 7 due Wednesday, November 10. Solutions thanks to our CA Seungki.
Problem Set 8 due Wednesday, November 17. Solutions thanks to our CA Seungki.
Problem Set 9 due Wednesday, December 1. Solutions thanks to our CA Seungki.
Sept 22: Estimates for the size of n!. O-notation. Chebyshev estimates for the number of primes up to x. Notes on Bertrand's postulate.
Sept 27: Congruences. The additive group of residue classes mod n. The multiplicative group of reduced residues mod n. Proof that multiplicative inverses exist; solving ax congruent to b mod n, when (a,n) = 1. Wilson's theorem (p-1)! is -1 mod p. Euler's phi function. Euler's theorem and Fermat's little theorem. Order of an element; Lagrange's theorem that it divides the order of the group (for reduced residues). Diffie Hellman key exchange.
Sept 29: RSA public key cryptosystem. Solving two linear congruences simultaneously. The chinese remainder theorem . Euler's phi function is multiplicatice. The structure of Z/nZ (the additive group of residue classes); cyclic. Structure of the multiplicative group: reduction to prime powers via chinese remainder theorem. Stated when primitive roots exist: when n=p^a or 2p^a for an odd prime p, or n= 2 or n=4.
Oct 4: Polynomial congruences. The congruence mod p has no more than the degree number of solutions (assuming that the leading coefficient is coprime to p). The conguence may have many more solutions to composite moduli. Existence of primitive root mod p: first show that if q^{alpha} exactly divides p-1 then there is an element of that order. Then if a has order m, and b has order n, and m and n are coprime then ab has order mn. Conclude that there are primitive roots mod p. If d divides p-1 then there are exactly phi(d) residue classes of order d.
Oct 6: Recap of proof of primitive roots mod p. Lifting primitive roots to mod p^2: Take g a primitive root mod p and look at g+kp for 0\le k\le p-1. Exactly one of these has order p-1 (mod p^2) and the rest are primitive roots mod p^2. A primitive root mod p^2 lifts to give p primitive roots mod p^3. And so on. The case of powers of 2 is a little different; stated but not proved. Quadratic congruences. Completing the square; quadratic residues and non-residues; Legendre symbol.
Oct. 11: Euler's criterion. Law of quadratic reciprocity. Proof of quadratic reciprocity. Condtion for 2 to be a quadratic residue mod p. Condition for -1 to be a quadratic residue mod p.
Oct 13: Knowing whether n is a quadratic residue mod p can be described in terms of p (mod 4n). Ostrowski's Theorem.
Oct 18: Sums of two squares. If m and n are sums of two squares then so is mn. Primes that are 1 mod 4 are sums of two squares. Proof I by descent on the smallest multiple of p which is a sum of two squares. Proof II by Dirichlet's theorem on diophantine approximation. Proof III via the Gaussian ring of integers (begun).
Oct 20: Midterm.
Oct 25: Arithmetic in the gaussian ring of integers. The norm map. Division algorithm. Euclidean algorithm. Irreducibles are the same as primes. Proof that every rational prime which is 1 mod 4 splits in Z[i]. Failure of unique factorization in Z[\sqrt{-5}].
Oct 27: Notes on Dirichlet's theorem: the Riemann zeta function and Dirichlet's theorem (mod 4).
Nov 1: Notes on Dirichlet's theorem.
Nov 3: Notes on Dirichlet's theorem: characters and orthogonality relations.
Nov 8: Notes on Dirichlet's theorem.
Nov 10: See Nov 8 notes.
Nov 15: See Nov 8 notes.
Nov 17: See Nov 8 notes.
Nov 29: Positive definite binary quadratic forms. Reduction theory: |b|\le a\le c. The class number.
Dec 1: A number is properly represented by some binary quadratic form of discriminant D if and only if D is a square mod n. Applications to the primes of the form x^2 +y^2, x^2+2y^2, x^2+3y^2, x^2+5y^2 (genus theory). Dirichlet's class number formula for negative discriminants. Euler's polynomial: n^2+n+41, and the discriminant -163.