Math 453, Section X, Elementary Number Theory, Spring 2011
Professor A.J. Hildebrand

Final Exam and Course Grades

Course grades were assigned on a linear scale, based on the overall average, which in turn was computed using the weights of 1/3 final, 1/6 homework, and 1/2 midterms announced at the beginning of the class. The cutoffs for letter grades were a bit more generous than those in place after the midterms. In addition, I manually adjusted some of the grades upwards to avoid hardships. As a result, nobody was within one percentage point of the next higher grade; in fact, most gaps between grades were 2 percentage points or more.

Course Policies, Exams, Grades

• Course Information Sheet. The first-day handout. Everything you need to know about this class: Syllabus, grading policies, office hours, etc.
• Midterm Exam 1: Wednesday, February 23.
  • Syllabus and Study Guide
  • Exam 1 Solutions
• Midterm Exam 2: Wednesday, April 13.
  • Syllabus and Study Guide
  • Exam 2 Solutions
• Final Exam: Wednesday, May 11, 7 pm - 10 pm.
  • Final Exam Syllabus and Study Guide
  • Final Exam Solutions
• Online Scores. Log in with your Net-ID and password. The display shows the scores on all assignments and exams given out so far.

Announcements

• Open House Hours: Wednesdays/Thursdays, beginning at 5 pm. Also Sundays beginning at 3 pm, in 159 Altgeld (or an adjacent classroom in case 159 is taken). I'll stay as long as necessary.
• Add/drop deadlines: Monday, January 24 is the last day to add a course. If you want to switch to another section, you have to do so by this day. The deadline for dropping a course is March 11.

Class Notes

Note:The numbering of the first five chapters is the same as in Strayer. Chapter 6 of the notes (Continued Fractions) corresponds (roughly) to Chapter 7 in Strayer, and Chapter 7 of the notes (Primality Testing and RSA Encryption) corresponds to Sections 8.2 and 8.3 in Strayer.

• Chapter 1.
• Chapter 2.
• Chapter 3.
• Chapter 4.
• Chapter 5.
• Chapter 6.
• Chapter 7.

Class Diary

• Wednesday, 5/4:
  • Lecture: Last day of class. Discussed a real world RSA example, generated by the openssl utility. Handed out final set of class notes, on RSA encryption.
  • Some links:
    • RSA Laboratories. The company behind the RSA system.
    • The Mathematics of the RSA Public-Key Cryptosystem. A very readable and nontechnical article by Burt Kaliksi, a pioneer in cryptography and co-founder of RSA Laboratories.
• Monday, 5/2:
  • Lecture. The general idea behind encryption schemes. "Public" (open) versus "private" (secret) keys. One-way functions with (secret) backdoor. The RSA encryption scheme: Description of encryption and decryption algorithms, why it works, and why it is secure.
  • Read: Strayer, Sections 8.2 and 8.3. Section 8.2 gives a rather readable account of the RSA algorithm, and Section 8.3 discusses some primality tests. I'll distribute additional materials on Wednesday, including the final installment of the class notes, on the RSA algorithm.
• Friday, 4/29:
  • Lecture. The primality tests of Lucas and Pepin. Euler's theorem for prime factors of Fermat numbers. World record (nontrivial) composite number: 2^(2^2478782)+1 (Cosgrave/Gallot, 2003; see the links below).
  • For fun: Here are some links about the above "record composite":
    • Prime factors of Fermat numbers. An encyclopaedic site with all sorts of records on Fermat numbers, their primality status, and factors found.
    • Fermat Number Record. From John Cosgrave, holder of many Fermat number records, including the above world record composite Fermat number. Provides some fascinating details on how such records were found, including computer screen shots, and a link to the program used (a Windows 95 .exe file!).
    • Cracking Fermat Numbers. An article about these discoveries. by Ivars Peterson. Nontechnical, and very readable.
