# Lectures

Below you will find lecture notes, brief listing of topics, etc. This page will be updated often (both before and after the relevant lectures).

• Monday, January 14th:
• introduction to the class
• motivational questions in number theory: questions and answers
• Wednesday, January 16th:
• Friday, January 18th:
• We covered Division Algorithm, divisibility, gcd, basic definitions and properties
• We revisted the classroom activity from last time, briefly played with legos, and then gave a proposition and associated challenge described in this post.
• Wednesday, January 23rd:
• We explored and finally formalized the Euclidean Algorithm.
• For those interested in the efficiency of the Euclidean algorithm with least positive vs. smallest absolute value remainder, here’s a paper (you may need campus wifi to access this).
• Friday, January 25th:
• Today, we did a worksheet exploring solving Linear Diophantine Equations, available here. Note: the word ‘contrapositive’ should have been ‘converse’ three times on page 5 in the printed version you have. It has been corrected here. We discussed/completed pages 1, 2 and 3.
• Monday, January 28th:
• We continued discussing Linear Diophantine Equations using the worksheet. We gave a detailed proof of the solution set for the Homogeneous case. This depended upon Theorem 1.23 from the text, which I proved (in the same method as the text).
• Wednesday, January 30th:
• Friday, Feb 1st:
• Monday, Feb 4th:
• Quizzes were handed back, together with solutions and a handout about writing definitions, which we discussed.
• We began studying the primes by realizing that prime factorization, while familiar, is amazing and mysterious. We proved that every integer greater than 1 is divisible by a prime, and proved there are infinitely many primes (following the text, mostly). We began discussing the prime counting function, i.e. how many primes there are.
• A very enjoyable article about prime number counts is called Prime Number Races.
• Here’s a picture of a Sieve of Eratosthenes. You may enjoy looking up the sieve on Wikipedia, as well as prime counts.
• Wednesday, Feb 6th:
• We enjoyed two beautifully done visualizations to do with primes and factorizations:
• We proved unique prime factorization in the integers.
• Friday, Feb 8th:
• I proved the proportion of coprime integers. See this article or alternate link (you need campus internet or proxy to access; or search it in cu libraries and use your identikey), for the source of this proof. We then gave Euler’s argument for the Basel Problem (upon which this proof depends). Here’s a beautiful 3blue1brown video of a proof of the Basel Problem.
• The (Frobenius) Postage Stamp Problem or Chicken Nugget Problem was the optional extra credit exploration on homework (what values can’t be obtained by positive linear combinations). Here’s some info on it.
• The Tortoise and Hare problem and its variations is a classic brainteaser, and we will meet it again with Chinese Remainder Theorem later in the course. Here’s a hint.
• Monday, Feb 11th:
• We finished Chapter 2, in particular sum-of-divisors functions (pages 63-69). I do not place much emphasis on Mersenne primes and perfect numbers.
• Wednesday, Feb 13th:
• We had a handout on axioms of the integers, which we discussed out loud.
• We discussed defining the rationals as a subset of the reals, and by means of an equivalence relation on pairs of integers. (A useful overview is given in the first four pages of these slides.)
• We covered pages 75-77 of the text.
• Friday, Feb 15th:
• We covered Proposition 3.5.
• You may be curious for a proof that pi is irrational or that e is irrational.
• If you add/subtract/divide/multiply irrationals/rationals, what is the result, irrational or rational? (We analyzed all situations; you should be able to give proofs of any case.)
• Between any two real numbers, there is both a rational and an irrational number. (We proved this.)
• The proof that there exist two irrational numbers a and b so that ab is rational. This can be found in Section 7.4 of The Book of Proof, available as online PDF.
• We discussed more generally what is known and not known about rational and irrational numbers.
• Monday, Feb 18th:
• Here’s a Numberphile video (7 minutes) on greek constructions.
• We covered commensurable numbers, rational root theorem, Pythagorean triples.
• Here is a wonderful 3blue1brown video (15 minutes) that visualizes Pythagorean Triples.
• Wednesday, Feb 20th:
• We discussed how the rationals are arranged in the real line by drawing FOUR pictures:
• Here’s a great visual blog post showing how to see the Farey fractions when you are driving past a corn field.
• Friday, Feb 22nd:
• Monday, Feb 25th:
• Latex Workshop day (see Latex Tutorial page in the menu above).
• Wednesday, Feb 27th:
• We finished showing the Farey tree built using mediants contains all the rational numbers, and then we showed two fundamental theorems of Diophantine Approximation using the Ford circles (following your textbook, end of Chapter 3).
• Associated Mathologer video.
• Friday, Mar 1st:
• We exhibited a transcendental number and then did the basics of modular arithmetic. Don’t be fooled! Modular arithmetic is not trivial. We discussed how properly to define it and prove that the arithmetic is well-defined.
• Monday, Mar 4th:
• This was a Sage Workshop (see menu above).
• Wednesday, Mar 6th:
• We talked about modular arithmetic. Specifically, we showed arithmetic is well-defined and talked about some common pitfalls (cancellation, simplifying exponents), some uses (e.g. Diophantine equations), etc.
• Friday, Mar 8th:
• Monday, Mar 11th:
• Wednesday, Mar 13th:
• Friday, Mar 15th:
• Week of Mar 18th-22nd:
• Monday, April 1st:
• Review of the very important topics of Modular Dynamics, including Euler’s Theorem / Fermat’s Little Theorem.
• Wednesday, April 3rd:
• Friday, April 5th:
• We finished the Diffie-Hellman worksheet outdoors in the sunshine. Those who were further along were challenged to discover and implement a 3-way Diffie-Hellman.
• Monday, April 8th:
• Review of discrete logs, primitive roots and Diffie-Hellman
• Began to prove that there is a primitive root modulo p for any prime p (will finish on Wed).
• Wednesday, April 10th:
• We finished the proof of the existence of primitive roots modulo p. Here’s the handout.
• Introduced the idea of Chinese Remainder Theorem, just a bit.
• Here’s a Computerphile video some students pointed out to me explaining the big idea of Diffie-Hellman Key Exchange.
• Friday, April 12th:
• Monday April 15th:
• Wednesday, April 17th:
• More Chinese Remainder Theorem! We covered examples of how to use it to compute things like inverses and square roots by breaking the problem down into pieces.
• We began a proof of the multiplicativity of phi and will finish it on Fri.
• Friday, April 19th:
• We discussed multiplicativity of phi, and other computational aspects of Chinese Remainder Theorem.
• We had a challenge to compute the last two digits of 3^3^5 efficiently. This used Chinese Remainder Theorem, computation of Euler phi function, and Fermat-Euler Theorem.
• Monday, April 22nd:
• We talked about lifting, particularly lifting inverses modulo powers of p.
• Wednesday, April 24th:
• We had an introduction to quadratic residues and non-residues covering Chapter 8 up to about page 199.
• Friday, April 26th:
• More about quadratic residues and non-residues, including the reciprocity law for 2 modulo p.
• Monday, April 29th:
• All about permutations and how to compute the sign of a permutation.
• Wednesday, May 1st:
• Example of using quadratic reciprocity.
• Zolotarev’s Proof of Quadratic Reciprocity. My notes.