number theory - exams
note: more information
will be added as the exam dates near.
midterm exam: wed oct 30 (in class)
content: this exam will cover most of the first 3 chapters of the notes - more precisely,
-
sections 1.1-1.3, 1.5, 2.1-2.3, theorem 2.5.1 from sec 2.5, and sections 3.1-3.3.
while not necessarily a comprehensive list of topics covered on the exam, here
are the main things i am thinking about asking you to do on the exam. in
terms of types of problems, i would expect the following:
- answer true/false questions
- precisely state definitions/theorems with names (fundamental theorem of
arithmetic, Lagrange's theorem, Fermat's little theorem, Euler's theorem, etc)
- some computational exercises (by hand, no calculators allowed)
- write one or two simple non-computational proofs
(possibly of a result that was already
proved in class, an exercise, or something new)
in terms of content, be prepared to:
- determine if something is a group/ring/field
- compute the gcd of two integers (detailing steps of the Euclidean algorithm)
- use the extended Euclidean algorithm to find a solution (or prove
none exist) to a linear Diophantine equation: ax + by = c (possibly
over an imaginary quadratic ring)
- factor elements of irreducible quadratic rings into irreducibles
(which includes determining if an element in a quadratic ring is irreducible)
- check that an element of a quadratic ring has two distinct factorizations
or show why two factorizations are equivalent
- be able to use/prove basic divisibility tests
- do calculations mod n, such as determining of squares/non-squares or inverses of numbers
- use modular arithmetic to show certain equations have no solutions,
or possibly no solutions of a certain form
to prepare:
here is a selection of
to help you prepare for the exam. i encourage you to review first (using note, homeworks, etc), and then try the practice problems on your own like a mock test, before using notes/asking for help on them. bring whatever questions you have to class mon oct 28, which will be a review day. relatedly, i will move my office hours that week from their usual time:
office hours for week of oct 28: mon and wed 10-11am
final exam: mon dec 9, 1:30-3:30pm, phsc 1105
the final exam will be cumulative. the following information will be updated as we get closer to the end of the semester.
in terms of content, here are the main things you should be comforable with
(this is not necessarily a comprehensive list of topics to study):
- all topics listed above for the midterms
- fermat's two square theorem, including various aspects of the proof
(e.g., lagrange's lemma, the connection with unique factorization in Z[i], ...)
- understand the statement of the chinese remainder theorem and how to
use it to determine the euler phi function, and what is say about lifting
congruences mod m and mod n to congruences mod mn
- know the statement of and how to use quadratic reciprocity (including the
first but not the second supplementary law) to compute legendre symbols
and apply to diophantine equations such as x^2 + dy^2 = n
(you do not need to know the proof of quadratic reciprocity)
- know the statements of the three and four square theorems, but not
the proof or anything about quaternions
- know the structure theorem for units of real quadratic rings and the
relation to Pell's equation (e.g., knowing how to compose solutions to Pell's
equation)
- know how solutions of Pell's equation give good approximations to sqrt(d),
including the "1/2y" error bound
- be able to compute fundamental units or +units for Z[sqrt(d)], using
continued fractions or otherwise
- compute continued fractions of rational and quadratic numbers
- be able to put together the above 4 bullet points to get rational
approxiations to sqrt(d) within a specified bound, as in the final exercises
of section 5.4 (section 5.5 will not be covered on the exam)
- carry out an example of RSA and/or prove why RSA works
- other topics to be added based on what we cover in the course
course home