Print this problem set out (there are X problems!) and answer the problems on the given sheet.
  1. Consider the following definition:
    Integer $g$ is a common divisor of integers $a$ and $b$ if and only $g|a$ and $g|b$.

    Here is the statement and proof of a nice theorem. Fill in each line of the proof with a (brief!) justification for that line.

    For any $a$, $b$, $x$, $y$, if $g$ is a common divisor of $a$ and $b$, $g|(x*a + y*b)$.
    Let $g$ be a common divisor of $a$ and $b$.

    Then $g|a$ and $g|b$. _______________________________________________________

    So $a = g*x_1$ and $b = g*x_2$, for some $x_1$ and $x_2$. ___________________________

    So $x*a + y*b = x*g*x_1 + y*g*x_2$. ________________________________

    So $x*a + y*b = g*x*x_1 + g*y*x_2$. ________________________________

    So $x*a + y*b = g*(x*x_1 + y*x_2)$. _________________________________

    So $g|(x*a + y*b)$. ___________________________________________________



  2. Prove that for any $a$ and $b$, with $0 \leq a$ and $0 \lt b$, the quotient of $\text{div}(a,b)$ is less than or equal to $a$.
    Note: I would like a prose proof with level of detail similar to the proof from the previous problem (with your justificiations filled in).
    Hint: after writing out what you know about the quotient and remainder from $\text{div}(a,b)$, you will want to subtract the remainder from both sides! Then look at the "Divisors are smaller" theorem from Class 25.

  3. What are the quotient and remainder for 87 divided by 19, i.e. $\text{div}(87,19)$?
  4. Algorithm div only applies to non-negative $a$ and positive $b$. However, defines what the quotient and remainder need to be for any $a$ and any non-zero $b$. What are the quotient and remainder for -87 divided by 19, i.e. $\text{div}(-87,19)$?
    Note: Read the Quotient and reminder with negative numbers section of the Class 26 notes to see how to do this!