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(a, b)$.
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)$.
6. (1) $lcm(a,b)$ is a common multiple of $a, b: a|lcm(a,b) \text{ and } b|lcm(a,b)$. (2)If $m$ is any other common multiple, then $lcm(a,b)|m$.

Book Problems:

5. $8$

7. $60$

Problems:

2. $gcd(6,9) = 3$, $gcd(6,-9) = 3$

3. $-a|a, b|b$, then $a \in \left\langle -a \right\rangle , b \in \left\langle b \right\rangle \rightarrow a \in \left\langle -a, b \right\rangle \wedge b \in \left\langle -a, b \right\rangle$. $\left\langle a, b \right\rangle$ is the smallest subgroup that contains $a, b$, $\left\langle -a, b \right\rangle$ also contains $a, b$, which means that $\left\langle a, b \right\rangle \subseteq \left\langle -a, b \right\rangle$. With similar proof we get $\left\langle -a, b \right\rangle \subseteq \left\langle a, b \right\rangle$. Therefore, $\left\langle a, b \right\rangle = \left\langle -a, b \right\rangle$

4. $\left\langle a, b \right\rangle = \left\langle -a, b \right\rangle$, $\left\langle a, b \right\rangle$ and $\left\langle -a, b \right\rangle$ have same generator. Generator of $\left\langle a, b \right\rangle = gcd(a, b)$, generator of $\left\langle -a, b \right\rangle = gcd(-a, b)$. Therefore, $gcd(a,b)=gcd(-a,b)$.

5. (a) $0a+0b = 0, \text{ identity } \in S_{alb}$; (2) $\forall x_1, y_1, x_2, y_2 \in \mathbb Z, if x_{1}a + y_{1}b \in S_{alb} \wedge x_{2}a + y_{2}b \in S_{alb}$, $(x_{1}a + y_{1}b + x_{2}a + y_{2}b) = (x_{1} + x_{2})a + (y_{1} + y_{2})b,(x_{1} + x-{2}) \in \mathbb Z, (y_{1} + y_{2}) \in \mathbb Z \rightarrow (x_{1}a + y_{1}b + x_{2}a + y_{2}b) \in S_{a, b} $. (3) Inverse $= -(xa + yb) = (-x)a + (-y)b, (-x), (-y) \in \mathbb Z$, inverse $\in S_{a, b}$. $S_{a, b}$ is a subgroup of $\mathbb Z$.

6. By taking $x=1, b=0$ we see that $a\in S_{a,b}$. Similarly, we also have $b\in S_{a,b}$. Since $\left\langle a,b\right\rangle$ is the smallest subgroup containing both $a$ and $b$, this gives $\left\langle a,b\right\rangle\subseteq S_{a,b}$. On the other hand, any element of $S_{a,b}$ must also be an element of $\left\langle a,b\right\rangle$ simply because $\left\langle a,b\right\rangle$ contains both $a$ and $b$ and is closed under addition and negation.

7. Since $\left\langle a,b\right\rangle=\left\langle\mathrm{gcd}(a,b)\right\rangle$ we certainly have $\mathrm{gcd}(a,b)\in\left\langle a,b\right\rangle$ and thus $\mathrm{gcd}(a,b)\in S_{a,b}$.

Euclidean Code (Euclidean.java):

import stdlib.StdOut;
public class Euclidean {
   // Entry point. 
   public static void main(String[] args) {
       int a = Integer.parseInt(args[0]);
       int b = Integer.parseInt(args[1]);
       StdOut.println(gcd(a, b));
   }
   // Returns the gcd
   private static String gcd(int k1, int k2) {
       // Set integer a to be the bigger number
       int a = k1;
       // Set integer b to be the smaller number
       int b = k2;
       if (k1 < k2) {
           a = k2;
           b = k1;
       }
       else if (k1 > k2) {
           a = k1;
           b = k2;
       }
       else if (k1 == k2) {
           a = k1;
           b = k2;
       }
       // quotient q
       int q = 0;
       // reminder r1 (final reminder)
       int r1 = a;
       // reminder r2 (temp reminder)
       int r2 = b;
       // coefficient for a, s1
       int s1 = 1;
       int s2 = 0;
       // coefficient for b, t1
       int t1 = 0;
       int t2 = 1;
       while (r2 > 0) {
           q = r1/r2;
           int temp_r = r2;
           r2 = r1 - q * temp_r;
           r1 = temp_r;
           int temp_s = s2;
           s2 = s1 - q * temp_s;
           s1 = temp_s;
           int temp_t = t2;
           t2 = t1 - q * temp_t;
           t1 = temp_t;
       }
       String s =  r1 + " = " + "(" + s1 + ")" + "*" + "(" + a + ")" + " + " + "(" + t1 + ")" + "*" + "(" + b + ")";
       return s;
   }
}

Result:

jingwens-MBP:workspace jingwenfeng$ java Euclidean 240 46

2 = (-9)*(240) + (47)*(46)