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!
Course Policies, Exams, Grades
 Course Information Sheet.
The firstday handout. Everything you need to know about this class:
Syllabus, grading policies, office hours, etc.

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 NetID 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:
 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:
 Monday, 5/2:
 Lecture.
The general idea behind encryption schemes. "Public" (open) versus
"private" (secret) keys. Oneway 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.
 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. Onetoone 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:
 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.
 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:
 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:
 Friday, 3/4:
 Lecture:
More about the divisor function and the sumofdivisors function.
Perfect numbers: History, conjectures, and connection with Mersenne
primes.
 Read: Strayer, Section 3.5.
 Wednesday, 3/2:
 Lecture:
Euler phi function wrapup. The role of the FTA and CRT in the analysis
of phi values. Gauss' Theorem. The divisor and sumofdivisors 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.
 Read: Strayer, Section 2.6.
 Friday, 2/18:
 Wednesday, 2/16:
 Lecture:
Fermat and Mersenne numbers/primes. Compositeness of numbers
of the form 2^n1 (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^n1 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 (noninteger) 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:
 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:
Last modified: Fri 13 May 2011 01:26:04 PM CDT
A.J. Hildebrand