• Wednesday, 4/27:
  • Lecture. Basic primality tests: trial division, Wilson test, Fermat test. Advantages and drawbacks of each. Underlying theory,
• Monday, 4/25:
  • Lecture. Primality testing and integer factoring, overview. Testing for primality versus factoring. What is known and what is not known about these problems. Primality and factoring status of Fermat numbers.
  • Related links. Here are some sites with more information about these topics.
    • "Primes is in P" FAQ. Answers some basic questions about the AKS polynomial time primality test. Nontechnical and very readable.
    • Prime factors of Fermat numbers. Up-to-date information on factoring status of Fermat numbers.
    • The Prime Pages. The place to go for anything about primes.
• Friday, 4/22:
  • Lecture: Started final topic of the course: Computational aspects of number theory. Examples of numbertheoretic problems that are computationally easy and of problems that are computationally hard. One-to-one functions that are easy to compute in one direction and hard to compute in the reverse direction.
• Wednesday, 4/20:
  • Lecture. Wrapped up Continued fractions. Proof of the best approximation property. Some applications: leap year schemes in calendars. Musical scales.
• Monday, 4/18:
  • Lecture. Continued fractions, proof of convergence properties.
  • Handout: Continued Fractions: Definitions and Theorems.
  • Read: Strayer, Sections 7.2 - 7.5
  • Homework Assignment 9, due Monday, 4/25.
• Friday, 4/15:
  • Lecture. Continued fractions, continued: Recursion formulas for p_i's and q_i's. Matrix interpretation.
• Wednesday, 4/13: Midterm Exam 2.
• Monday, 4/11:
  • Lecture. Continued fractions, general theory: Basic definitions and notations: finite and infinite c.f.'s, simple c.f.'s, convergents, etc.
• Friday, 4/8:
  • Lecture. More fun with continued fractions. CF expansion of Golden Ratio, and Fibonacci ratios. Geometric interpretation of CF algorithm as tiling of rectangles by squares.
• Wednesday, 4/6:
  • Lecture. Continued fractions: Motivation and introductory examples, Famous rational approximations to pi, and their connection to CF expansion of pi.
  • Handout. Continued Fraction Approximation to pi.
  • Just for fun: World record computations for pi.
    • Pi to 2,700 billion digits. (World record by Fabrice Bellard, February 2010, using a desktop computer.)
    • Pi to 5 trillion digits. Current world record (as of March 2011), set by Alexander Yee and Shigeru Kondo.
    • Wikepedia page on computations of pi
• Monday, 4/4:
  • Lecture. Classification of real numbers: Integers, rationals, algebraic numbers, and transcendental numbers. Representation of rational numbers in decimal. Period of decimal expansion of 1/p, and connection to orders and primitive roots. (This is a prelude to Chapter 7, the final chapter in the course, which will focus on continued fractions; we will skip Chapter 6.)
• Friday, 4/1:
  • Lecture: Finished Chapter 5. Primitive roots and reduced residue systems. The Primitive Root Theorem. Application to card shuffling.
  • Mathematics and Magic Tricks. An article by famed magician/mathematician Persi Diaconis on the card shuffling problem discussed in today's class.
  • Read: Strayer, Section 5.3.
  • Homework 8 due date moved back: Acceding to popular demand, I have moved the due date for HW 8 to Monday, April 11. (This is the Monday before the second midterm. I will pass out solutions that day.)
• Wednesday, 3/30:
  • Lecture: Orders and primitive roots, continued. Numerical illustration for primes p=7 and p=11. General theory: number of primitive roots, number of residues with given order, etc.
  • Handout: Chapter 5: Definitions and Theorems.
  • Read: Strayer, Sections 5.1 and 5.2
  • Homework Assignment 8, due Friday, 4/8.
• Monday, 3/28:
  • Lecture. Wrapped up the discussion of quadratic residues; computation of Legendre symbol (a/p) when a is fixed and p varies. Started Chapter 5 on primitive roots. Motivation and first examples.
  • Read. Strayer, Section 5.1
