MPCS 50103 — Problem Set 2

Instructions

This problem set is due on Wednesday January 22, 2020 at 17:00. Solutions to Problems should be submitted on Gradescope and will be graded. Each problem is worth 10 marks in total. 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. Prove that if $a \mid b$ then $\operatorname{Div}(a) \subseteq \operatorname{Div}(b)$.
  2. Prove that for all integers $a$ and $b$ that $\gcd(a,b) = 1$ if and only if there exist integers $m$ and $n$ such that $am + bn = 1$.
  3. Prove or disprove that if $a \mid bc$, where $a,b,c$ are positive integers, then $a \mid b$ or $a \mid c$.
  4. Use Euclid's algorithm to determine the gcd for the following pairs of integers:
    1. $14112, 3024$
    2. $2006, 935$

Exercises

Set theory and functions

  1. Rosen 2.1 Exercises 5, 11
  2. Rosen 2.1 Exercises 25
  3. Rosen 2.1 Exercises 31
  4. Rosen 2.2 Exercises 19, 21, 23
  5. Rosen 2.3 Exercises 33
  6. 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$.

Number theory

  1. Rosen 4.1 Exercises 5, 7
  2. Rosen 4.1 Exercises 21, 23
  3. Rosen 4.1 Exercises 34-36
  4. Rosen 4.3 Exercises 32, 33