MTH 350 Homework 6

--- tags: mth350, homework --- # MTH 350 Homework 6 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.** ::: Suppose $a,m \in \mathbb{N}$ and $a,m > 1$. Prove that if $\gcd(a,m) > 1$, then $\overline{a}$ is a zero divisor in $\mathbb{Z}_m$. **Notes and hints:** - **Do not start this proof until you have practiced and are clear on the concept of zero divisors.**. Suggestion: For $m = 2, 3, \dots, 20$, find all the zero divisors of $\mathbb{Z}_m$, make sure you understand why they are zero divisors, and check this with your group (or a computer). Example: $\overline{6}$ is a zero divisor in $\mathbb{Z}_9$ because $\overline{6} \cdot \overline{3} = \overline{0}$. - This is based on work we started in class on February 22. Feel free to use any part of that discussion; but if a proof was only partial, make sure to give a complete proof in your submission. - Without loss of generality you may assume $a < m$ since this proof has to do with the congruence class of $a$ in $\mathbb{Z}_m$, which we always represent with an integer less than $m$. - Because we are assuming $1 < a < m$ it means that you can assume $\overline{a} \neq \overline{0}$. That's important for proving $\overline{a}$ is a zero divisor! - Remember that $\overline{a}$ is a zero divisor if $\overline{a} \neq \overline{0}$ (which we just said we can assume) and there exists a class $\overline{b}$ *which is also not equal to $\overline{0}$* such that $\overline{a} \cdot \overline{b} = \overline{0}$. That part about $\overline{b}$ not equalling $\overline{0}$ is essential, so make sure it's part of your proof. ## 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). :::   1. Prove the converse of Problem 1: If $\overline{a}$ is a zero divisor in $\mathbb{Z}_m$, then $\gcd(a,m) > 1$. (Use all the same assumptions that were given in Problem 1.) 2. Prove that if $p$ is prime, then for all $\overline{x} \in \mathbb{Z}_p$ not equal to $\overline{0}$, the equation $\overline{x} \cdot \overline{y} = \overline{1}$ has a solution. **Notes and hints:** - For option 1, you might test-drive different techniques for proving this "if-then" statement: Direct proof, contradiction, and proving the contrapositive. **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$.