Math 453, Section X13

Final Exam Information

General Information

• Date/time/location: The final will be Thursday, May 8, 2008, 8 am - 11 am, in the usual room, 145 Altgeld. This is the official final exam slot for classes meeting at 12 pm - 1 pm.
• Exam rules: The same as for the midterms. No calculators, closed books/notes, no formula sheets, and no cheating.
• 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.)
• Office hours. The last class hour (Wednesday, April 30) will be a Q and A session, at the regular classroom. I plan to hold the usual Open House hours this week (April 28 - May 2), i.e., Wednesday, 4/30, and Thursday, 5/1, at 5 pm; if there is interest, I will schedule additional slots the week of the final.

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.

Chapter 1: Divisibility and Factorization

• 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
• Characterization of gcd in terms of linear combinations of integers
• Fundamental Theorem of Arithmetic
• Divisibility: characterization in terms of prime factorization
• Gcd and lcm: characterization in terms of prime factorization

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, and associated algorithm
• Fermat's Little Theorem
• Wilson's Theorem
• Pseudoprimes and Carmichael numbers
• Reduced systems of residues
• The Euler phi-function
• 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 Carmichael conjecture
• The number-of-divisors function: Definition and properties
• The sum-of-divisors function: Definition and properties
• Perfect numbers: Definition
• Perfect numbers: Characterization of even perfect numbers, connection with 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: Value at -1, and at 2.
• 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
• Continued fraction algorithm
• Continued fraction expansions of rationals, irrationals, and quadratic irrationals
• Convergents: definition and basic properties
• Algorithm for convergents
• Convergents and rational approximations