CMSC 27100 — Problem Set 2

Instructions

This problem set is due on Friday October 18, 2019 at 23:59. Solutions to Problems should be submitted on Gradescope and will be graded. Solutions to Exercises will not be graded and you should not submit them, although we will be happy to discuss them with you.

Problems

  1. Show that $A \subseteq B$ if and only if $A \cap \overline B = \emptyset$.
  2. Prove that if $a \mid b$ then $\operatorname{Div}(a) \subseteq \operatorname{Div}(b)$.
  3. Prove that if $a \mid b$ and $b \mid a$ then $a = ±b$.
  4. Use Euclid's algorithm to determine the gcd for the following pairs of integers:
    1. $14112, 3024$
    2. $2006, 935$
  5. Let $a,b,q,r$ be integers such that $a = bq + r$ satisfies the Division theorem. Show that $r = a \pmod b$.

Exercises

  1. Rosen 2.1 Exercises 38
  2. Rosen 2.2 Exercises 18, 19
    1. Show that $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$
    2. Show that $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
  4. Prove that a function $f:A \to B$ is one-to-one if and only if $\forall x, y \in A, x \neq y \rightarrow f(x) \neq f(y)$.
  5. Suppose that $f:A \to B$ is a correspondence. Show that $f$ has a unique inverse, denoted $f^{-1}$, and that $\forall x \in B, f(f^{-1}(x)) = x$. (For the definition of inverse, see Definition 3.21)
  6. Rosen 4.1 Exercises 6, 7
  7. Rosen 4.1 Exercises 34-36
  8. Rosen 4.3 Exercises 32, 33
  9. Rosen 4.3 Exercises 41-44. These involve the Extended Euclidean Algorithm that was mentioned in class.