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

## Final Exam and Course Grades

Final Exam scores and course grades are now online and can be accessed as usual. The average score on the Final was 92/120, the median 101/120, the highest score (including Extra Credit points) 121/120. Final Exam Solutions are available under this link.

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.

Have a good break and enjoy your summer!

• Midterm Exam 1: Wednesday, February 23.
• Midterm Exam 2: Wednesday, April 13.
• Final Exam: Wednesday, May 11, 7 pm - 10 pm.
• 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

These class notes summarize the key definitions and theorems that you need to know for the homework and in exams. I will pass these out in small installments in class as we move along with the material and post complete versions here at the end of each chapter.

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.

## Class Diary

• Wednesday, 5/4:
• 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.
• 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:
• 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:
• 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.
• 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:
• 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.
• 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.
• 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.
• 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.
• 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:
• Friday, 3/4:
• Lecture: More about the divisor function and the sum-of-divisors function. Perfect numbers: History, conjectures, and connection with Mersenne primes.
• 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:
• 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.
• Friday, 2/18:
• 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:
• 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:
• 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.
• 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.