Math 453, Section X: Exam 1 Syllabus Study Guide

General Information

• Date/time/location: The exam will be given during the regular class time, Wednesday, 2/23/2011, 12:00 pm - 12:50 pm, in the regular classroom, 343 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

The problems will be of the following types:

• Computional problems: These are concrete problems with numerical answers that test your knowledge of basic techniques and algorithms, such as congruence arithmetic and the Euclidean 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 by name.
• 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."
• Exam versus homework problems: In terms of difficulty, most of the exam problems will be comparable to that of an average homework problem, and most of the homework problems would make perfectly good exam problems. However, exam and homework problems are not completely interchangeable. Some problems that occurred in the hw assignments would be inappropriate in an exam, for example, because the computations are too involved (e.g., 36 in Chapter 2, the pirate problem from HW 4), or because they require elaborate or tricky proofs (e.g., 76 in Chapter 1, or 78 in Chapter 2). Conversely, the exam may include problems (such as questions about a particular definition or theorem) that would be inappropriate for a homework assignment since you could look up the answers in the class notes or in the text.

Past Exams

Exam 1 Syllabus

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

Advice on Preparing for the Exam

• Start studying early. Don't wait till the night before the exam.
• Find someone, or a group, to study with. Most students do best when studying together.
• Prepare a review/cheat sheet (but don't bring it to the exam!). Make up a sheet containing all the results, definitions, terminology, etc. that you need to know. The above syllabus can serve as a rough guide for things you should have on the sheet. Simply writing down this material helps committing it to memory, but to get the most out of this exercise, make up your first draft of the sheet without referring to class notes or the book, reconstructing the definitions from memory as best you can. Then use the class notes and handouts and the book to fill in any gaps, compare your definitions to the "official" ones, and make any corrections necessary.
• Redo the problems from the homework assignments, and examples from class and in the text. Many of the exam problems will be problems of the kind that have come up in the homework or in class. To do well on the exam you must get comfortable with such problems, be able to recognize them when they come up, know how to approach them and, in case of proof problems, know how to properly write up a proof. The best way to prepare for this is to redo the problems without referring to the solutions. The latter is a crucial point. Many students make the mistake to read over the solutions, think that they understand it, and then leave it at that. This gives a false sense of confidence, and many end up getting lost if they have to work a problem completely on their own in an exam situation. Thus, do the problems on your own first, and use the solutions only to compare and check your work.
• Try to understand the definitions and theorems rather than just mechanically memorize them. Try to understand how a definition "works", and why the way it is stated is the "right" way. Ask yourself why the the quantifiers appear in the given order and why they are of the "right" type ("for all" versus "exists"). If you understand the "inner workings" of a definition, it is a lot easier to memorize it and keep it straight, and it is easier to work with the definition, apply it correctly in proofs, find its negations, etc.
• Take advantage of the Open House. Open House hours are Wednesdays and Thursdays at 5 pm, and Sunday afternoons beginning at around 3 pm. In addition, I'll hold a special Open House on Monday before the exam, 5 pm, at the usual location (159 Altgeld). This is your chance to ask questions about the exam material, the exam content, what you do and do not need to know, etc. Take advantage of this opportunity. For last minute questions, send me email.