Math 453, Section X13

Final Exam Information

General Information

• Date/time/location: The final will be Wednesday, May 11, 2011, 7 pm - 10 pm, in the usual room, 343 Altgeld. This is the official final exam slot for classes meeting at 12 pm MWF.
  (See the Spring 2011 Final Exam schedule.)
  
• Exam rules: The same as for the midterms. No calculators, closed books/notes, no formula sheets, and no cheating.
• Final Exam Conflicts: The University is very strict about enforcing final exam time slots. In particular, a student can not take the final at a different time to accommodate travel plans. The main exception is the "no three consecutive finals" rule, and in this case the University has specific guidelines on how to prioritize conflicts. As a general rule, the class with the largest number of students is responsible for providing make-up/conflict dates for students in a "three consecutive finals" situation. If you are in this situation, and our class is the largest of the three involved, contact me by email (ajh@illinois.edu) no later than the last day of class, Wednesday, May 4, providing details about the three classes (course/section numbers, final exam times, and any conflict exams offered).
• Missed final, illness, and other emergencies: By University policy, a missed final exam automatically translates into a failing grade unless the student has been granted an "excused/incomplete" grade by the Dean, in which case the student is entitled to take a make-up final by the middle of the following semester. If you miss the final because of an illness or other emergency do the following as soon as possible (preferably before the time of the final):
  • Call the Emergency Dean (333-0050) and explain your situation. This is the most important step. The Emergency Dean can initiate further action or refer you to the appropriate Dean to get the excused/incomplete grade approval process started. (Only Deans have the authority to grant excused/incomplete grades - the instructor cannot assign such grades.)
  • If you are sick, make sure to see a doctor or nurse as you will likely need some documentation proving that you really have been sick.
  • Notify me by phone (244-7721) or email (ajh@uiuc.edu). (This is just a matter of courtesy so that I know what is going on. You still need to go through the Dean to get an excused grade and make-up final approved.)
• Open House/Office Hours. Here is a tentative Open House Hour schedule up until the Final Exam:
  • Wednesday, 5/4: 5 pm
  • Thursday, 5/5: 5 pm
  • Sunday, 5/8: 3:30 pm
  • Monday, 5/9: 6 pm
  Feel free to email me (ajh@illinois.edu) with any questions or to set up an appointment outside the above hours.
• Grading: The Final Exam is worth 1/3 of the course grade; the other components are homework (1/6) and midterms (1/2). Your course grade will be determined by the average of these three components, with the appropriate weights. The grade cutoffs will be similar to those announced after the second midterm (86/100 cutoff for the A range, 72/100 for the B range, etc.), but may be adjusted slightly to take into account the score distribution on the final and to avoid hardships and close calls. Once the final exam scores are in, you will be able to access all of your scores, and your course grade, in the usual way. See the Grading Information page for an explanational of the score display.

Final Exam Content

Below is a detailed syllabus for the final. It corresponds to the combined syllabi for the two midterms, plus a syllabus for the post Exam 2 material.

The links are to the course notes (summary of definitions and theorems). The numbering of the chapters is that of these notes. Chapters 1 - 5 correspond to the same chapters in Strayer; Chapters 6 and 7 correspond (roughly) to Chapters 7 and 8 in Strayer.

Chapter 1: Divisibility

• Divisibility: definition and properties
• Division algorithm
• Primes and composite numbers
• Sieve of Eratosthenes
• Mersenne numbers
• Fermat numbers
• Goldbach conjecture
• Twin prime conjecture
• Prime number theorem
• Dirichlet's Theorem on primes in arithmetic progressions
• Greatest common divisor (gcd): definition and properties
• Euclidean algorithm
• Least common multiple (lcm): definition and properties
• GCD and linear combinations of integers
• Fundamental Theorem of Arithmetic (FTA):
• Applications of FTA: Characterization of divisibility, gcd, and lcm, in terms of prime factorizations. Counting divisors.

Chapter 2: Congruences

• Congruences: Definition and basic properties
• Residue classes
• Complete systems of residues
• Linear congruences: Theorem and algorithm for solution
• Modular inverses
• Chinese Remainder Theorem. (You only need to know the theorem; not the algorithm associated with it.)
• Fermat's Little Theorem
• Wilson's Theorem
• Pseudoprimes and Carmichael numbers
• Euler's Theorem

Chapter 3: Arithmetic functions

• Notational conventions: Divisor sums and products, empty sum/product convention
• Arithmetic function: Definition
• Multiplicative and completely multiplicative arithmetic function: Definition and representation in terms of prime factorization
• Dirichlet product of arithmetic functions: Definition and properties (commutativity, associativity, identity element, Dirichlet inverse)
• Dirichlet product of multiplicative functions
• The three trivial arithmetic functions: delta function, unit function, and identity function.
• The Moebius function (mu(n)): Definition and properties, Moebius inversion formula
• The Euler phi function: Definition and properties, Gauss identity
• The number-of-divisors function: Definition and properties
• The sum-of-divisors function: Definition and properties
• Perfect numbers: Definition. Characterization of even perfect numbers in terms of Mersenne primes

Chapter 4: Quadratic residues

• Quadratic residues and nonresidues: Definition
• Number of quadratic residues and nonresidues modulo p
• Number of solutions to quadratic congruences modulo p
• Legendre symbol: Definition and properties (periodicity, complete multiplicativity)
• Legendre symbol: Special values (-1|p) and (2|p)
• Euler's criterion for the Legendre symbol (Note: You do not need to know Gauss' Lemma)
• The Quadratic Reciprocity Law

Chapter 5: Primitive roots

• The order of an integer: Definition and properties
• The order of a power of an integer.
• Number of elements of a given order modulo an odd prime p
• Primitive root: Definition, and connection to reduced systems of residues
• The Primitive Root Theorem (Characterization of moduli for which a primitive root exists)
• Number of primitive roots modulo m

Chapter 6: Continued fractions

• Definitions and notations
• Convergence of infinite continued fractions
• Computing convergents: Recursion formula and matrix representation.
• Best rational approximation property of convergents
• Continued fraction expansions of rationals, irrationals, and quadratic irrationals.

Chapter 7: Topics from computational number theory

• Computationally easy versus hard problems. Examples of each. Polynomial time algorithms.
• Primality Testing algorithms: Wilson, Fermat, Lucas, Pepin.
• The RSA encryption scheme.