Lecture 1 (Sep 6)
We explored the structure of sets of the form aZ+bZ. After some playing around, we decided this always took the form dZ, where d is the greatest common divisor of a and b. We made some progress towards proving this.
Lecture 2 (Sep 10)
We proved (after some insights) that aZ+bZ = dZ, where d is the gcd of a and b. We then started discussing the Fundamental Theorem of Arithmetic.
Lecture 3 (Sep 13)
We proved the Fundamental Theorem of Arithmetic.
Lecture 4 (Sep 17)
We discussed the Euclidean algorithm, then turned to irrationality proofs.
Lecture 5 (Sep 20)
We gave a fourth proof of the irrationality of √2. Then we explored one application of the Euclidean algorithm to solving some linear equations. Finally we turned to the distribution of primes. We gave Euclid's proof that there are infinitely many primes, and then used the main idea from the proof to give an upper bound on the n-th prime.
Lecture 6 (Sep 24)
We used our work from last time to obtain an explicit lower bound on the growth of π(x), but our bound was terrible. We started working towards an improvement, in particular proving a neat upper bound due to Chebyshev and Ramanujan. Along the way we described the Prime Number Theorem and introduced some useful notation for measuring how quickly a function grows.
Lecture 7 (Sep 27)
We completed the proof of Chebyshev's theorem.
Lecture 8 (Oct 1)
We discussed the prime number theorem, in particular explicitly stating one of the biggest unsolved problems in all of mathematics (the Riemann Hypothesis). Next we turned to the study of modular arithmetic. To motivate this, we played around with the Doomsday algorithm, John Conway's crazy method of calculating the day of the week from a given date.
Lecture 9 (Oct 4)
We explored the world of modular arithmetic, in particular examining some multiplication tables. This led us to the discovery of the `sudoku rule' as well as to Fermat's Little Theorem.
Lecture 10 (Oct 11)
Considering the Sudoku Rule a bit more carefully motivatived us to define the set Znx. This in turn led us to discover Euler's theorem, which generalizes Fermat's Little Theorem from last time.
Lecture 11 (Oct 15)
After introducing a new (useful) notation for discussing fractions (mod n) -- which, in turn, led us to a brief discussion of Egyptian fractions and the Erdos-Straus conjecture -- we explored Euler's totient function φ(n). We collaboratively discovered a nice formula for φ(pk). After some more playing around we discovered that φ seems to be multiplicative, although it wasn't clear how to prove this. We then explored an interesting question of Oliver concerning whether φ(mn) can equal φ(m)φ(n) when m and n aren't coprime. Finally, we found combinatorial interpretations of φ(m), φ(n), φ(m)φ(n), and φ(mn) that point towards a proof that φ is multiplicative.
Lecture 12 (Oct 18)
Today we proved that the totient function φ is multiplicative. Along the way we discovered an explicit bijection between the sets Zmnx and Zmx x Znx.
Lecture 13 (Oct 22)
Today we explored power congruences. After considering a number of examples, we came up with an algorithmic approach.
Lecture 14 (Oct 25)
Today we discussed cryptography, in particular describing a cool application of our work on power congruences: the RSA encryption algorithm.
Lecture 15 (Oct 29)
Today we began exploring quadratic congruences, which our earlier trick failed to solve. Although we were unable to find a nice way to determine a square-root of a given integer a (mod p) in general, we came up with a nice way of testing whether or not a given integer has a square-root (mod p); this is called Euler's criterion. This inspired us to define the Legendre symbol, which we proved is periodic and completely multiplicative. We ended by coming up with an explicit formula for when -1 has a square-root (mod p).
Lecture 16 (Nov 1)
Today we practiced computing with the Legendre symbol. In particular, using a combination of tools (all boiling down to Euler's criterion) we were able to compute several complicated-looking examples with relative ease. Motivated by some harder examples, we saw that all our computations can be reduced to figuring out Legendre symbols of the form (q/p), where q and p are primes. Although there's no nice formula for this, there is a beautiful formula -- the Law of Quadratic Reciprocity -- relating (q/p) to (p/q). After stating QR, we displayed its utility in computing Legendre symbols. Finally, we discussed one important ingredient in our proof of QR: the Chinese Remainder Theorem, which we already proved earlier in the course.
Lecture 17 (Nov 5)
Today we proved Quadratic Reciprocity, using the proof discovered by George Rousseau in 1991 (and independently re-discovered by high-schooler Tim Kunisky in 2008). Although not short, it is completely elementary, and the easiest-to-remember proof that I know.
Lecture 18 (Nov 8)
Today we outlined a method for solving quadratic congruences (mod p). We also showed that, even though we seemingly only considered a special type of quadratic congruence, we secretly have discovered a method for solving all quadratic congruences (mod p). We then discussed how to solve quadratic congruences (mod pq). Then we turned to totally new problem: which integers can be written as the sum of two squares?
Lecture 19 (Nov 12)
Today we completely characterized which integers can be written as the sum of two squares. We did this by rephrasing the problem in the language of Gaussian integers, and then studying arithmetic in that set (in particular, prime factorization). Along the way, we proved Fermat's Two-Squares Theorem: an odd prime can be written as the sum of two squares if and only it's one more than a multiple of 4.
Lecture 20 (Nov 15)
Today we completed our characterization of the numbers that can be written as a sum of two squares, and discussed other theorems involving squares, namely Lagrange's four-square theorem, Legendre's three-square theorem, Jacobi's four-square theorem, and recent work of myself with Paul Pollack.
Lecture 21 (Nov 19)
We started by exploring a nice infinite product. This led us to Euler's pentagonal number theorem, which we made sense of by playing around with triangular and pentagonal numbers. We then formulated Fermat's polygonal numbers conjecture (now a theorem, proved by Cauchy) that subsumes Lagrange's Four-Squares theorem. Finally, we turned to our last topic involving sums of squares: the study of pythagorean triples. We translated this problem into the study of rational points on the unit circle.
Lecture 22 (Nov 26)
Motivated by our problem from last class (trying to characterize all pythagorean triples), we characterized all rational points on the unit circle. We did this by finding a bijection between the unit circle and the y-axis that preserves rationality. We then applied our understanding of rational points to give a complete description of all primitive pythagorean triples. Finally we turned to Fermat's Last Theorem, in particular considering the equation x3+y3=z3. Following our previous model, we need to find rational points on the curve x3+y3=1. A change of variables shows that this is equivalent to finding all rational points on y2=x3-432. The rest of the term will be devoted to studying rational points on curves of this type (called elliptic curves).
Lecture 23 (Nov 29)
We first reduced the n=3 case of Fermat's Last Theorem to showing that the only rational points on the elliptic curve y2=x3+16 are (0,±4). This inspired us to consider rational points on other elliptic curves. In particular, we discovered a group law on the set of all rational points and stated Mordell's theorem that this group is finitely generated. We also discussed where the name `elliptic curve' comes from.
Lecture 24 (Dec 3)
Last class, Mazur's theorem came up as a limitation on the number of rational points an elliptic curve can have. This time we gave a much more precise version of Mazur's theorem: it's a result not just about the number of rational points, but about their relationship to one another. This forced us to formulate the notion of isomorphism, which we did by playing a few rounds of the Game of 15. This in turn led us to the notion of the rank of an elliptic curve, and we briefly discussed what's known and unknown about the rank. We then took an unexpected turn and considered points of Zp on an elliptic curve. After discussing the Hasse bound and the Sato-Tate conjecture (now a theorem!), we turned to one of the outstanding conjectures of number theory: the Birch and Swinnerton-Dyer conjecture. Finally, we gave an overview of the proof of Fermat's Last Theorem. Next time, we'll see a concrete application of the theory of elliptic curves to cryptography: the Diffie-Hellman Key Exchange.
