---
tags: mth350, homework
---

# MTH 350 Homework 2

Instructions for this Homework set are on Blackboard where this is posted. The due date is on the class calendar, which is linked on Blackboard.

## Problem 1

:::warning
This problem is an **independent** problem. As described in [the Syllabus](https://docs.google.com/document/d/1Rest_DodWnDy7Y8EVhp2lEOVnWcTEjLAGfWV2khuQQY/edit?usp=sharing) (top of page 14) this means that **on this problem, the only help you can get is from the professor.**
:::

**Complete the proof of Theorem 1.2.5c** which we started in class. Here is a formal statement:

>Suppose $a,b \in \mathbb{N}$ and that $r$ is the smallest element of the set $S = \{a - bs \, : \, s \in \mathbb{N}_0, a - bs \geq 0\}$. Then $0 \leq r < b$.

Some notes on this problem:

- We proved in class that $S$ actually does have a smallest element. This doesn't have to be proven again; it's a fact now.
- The strategy discussed in class is to prove the inequality in two parts: First prove $r \geq 0$ then prove $r < b$, with the second inequality being proven by contradiction. You don't *have* to use that strategy and there could possibly be simpler approaches; but it's a potential strategy you can use.
- Some parts of this proof were sketched out in class, and it's OK to use those. What you're doing here is putting our discussion into your own words, and then coming up with the missing parts that we didn't discuss.
- By "complete the proof", we mean *give a complete and correct proof*. Your writeup should not merely pick up where we left off in class, but instead start at the beginning and complete it all the way to the end.

## Problem 2

:::success
This problem is a **collaborative** problem. This means that **you can work on it in a small group, as long as you stay within the bounds of academic honesty** laid out in [the Syllabus](https://docs.google.com/document/d/1Rest_DodWnDy7Y8EVhp2lEOVnWcTEjLAGfWV2khuQQY/edit?usp=sharing) (starting on page 13).
:::

**Choose exactly one of the following statements** and write a complete, correct, and clear proof.

You can (and should) test-drive each of these problems in your notes to see which one feels best for you, but please only turn in work on one of these (in addition to Problem 1).

1. Let $n \in \mathbb{N}$. Suppose that $b_1, b_2, \dots, b_n$ are natural numbers and $a | b_i$ for each $1 \leq i \leq n$. Prove that $a | (b_1 + b_2 + \cdots + b_n)$. (This is an extension of Theorem 1.2.2, where the sum involves only two numbers.)
2. Let $a,b \in \mathbb{Z}$, and $a$ and $b$ are not both zero. The Division Algorithm says there are integers $q$ and $r$ such that $a = bq + r$ and $0 \leq r < b$. Prove that $\gcd(a,b) = \gcd(b,r)$. (This result is a critical step in the proof of the Euclidean Algorithm.)
3. **Prove Theorem 1.2.8:** Let $a,b,c \in \mathbb{Z}$ such that $a = b+c$, with $a$ and $b$ not both zero. Then $\gcd(a,b) = \gcd(b,c)$.

**Additional options for Problem 2 may be added through Tuesday, depending on class activities. Watch your announcements!**

## Submission instructions

You are turning in two items:

1. The proof for Problem 1 (Theorem 1.2.5c)
2. Your choice of proof in Problem 2.

Remember to type up your work using $\LaTeX$, and create a single PDF document with each problem on a separate page. (Use the command `\pagebreak` to start a new page.)

Then upload your PDF to the "Homework 2" assignment area, and remember to hit **Submit**.