---
tags: mth350, homework
---

# MTH 350 Homework 5

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.**
:::

Prove **Theorem 1.4.9**: Let $a,b,c$ and $m$ be integers with $m > 1$ and $\gcd(c,m) = 1$. Then there is some $x \in \mathbb{Z}$ such that $\overline{c} \cdot \overline{x} = \overline{1}$. Then use this fact to prove that if $\gcd(c,m) = 1$ and $\overline{a} \cdot \overline{c} = \overline{b} \cdot \overline{c}$, then $\overline{a} = \overline{b}$.

**Notes and hints:**

- This was one of the Daily Prep problems from February 17, so we've discussed it in class. You are welcome to use anything from that discussion in your personal writeups.
- I've slightly rephrased this from the book, to clarify that this theorem has two parts, and the second part is assuming the same things as the first part, especially the fact that $\gcd(c,m) = 1$. Without that assumption, we showed in class that the "cancellation" in the second part doesn't always work.
- For the second part, there's no such thing as "division" of congruence classes, so you can't "divide off" $\overline{c}$; nor can you use integer division, because that's illegal for now. Given the equation $\overline{a} \cdot \overline{c} = \overline{b} \cdot \overline{c}$, is there something you *can* do to both sides that would get rid of $\overline{c}$? Might the first part of the theorem be helpful?
- You may assume here that addition and multiplication in $\mathbb{Z}_m$ satisfy all the arithmetic properties that plain integer arithmetic satisfies: closure of the operations, commutativity, associativity, distributivity, etc. [Here again is the list of those properties for integers](https://hackmd.io/ekF3OWspRbm-WWhSGcaqGQ?view#Basic-Axioms-and-Definitions). (The "Ordering Axioms" do *not* apply here since we haven't defined what "$<$" would mean for congruence classes.) We talked about the commutative property in class; below you'll have a chance to prove a few more of these.

## 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. Prove Theorem 1.4.10. (This definitely uses Theorem 1.4.9.)
2. Let $m > 1$. Show that addition and multiplication modulo $m$ satisfy the following properties similar to those in [the list of Arithmetic Axioms for integers](https://hackmd.io/ekF3OWspRbm-WWhSGcaqGQ?view#Basic-Axioms-and-Definitions):
(a) The **associative property**: For every $\overline{a}, \overline{b}, \overline{c} \in \mathbb{Z}_m$, $\overline{a} + (\overline{b} + \overline{c}) = (\overline{a} + \overline{b}) + \overline{c}$ and $\overline{a} (\overline{b} \overline{c}) = (\overline{a} \overline{b}) \overline{c}$.
(b) The **distributive property of multiplication over addition**: For every $\overline{a}, \overline{b}, \overline{c} \in \mathbb{Z}_m$, $\overline{a} (\overline{b} + \overline{c}) = \overline{a} \overline{b}+ \overline{a} \overline{c}$.
(c) The existence of **additive inverses**: For every $\overline{a} \in \mathbb{Z}_m$, there exists $\overline{b} \in \mathbb{Z}_m$ such that $\overline{a} + \overline{b} = \overline{0}$. (This one is trickier than it looks. Be sure to use *only* elements $\mathbb{Z}_m$, where the representative of the equivalence class is between $0$ and $m-1$ inclusive. For example we can't say the additive inverse for $\overline{3}$ in $\mathbb{Z}_{10}$ is $\overline{-3}$; the representative has to be between $0$ and $9$. So we'd need to say the additive inverse is $\overline{7}$. Given any $\overline{a} \in \mathbb{Z}_m$, how would you find its additive inverse?)
3. Let $n > 1$ and suppose $a,b \in \mathbb{Z}$. Prove that if $a \equiv b \pmod n$, then $\overline{a} = \overline{b}$ in $\mathbb{Z}_n$.
4. Let $n > 1$ and suppose $a,b \in \mathbb{Z}$. Prove that if $\overline{a} = \overline{b}$ in $\mathbb{Z}_n$, then $a \equiv b \pmod n$. (This is the converse of option 3. Put together, they make a very useful "if and only if" theorem.)

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

## Submission instructions

You are turning in two items:

1. Both parts of Problem 1.
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 5" assignment area, and remember to hit **Submit**.

**Handy $\LaTeX$ commands:**

- To put a bar over the top of something, enclose it in `\overline{}` in math mode. For example `$\overline{x}$` creates $\overline{x}$; `$\overline{x^2 + y^2}$` creates $\overline{x^2 + y^2}$.
- To get the "integers mod $m$" just use the fancy $\mathbb{Z}$ for integers and subscript it with $m$. For example `$\mathbb{Z}_6$` gives $\mathbb{Z}_6$, and `$\mathbb{Z}_{100}$` gives $\mathbb{Z}_{100}$. Or if you are using the macro `$\Z$` defined in the template, it's just `$\Z_6$` or `$\Z_{100}$`
- To typeset a basic integer congruence like $10 \equiv 2 \pmod 8$, use `\equiv` to get the triple-equals sign, and `\pmod` to get the "mod". For example, `$10 \equiv 2 \pmod 8$` gives $10 \equiv 2 \pmod 8$.