Final Review Sheet for
Colorado State University, Pueblo
Math 419 — Number Theory — Spring 2012

Definitions

1. Carmichael numbers
2. the order $e_p(a)$ of a number $a$ modulo $p$
3. a primitive root mod $p$
4. the index $I(a)$ of a number $a$ modulo $p$ with respect to a base $g$, also called the discrete logarithm $\log_g(a)$.
5. a quadratic [non]residue mod $p$ and the corresponding sets $QR_p$ and $NR_p$.
6. the Legendre symbol $\left(\dfrac{a}{p}\right)$
7. the Jacobi symbol $\left(\dfrac{a}{b}\right)$

Theorems, Conjectures, and Algorithms

1. Korselt's Criterion for Carmichael Numbers
2. Rabin-Miller Test for Composite Numbers
3. a theorem about the sum of the values of Euler's $\phi$ function over all the divisors of a number
4. The Order Divisibility Property
5. The Primitive Root Theorem
6. a theorem on rules for indices (known in precalculus as the laws of logarithms)
7. Euler's Criterion (for the Legendre symbol)
8. The Primes Congruent to 1 mod 4 Theorem
9. The Law of Quadratic Reciprocity, which really contains what the book calls
   1. The Quadratic Residue Multiplication Theorem
   2. Quadratic Reciprocity, Part I (for $\left(\dfrac{-1}{p}\right)$)
   3. Quadratic Reciprocity, Part II (for $\left(\dfrac{2}{p}\right)$), and
   4. Quadratic Reciprocity (the "flipping part")

Things to know how to do

1. prove theorems 4, 8, and 9abc
2. use the RSA cryptosystem to encrypt or decrypt a message
3. compute the Legendre or Jacobi symbol for given numbers

Format of the test

• The first part of the test is your contributions to the wiki. These will count for one quarter of the final exam points.
• Next, you will be asked to state — in full formality and five-part harmony (i.e., give context and examples) — something like half of the above definitions, and half of the above theorems. This is the second quarter of the final points
• You will then be given a printed copy of the wiki, in its state as of Friday at 8am, which you may consult for the last part of the test.
• There will then be four of the previously assigned HW problems, of which you must do two. This is the third quarter of the final exam points.
• There will then be four entirely new problems, of which you must do two. These will count as the last quarter of the final exam points.
• Topics: for the eight problems just mentioned, comprising the last half of final exam points, the general topics which have talked most about in class and which therefore are likely sources for these problems are:
  • general congruences, solving congruence equations
  • understanding and applying the GCD
  • The Chinese Remainder Theorem
  • Fermat's Little Theorem
  • quadratic residues
  • one of the many times we've done some proof infinitely many primes of some type
  • using the Euler $\phi$ function
  • primitive roots

It is clear from the above that it makes sense to contribute a lot to the wiki, both for those first 25% of points, and to have useful content to consult during the test. But please note that I will do a final edit of the wiki before printing it out, to remove offensive content, or too detailed descriptions of how to do old HW problems — instead, you should make sure that the wiki has clear statements of all the results you used (or we discussed in class) that might be helpful in doing the problems on the final.