Math 360, Fall 2021, Assignment 8

Mathematical proofs, like diamonds, are hard as well as clear, and will be touched with nothing but strict reasoning.

- John Locke, Second Reply to the Bishop of Worcester

Carefully define the following terms, then give one example and one non-example of each:

1. $\mathrm{gcd}(a,b)$.
2. $\mathrm{lcm}(a,b)$.
3. $|$ (the divisibility relation on $\mathbb{Z}$).

Carefully state the following theorems (you need not prove them):

1. Classification of subgroups of cyclic groups ("Every subgroup of a cyclic group is...").
2. Containment criterion for subgroups of $\mathbb{Z}$.
3. Equality criterion for subgroups of $\mathbb{Z}$.
4. Classification of subgroups of $\mathbb{Z}$ ("Every subgroup of $\mathbb{Z}$ has a unique...").
5. Theorem concerning the properties of $\mathrm{gcd}(a,b)$.
6. Theorem concerning the properties of $\mathrm{lcm}(a,b)$.

Solve the following problems:

1. Section 6, problems 5, and 7.
2. Compute $\mathrm{gcd}(6,9)$. Then compute $\mathrm{gcd}(-6,9)$. (Hint: think about the subgroups $\left\langle 6,9\right\rangle$ and $\left\langle -6,9\right\rangle$.)
3. For any $a,b\in\mathbb{Z}$, prove that $\left\langle a,b\right\rangle=\left\langle -a,b\right\rangle$. (Hint: prove mutual containment. Bear in mind that $\left\langle a,b\right\rangle$ is the smallest subgroup containing $a$ and $b$, so it is contained in any other subgroup that contains $a$ and $b$.)
4. Prove that for any $a,b\in\mathbb{Z}$, we have $\mathrm{gcd}(-a,b)=\mathrm{gcd}(a,b)$.
5. Prove that for any $a,b\in\mathbb{Z}$, the set $S_{a,b}=\{xa+yb\,|\,x,y\in\mathbb{Z}\}$ is a subgroup of $\mathbb{Z}$.
6. Prove that the subgroup $S_{a,b}$ above is in fact equal to $\left\langle a,b\right\rangle$. (Hint: prove mutual containment.)
7. Prove that for any integers $a,b\in\mathbb{Z}$, there exist integers $x,y$ with $xa+yb=\mathrm{gcd}(a,b)$.
8. (Optional) Read the Wikipedia article on the Extended Euclidean Algorithm, which is a very efficient computer algorithm that computes $\mathrm{gcd}(a,b)$ as well as the integers $x,y$ referenced above. This algorithm, which is lightning-fast even when the inputs $a,b$ are astronomically large, is foundational to many cryptographic and cryptanalytic techniques.
9. (Optional) Implement the Extended Euclidean Algorithm in the programming language of your choice.

--------------------End of assignment--------------------