• Friday, 3/18:
  • Lecture. The Quadratic Reciprocity Law, and First and Second Supplementary Laws. Computation of quadratic residues using QRL and properties of Legendre symbol.
  • Read. Strayer, Section 4.3
• Wednesday, 3/16:
  • Lecture: Quadratic residues and the Legendre symbol. Recap and proofs of key results.
    A real world application: Quadratic residue diffuser. If you are interested, here are some links:
    • Quadratic Residue Diffuser Calculator. A tool to compute the dimensions of a "diffusing" wall with a quadratic residue pattern. Given a modulus (a prime up to 47) and the minimum and maximum well depths, the tool calculates the well depths based on a quadratic residue pattern.
    • Diffusers. A nice article on diffusers.
  • Read: Strayer, Section 4.1.
  • Homework Assignment 7, due Monday, 4/1.
• Monday, 3/14:
  • Lecture. I started Chapter 4. Quadratic residues and nonresidues. Overview and motivation. Terminology and notation. The Legendre symbol. Euler's Criterion.
  • Read. Section 4.1
• Friday, 3/11:
  • Lecture. Wrapped up Chapter 3 with some interesting applications of Dirichlet product machinery: Evaluation of the series over mu(n)/n^2. Computation of the probability that two random integers are relatively prime.
• Wednesday, 3/9:
  • Lecture: Revisited some results on arithmetic functions from the Dirichlet product perspective: multiplicativity of phi and other functions, Gauss and Moebius identities, Moebius inversion formula.
  • Handouts: Definitions and Theorems, Chapter 3. (Complete version.)
• Monday, 3/7:
  • Lecture: The Moebius function. The Moebius Inversion Formula. Algebraic theory of arithmetic functions, the Dirichlet product.
  • Read: Strayer, Section 3.6.
  • Homework Assignment 6, due Monday, 3/14.
• Friday, 3/4:
  • Lecture: More about the divisor function and the sum-of-divisors function. Perfect numbers: History, conjectures, and connection with Mersenne primes.
  • Read: Strayer, Section 3.5.
• Wednesday, 3/2:
  • Lecture: Euler phi function wrap-up. The role of the FTA and CRT in the analysis of phi values. Gauss' Theorem. The divisor and sum-of-divisors functions.
  • Read: Strayer, Sections 3.3 and 3.4.
• Monday, 2/28:
  • Lecture: More on the Euler phi function. Special values of the Euler phi function. Connection with Fermat primes.
  • Read: Strayer, Section 3.2.
  • Homework Assignment 5, due Monday, 3/7.
• Friday, 2/25:
  • Lecture: Fun stuff about the Euler phi function. Connection with lattice points visible from the origin, and reduced fractions in the interval (0,1]. Carmichael's conjecture.
• Wednesday, 2/23: Midterm Exam 1.
• Monday, 2/21:
  • Lecture: The Euler phi function. Euler's generalization of Fermat's Theorem, and applications to more congruence magic. Reduced systems of residues. Evaluation of the phi function. Values at primes and prime powers. Multiplicative property.
  • Read: Strayer, Section 2.6.
• Friday, 2/18:
  • Lecture: Applications of the Chinese Remainder Theorem.
  • Handouts: The Chinese Remainder Theorem in action. A concrete example showing the "encoding" provided by the CRT of residue classes modulo 5 x 7.
    Chinese Remainder Theorem: The Original. A Chinese manuscript containing the first known instance of a "Chinese Remainder" type problem.
• Wednesday, 2/16:
  • Lecture: Fermat and Mersenne numbers/primes. Compositeness of numbers of the form 2^n-1 (with n composite) and 2^n+1 (with n not a power of 2).
  • Read: Strayer, Sections 2.4 and 2.5.
  • Handout: Primes of the form 2^n-1 and 2^n+1.
