Math 453, Section X: Exam 2 Syllabus

General Information

• Date/time/location: The exam will be given during the regular class time, Wednesday, 4/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 relevant homework assignments are HW 5 - 8. (The due date for HW 8 is Monday before the exam, so I will distribute solutions that day.)

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

Summary of Concepts, Theorems, and Techniques

The following is a list of concepts, theorems, and techniques that you need to be prepared for in the exam. If you are a bit fuzzy about a particular item, review it from your class notes and from the appropriate sections in the text; also redo any relevant hw problems.

Section 2.6: 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

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.