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

Definitions

You should be able to give careful, complete, formal definitions of — and examples and know theorems involvng — the following terms:
  1. Euler's totient function $\phi(n)$
  2. the prime number counting function $\pi(x)$
  3. a Mersenne Prime
  4. the divisor sum function $\sigma(n)$
  5. a perfect number

Theorems, Conjectures, and Algorithms

Please know careful, complete statements of the following:
  1. Fermat's Little Theorem
  2. Euler's Formula (the one that is Theorem 10.1 in the book)
  3. The Chinese Remainder Theorem
  4. Formulæ for Euler's totient function $\phi(n)$ (being Theorem 11.1 in the book), which give
    1. a formula for $\phi(p)$, where $p$ is prime
    2. a relationship between $\phi(m\,n)$ and $\phi(m)\,\phi(n)$, which applies when $m$ and $n$ are                         
  5. Dirichlet's Theorem on Primes in Arithmetic Progressions
  6. The Prime Number Theorem
  7. The Twin Prime Conjecture
  8. Goldbach's Conjecture
  9. a theorem about when numbers of "Mersenne-like form" ($a^n-1$) can be prime (Theorem 14.1 in the book)
  10. Euclid's Perfect Number Formula
  11. Euler's Perfect Number Theorem
  12. a theorem relating $\sigma(m\,n)$ and $\sigma(m)\,\sigma(n)$, which applies when $m$ and $n$ are                         
  13. the Successive Squaring Algorithm to Compute $a^k\pmod{n}$
  14. an Algorithm to compute $k^{th}$ roots $\pmod{n}$

Things to know how to do

  1. proofs of theorems 1, 2, 3, 4, 9, 10, and 12, above (either from the book or as we did in class – e.g., our proof of FLT was much easier than the books...)
  2. use algorithms 13 and 14, above, for specific numeric computations
  3. compute $\phi(n)$ or $\sigma(n)$ using 4 and 12 (and other basic computations), for specific numerical $n$
  4. find a solution (whose existence is guaranteed by the CRT) to a system in the form of the Chinese Remainder Theorem, given with specific numbers
  5. proofs like (and including exactly) the homework assignment proofs we've had since Midterm I

Format of the test

Be able to state — in full formality and five-part harmony — all the definitions. You will be asked to do so for something like four out of the five listed above. You must also be able to give context, ideas, examples, etc., for each term you define!

You will also be asked to give full and formal statements of the theorems/algorithms/conjectures mentioned above, as well as an example (or counterexample when some hypothesis is dropped) to which the theorem applies; there will be a choice of four out of eight to state, roughly. You will also likely have to use those theorems in proving other statements.

There will then be a choice of about three out of six proof-y things to do. Of the six, most will be proofs of the above theorems (so, key steps from the proofs you must know how to do in I of Things to know how to do, above). One will be a very numerical computation, for those who like such things (I will give out four-function calculators if you want them, and various numerical facts will be given on the test -- including, but not limited to, many useful numerical compuations related to the give problem; you will not be allowed to use your own calculators). And one or two will be brand new proofs for you to do fresh, if you choose those problems.