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--------------------

Definitions:

1. Suppose $a, b \in \mathbb Z$. the non-negative generator of $\left\langle a, b \right\rangle$ is denoted $gcd(alb)$.
2. $\left\langle a \right\rangle \cap \left\langle b \right\rangle$ is a subgroup of $\mathbb Z$, so it has a unique non-negative generator. This is denoted $lcm(a,b)$.
3. Divisibility in $\mathbb Z$: $a|b$ ("a divides b" or "b is a multiple of a") means that $\exists c \in \mathbb Z$ such that $b = ac$.

Theorems:

2. Containment criterion for subgroups of $\mathbb Z$): In $(\mathbb Z, +), \left\langle a \right\rangle \subseteq \left\langle b \right\rangle \iff b|a$.
3. Equality criterion: $(\left\langle a \right\rangle = \left\langle b \right\rangle \iff b|a \wedge a|b)$. In $\mathbb Z, (a|b \text{ and } b|a) \iff b=\pm a$.
4. Any subgroup of $\mathbb Z$ has a unique non-negative generator.
5. (1) $gcd(a,b)$ is in fact a common divisor of $a \text{ and } b$: $gcd(a,b) |a \text{ and } gcd(a,b) | b$. (2) If $d$ is any other common divisor of $a, b$, then $d|gcd(a,b)$.