Prelim 1 Topics

This list of topics is not necessarily complete. Everything covered through number theory (Friday's lecture) will be in scope. Material covered on the homework will be given heavier emphasis.

You can find a collection of relevant questions from exams from previous semesters here (solutions)

• Definitions, proofs
  • Be able to write clear and succinct proofs
  • Be able to give examples and counterexamples given a definition
  • Be able to prove and disprove "there exists" and "for all" statements
  • Avoid backwards proofs and other logical errors
  • Determine whether proofs are valid or not, and why
• Sets and functions
  • Understand and use set and function notation
  • Determine whether a function is well-defined
  • Definitions: function, one-to-one/injective, onto/surjective, bijective
• Cardinality
  • Definitions of ∣X∣≤∣Y∣, ∣X∣≥∣Y∣, ∣X∣ = ∣Y∣
  • Know examples of countable and uncountable sets
  • Prove a set is countable
  • Prove a set is uncountable (by diagonalization)
• Induction
  • Strong and weak induction
  • Common errors in inductive proofs
  • Inductively defined functions
• Number bases
  • Definitions, arithmetic, conversion
• GCD
  • Euclid's algorithm, statement of correctness
  • Bezout coefficients, finding modular inverses
• Modular arithmetic
  • Equivalence classes
  • Functions defined using representatives
  • Units, inverses
  • Exponentiation, Euler's theorem
• RSA
  • Overview of RSA algorithm
  • High-level argument of correctness and security