Review for Final Exam - MAT 330 Elementary Number Theory

  1. Prime numbers: factorization, sequence of prime numbers, Erathostene’s sieve, sketch of Euclid’s proof that there are infinitely many prime numbers.
  2. Ring of integers modulo n:
  3. Congruences modulo n, complete set of residues, arithmetic operations and properties;
  4. Chinese Reminder Theorem and associated isomorphism (homomorphism of rings)
  5. Solving linear equations modulo n
  6. Euler’s phi-function, relatively prime elements
  7. Fermat’s Little Theorem and Euler’s Theorem
  8. Multiplicative and completely multiplicative functions; examples: phi-function & powers
  9. How to solve ax=1 mod n; extended Euclidian Algorithm and representation ax+by=g
  10. Primality Test: n>1 is prime iff for all a>0, a^(p-1)=1 mod n (behaves like one: satisfies the statement from Fermat’s Little Theorem)
  11. Structure of (Zp*,.): it is a cyclic Abelian group; generators: primitive roots
  12. Solving polynomial equations over Zn (direct methods: guess & quadratic formula)
  13. Public-key cryptography:
  14. Cryptography using a secret key (translating a phrase into a number, encoding/decoding using a secret key / trap-door function)
  15. Diffie-Hellman key exchange
  16. Discrete log problem
  17. RSA cryptosystem (general description)
  18. Quadratic reciprocity
  19. Existence of square-roots: quadratic residues vs. quadratic non-residues
  20. Legendre symbol (def. and properties: group homomorphism) and Euler’s criterion
  21. Quadratic reciprocity for odd primes: L(p/q)=(-1)^e(p)e(q) L(q/p), e(p)=(p-1)/2; using it to reduce the numbers when determining Legendre symbol.
  22. Solving quadratic equations; square-root formula for p=-1 mod 4: sqrt(a)=a^[(p+1)/4] (Note: it is the case of inert primes: not splitting in Z[i]).
  23. Continued Fractions
  24. Def., convergence and their value, as a limit if infinite continued fractions
  25. Representation of rational numbers as finite CF
  26. Fact: quadratic irrationals have periodic CFs
  27. Using convergents of quadratic irrationals to find the fundamental solution of Pell’s equation
  28. Sums of Two Squares
  29. Gaussian integers, complex conjugation, algebraic norm N(z)=z z*
  30. For n=p prime, sum of two squares <-> splitting the prime
  31. N can be written as a sum of squares if its odd power prime factors split as Gaussian integers (p=1 mod 4).
  32. Elliptic Curves:
  33. equation, type of graph over R, C, Zp; determining the points of E(GF(p)) for given a & b; the graphical construction for the sum of two points under the group law
  34. Elliptic Curve Cryptography: main difference compared with DH & RSA; ElGamal Cryptosystem (analog of DH with Encode(Msg)=Msg+Key (group law in some EC(Zp)); EC discrete log problem.
  35. Elliptic Curves over Q: facts about rank & torsion.
  36. Congruent number problem and its relation with Elliptic Curves (at level of explanation).