Math 453, Section X1: Exam 1 Study Guide

General Information

• Date/time/location: The exam will be given during the regular class time, Wednesday, 2/27/2008, 12:00 pm - 12:50 pm, in the regular classroom, 145 Altgeld.
• Exam rules: Closed books and notes, and no calculators. The problems will be such that they do not require significant calculations if approached with the appropriate method.

Exam content

• Computional problems: These are concrete problems with numerical answers that test your knowledge of basic techniques and algorithms, such as congruence arithmetic, the Euclidean algorithm, or the Chinese Remainder Theorem algorithm. All of the problem will be of a type that have come up in class and/or the homework assignments (both turn-in and non-turn-in), usually multiple times. For these problems you are expected to use the appropriate algorithms, as discussed in class. The point of these problems is for you to show that you know these algorithms and that are able to apply them correctly. Answers arrived by guessing, trial and error, or brute force, won't earn credit.
• Definitions and theorems: Some questions are aimed at testing your knowledge of basic concepts and results, either directly, by asking to to state a definition or theorem, or indirectly, by asking a question that can be answered by applying an appropriate theorem (e.g., "does the congruence ... have a solution?"). In the latter case, you have to know and cite the appropriate theorem.
• Proof problems: The exam will include a few questions asking to prove or disprove a statement (though you may have to decide which!). The proofs you can expect in the exam will be of the routine kind, where the steps are pretty much dictated by the context, and no special tricks are required. A typical example of an "exam level" proof problem is the following: "Show that if a|b and b|c then a|c."

Summary of Concepts, Theorems, and Techniques

Chapter 1

• 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: 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