• Monday, 2/14:
  • Lecture: The Theorems of Fermat and Wilson. Further applications of congruences.
  • Read: Strayer, Sections 2.4 and 2.5.
  • Handout: The Theorems of Fermat and Wilson.
  • Homework Assignment 4, due Monday, 2/21.
    Correction: In Problem 11, the first term was missing a factor 453. The formula should therefore read 453 x 347^n + 408^(n+1).
• Friday, 2/11:
  • Lecture: More congruence magic. Quick computation of remainders of large powers. Check digit schemes.
• Wednesday, 2/9:
  • Lecture: More divisibility tests. Congruences as equivalence relations. Equivalence classes for congruences ("congruence classes"). Complete residue systems.
  • Read: Strayer, Section 2.1, and 2.2. Also, read/review the section "Equivalence Relations" in Appendix B
• Monday, 2/7:
  • Lecture: Started Chapter 2. Congruences. Definition and basic properties. Divisibility tests.
  • Read: Strayer, Section 2.1.
  • Homework Assignment 3, due Monday, 2/14.
• Friday, 2/4:
  • Lecture: The Fundamental Theorem of Arithmetic: meaning, significance, consequences, and applications.
• Wednesday, 2/2: Snow day. All classes cancelled. Enjoy and stay warm!
  • Do: Try to spend some of the extra free time productively, work on the homework, and read up on the Fundamental Theorem of Arithmetic (Section 1.5 in Strayer).
  • Some Hints for HW 2: Problem 76: Focus first on a concrete case, for example p=2 and 20! = 1 x 2 x 3 x 4 x 5 x .... x 20, and count how many times 2 occurs in this product. Try to detect the underlying pattern.
    Problem 78: If the number 1 + 1/2 + ... + 1/n were an integer, then any integer multiple of it would als be an integer. Try to find a multiplier that clears all but one of the denominators, so that the resulting number is an integer plus a (non-integer) rational. In the case n is a prime number, this is easier, so focus on that case first.
  • Open House Hours: Because of the weather, I won't have an Open House today, but will be available in the classroom (343 Altgeld) at the regular class timeslot (noon). Tomorrow's Open House will be as usual at 5 pm in 159 Altgeld. I am also available Friday afternoon after 2 pm. (I have another class in the same room, 343 Altgeld, at 1 pm, but am free after that.)
• Monday, 1/31:
  • Lecture: Wrapped up the discussion of the gcd. Using the Euclidean algorithm "in reverse" to express gcd(a,b) as a linear combination of a and b. The least common multiple.
  • Read: Strayer, Section 1.5.
  • Homework: Homework Assignment 2, due Monday, 5/7.
• Friday, 1/28:
  • Lecture: Prime Day: Famous results, problems, and some historical trivia about primes. Proof of Euclid's Theorem.
  • Read: Strayer, Section 1.2.
• Wednesday, 1/26:
  • Lecture: More on the gcd. The Euclidean Algorithm. Connection with the equation ax + by = c and linear combinations of a and b.
  • Read: Strayer, Sections 1.3 and 1.4.
• Monday, 1/24:
  • Lecture: The greatest common divisor. Definition, examples, and basic properties. The coin change, Chicken McNuggets, football/rugby scores problems.
  • Read: Strayer, Section 1.3.
  • HW 1. The first graded assignment, due Monday, 1/31.
• Friday, 1/21:
  • Lecture: Properties of divisibility. The division algorithm. Primes and composite numbers, formal definition.
  • Read: Strayer, Sections 1.1 and 1.2.
  • HW 1 Preview: The first graded assignment, due Friday next week, will include Problems 6, 8, 14, 23, 30, 36, 41 from Chapter 1 of Strayer. An official homework assignment sheet will be given out in Monday's class.
• Wednesday, 1/19:
  • Fun Fact: What is special about the number 11213?. The answer was revealed in class. To see it again, click on the above link (courtesy of the amazing Prime Pages site).
  • Lecture: Course Overview. Divisibility.
  • Read: Strayer, Section 1.1.