CS-235. Problem Set 2


Number Theory

  1. Ex.35 from Supplemental notes
  2. Prove Theorem 1.1
    (it is really trivial - les than half a line per item in most cases)
  3. 1.6
  4. Prove that for any ideal I an integer a is in I iff (if and only if) aZ is a subset of I.
  5. For any integers a1,..., ak , show that the ideal a1Z+...+ akZ  generated by these integers is the "smallest" ideal containing a1,..., ak. That is for any ideal I, prove that a1,..., ak are in I iff the ideal a1Z+...+ akZ is a subset of I.


  1. Prove that equality modulo n is an equivalence relation on the set of integers.
  2. Which one is the smallest equivalence relation on integers? What are the classes of this relation?
  3. Among two binary numbers of length n, n>0, we define this relation ~ : a~b if and only if a and b have the same parity. Is this an equivalence relation? If yes, describe its classes.
  4.  Let S be the set of all students registered for CS235. If x is a student then we define course(x)=#of courses that x is taking.
    1. What is the domain and range of this function? Write its type in the "f: A--> B" format.
    2. What kind of a function is this?
    3. If we define relation on S to be a ^ b iff course(a) ≤ course(b), which properties does this relation have?