Study Guide for FinalExam - MAT 330 Elementary Number Theory

  1. The ring of integers
  2. Prime numbers, gcd, lcm, Euclid’s algorithm, factorization,
  3. Fundamental Th. of Arithmetic
  4. Sequence of prime numbers, Erathostene’s sieve, sketch of Euclid’s proof that there are infinitely many prime numbers.
  5. Basic terminology from abstract algebra:
  6. Group, subgroup, group homomorphism (“Z-lines”),
  7. Generators and cyclic groups (Z,+) and (Zn,+);
  8. Ring, zero divisors, units;
  9. Fields; main examples Q and Fp=Z/pZ (also denoted Zp).
  10. Ring of integers modulo n:
  11. Congruences modulo n, complete set of residues, arithmetic operations and properties;
  12. Wilson’s theorem and converse (p-1)!=-1 mod p
  13. Chinese Reminder Theorem and associated isomorphism (homomorphism of rings)
  14. Solving linear equations modulo n
  15. Euler’s phi-function, relatively prime elements
  16. Multiplicative orders of elements, Fermat’s Little Theorem and Euler’s Theorem
  17. Primality tests, Fermat pseudo-primes
  18. Multiplicative and completely multiplicative functions; examples: phi-function & powers
  19. How to solve ax=1 mod n; extended Euclidian Algorithm and representation ax+by=g
  20. Structure of the group of units U(Zp)=(Zp*,.): it is a cyclic Abelian group; generators: primitive roots
  21. Solving polynomial equations over Zn (direct methods: guess & quadratic formula)
  22. Quadratic reciprocity
  23. Existence of square-roots: quadratic residues vs. quadratic non-residues
  24. Legendre symbol (def. and properties: group homomorphism)
  25. Euler’s criterion
  26. Quadratic reciprocity for odd primes: L(p/q)=(-1)e(p)e(q) L(q/p), e(p)=(p-1)/2, where e(p)=(p-1)/2; using it to reduce the numbers when determining Legendre symbol.
  27. Solving quadratic equations, and using quadratic reciprocity to determine if the discriminant has a square root or not;
  28. Prime numbers: construct new primes from old; deconstruct primes via factorization of p-1.
  29. Sums of squares:
  30. Pythagorean triples, finding the parameters n & m for an irreducible triple
  31. Fermat 2 squares theorem; representing p=a2+b2 (know in principle how to handle the general case)
  32. Lagrange 4 square theorem; representing p as a sum of 4 squares;
  33. Modular group: definition, trace, conjugation, fact: any A=TXT-1 for some T in M
  34. Continued fractions (CF):
  35. Definition, examples; representing rationals as CFs;
  36. Solving Pell’s equation using continued fractions.
  37. Arithmetic functions: Mangoldt fn., Mobius fn., Euler phi-function, Riemann zeta fn.; properties: multiplicative, complete multiplicative; Dirichlet series: def. and examples; Mobius inversion formula.
  38. Miscellaneous: Dirichlet Theorem, Prime Number Theorem (explaining what it means abut primes), primality testing (what is it? Examples), sieving methods (examples), cryptography (how does encryption work, in general).