Abstract Algebra

Goal: Verify that the algebraic structure $(\mathbb{Z}, *)$ satisfies all four group axioms.

Proof:

1. Closure: For any integers $a, b \in \mathbb{Z}$, the expression $a+b-1$ is also an integer because $\mathbb{Z}$ is closed under addition and subtraction. Thus, $a*b \in \mathbb{Z}$.
2. Associativity: We must show $(a*b)*c = a*(b*c)$ for all $a, b, c \in \mathbb{Z}$. $$\text{LHS: } (a*b)*c = (a+b-1)*c = (a+b-1)+c-1 = a+b+c-2$$ $$\text{RHS: } a*(b*c) = a*(b+c-1) = a+(b+c-1)-1 = a+b+c-2$$ Since LHS $=$ RHS, the operation is associative.
3. Identity Element: We seek an element $e \in \mathbb{Z}$ such that $a*e = a$ for all $a \in \mathbb{Z}$. $$a*e = a \iff a + e - 1 = a \implies e - 1 = 0 \implies e = 1$$ Check: $1*a = 1 + a - 1 = a$. So $e=1$ is the unique identity element.
4. Inverse Element: For any $a \in \mathbb{Z}$, we seek an element $a' \in \mathbb{Z}$ such that $a*a' = e = 1$. $$a*a' = 1 \iff a + a' - 1 = 1 \implies a' = 2 - a$$ Since $a \in \mathbb{Z}$, $2-a$ is also an integer. Check: $a * (2-a) = a + (2-a) - 1 = 1$. Thus, every element has a valid inverse $a^{-1} = 2-a$.

Since all four axioms hold, $(\mathbb{Z}, *)$ is a group. ∎

Goal: Find the possible orders of elements in a group $G$ of order 33.

Step-by-Step Analysis:

1. Lagrange's Theorem Constraint: By Lagrange's Theorem (Corollary 1), the order of any element $a$ in a finite group $G$ must divide the order of the group $|G|$. $$\text{ord}(a) \mid |G|$$
2. Find divisors: The order of the group is $|G| = 33$. The prime factorization of 33 is $3 \cdot 11$. The positive divisors of 33 are: $$\{1, 3, 11, 33\}$$

Conclusion: The only possible orders of elements in $G$ are 1, 3, 11, and 33. (Note: Only the identity element $e$ has order 1). ∎

Goal: Verify the group axioms, compute element orders, and determine if the group of fourth roots of unity is cyclic.

Solution:

1. (a) Group Verification: We construct the Cayley table for complex multiplication over $G$:

   ×	1	−1	$i$	$-i$
   1	1	−1	$i$	$-i$
   −1	−1	1	$-i$	$i$
   $i$	$i$	$-i$	$-1$	$1$
   $-i$	$-i$	$i$	$1$	$-1$

   • Closure: No entries in the table lie outside $G$.
   • Associativity: Multiplicative associativity is inherited from $\mathbb{C}^*$.
   • Identity: The table shows $1$ acts as the identity element ($1 \cdot z = z$).
   • Inverses: Every row contains $1$. Thus, inverses exist: $1^{-1}=1$, $(-1)^{-1}=-1$, $i^{-1}=-i$, and $(-i)^{-1}=i$.
2. (b) Element Orders: The order $\text{ord}(z)$ is the smallest $k \geq 1$ such that $z^k = 1$.
   • $\text{ord}(1) = 1$
   • $(-1)^1 = -1, (-1)^2 = 1 \implies \text{ord}(-1) = 2$
   • $i^1 = i, i^2 = -1, i^3 = -i, i^4 = 1 \implies \text{ord}(i) = 4$
   • $(-i)^1 = -i, (-i)^2 = -1, (-i)^3 = i, (-i)^4 = 1 \implies \text{ord}(-i) = 4$
3. (c) Cyclic check: A group is cyclic if it has an element of order equal to the group order $|G| = 4$. Since $\text{ord}(i) = 4$, $G$ is cyclic. The generators are the elements of order 4, which are $i$ and $-i$. ∎

Goal: Prove that the set $S = \{1, 2, 3, 4, 5\}$ does not form a group under multiplication modulo 6.

Proof of Failure:

1. Check Closure: Let $a = 2$ and $b = 3$. Both are elements of $S$. Compute their product modulo 6: $$2 \times_6 3 = 6 \equiv 0 \pmod 6$$ Since $0 \notin S$, the set is not closed under the operation.
2. Check Inverses: Let $a = 2$. For $2$ to have an inverse, there must exist $x \in S$ such that $2 \cdot x \equiv 1 \pmod 6$. We test all elements of $S$:
   • $2 \cdot 1 \equiv 2$
   • $2 \cdot 2 \equiv 4$
   • $2 \cdot 3 \equiv 0$
   • $2 \cdot 4 \equiv 2$
   • $2 \cdot 5 \equiv 4$
   None of the products yield the identity $1$. Thus, $2$ lacks a multiplicative inverse (because $\gcd(2, 6) = 2 \neq 1$).

Conclusion: Since closure and the existence of inverses both fail, the structure is not a group. ∎

Goal: Construct the multiplication modulo 10 table for the group of units $U(10)$ and find the order of all elements.

Solution:

1. Identify Elements: $U(10)$ consists of all elements in $\mathbb{Z}_{10}$ coprime to 10. $$U(10) = \{1, 3, 7, 9\}$$
2. Construct Cayley Table:

   ×	1	3	7	9
   1	1	3	7	9
   3	3	9	1	7
   7	7	1	9	3
   9	9	7	3	1

3. Determine Orders:
   • $\text{ord}(1) = 1$
   • $3^1=3, 3^2=9, 3^3=7, 3^4=1 \implies \text{ord}(3) = 4$
   • $7^1=7, 7^2=9, 7^3=3, 7^4=1 \implies \text{ord}(7) = 4$
   • $9^1=9, 9^2=1 \implies \text{ord}(9) = 2$

Conclusion: $U(10)$ is a cyclic group of order 4, generated by 3 or 7. ∎

Goal: Evaluate the composition of two permutations in both directions and check for commutativity.

Step-by-Step Composition:

1. Evaluate $\sigma_2 \circ \sigma_1$ (evaluate right-to-left: first $\sigma_1$, then $\sigma_2$):
   • $(\sigma_2 \circ \sigma_1)(\spadesuit) = \sigma_2(\sigma_1(\spadesuit)) = \sigma_2(\diamondsuit) = \diamondsuit$
   • $(\sigma_2 \circ \sigma_1)(\heartsuit) = \sigma_2(\sigma_1(\heartsuit)) = \sigma_2(\heartsuit) = \spadesuit$
   • $(\sigma_2 \circ \sigma_1)(\diamondsuit) = \sigma_2(\sigma_1(\diamondsuit)) = \sigma_2(\spadesuit) = \heartsuit$
   So, $\sigma_2 \circ \sigma_1 = \begin{pmatrix} \spadesuit & \heartsuit & \diamondsuit \\ \diamondsuit & \spadesuit & \heartsuit \end{pmatrix}$.
2. Evaluate $\sigma_1 \circ \sigma_2$:
   • $(\sigma_1 \circ \sigma_2)(\spadesuit) = \sigma_1(\sigma_2(\spadesuit)) = \sigma_1(\heartsuit) = \heartsuit$
   • $(\sigma_1 \circ \sigma_2)(\heartsuit) = \sigma_1(\sigma_2(\heartsuit)) = \sigma_1(\spadesuit) = \diamondsuit$
   • $(\sigma_1 \circ \sigma_2)(\diamondsuit) = \sigma_1(\sigma_2(\diamondsuit)) = \sigma_1(\diamondsuit) = \spadesuit$
   So, $\sigma_1 \circ \sigma_2 = \begin{pmatrix} \spadesuit & \heartsuit & \diamondsuit \\ \heartsuit & \diamondsuit & \spadesuit \end{pmatrix}$.

Conclusion: Comparing outputs on $\spadesuit$: $(\sigma_2 \circ \sigma_1)(\spadesuit) = \diamondsuit$ but $(\sigma_1 \circ \sigma_2)(\spadesuit) = \heartsuit$. Since they differ, the compositions are not equal ($\sigma_2 \circ \sigma_1 \neq \sigma_1 \circ \sigma_2$). This confirms that the symmetric group $S_3$ is non-abelian. ∎

Goal: Identify all generating elements of the additive cyclic group $\mathbb{Z}_{24}$.

Step-by-Step Analysis:

1. Apply Generator Theorem: In any additive cyclic group $(\mathbb{Z}_n, +_n)$, an element $k$ is a generator if and only if $k$ is coprime to $n$: $$\gcd(k, n) = 1$$
2. Identify coprime numbers for $n=24$: The prime factorization of 24 is $2^3 \cdot 3$. Thus, we must find all integers $k$ in the range $1 \leq k < 24$ that are not divisible by 2 or 3. Applying Euler's totient function, the total number of generators is: $$\varphi(24) = 24 \cdot \left(1 - \frac{1}{2}\right) \cdot \left(1 - \frac{1}{3}\right) = 24 \cdot \frac{1}{2} \cdot \frac{2}{3} = 8$$
3. List the elements: The 8 coprime integers are: $$\{1, 5, 7, 11, 13, 17, 19, 23\}$$

Conclusion: The generators of $\mathbb{Z}_{24}$ are 1, 5, 7, 11, 13, 17, 19, and 23. ∎

Goal: Find the possible orders of element $x$ given the constraints on its powers.

Step-by-Step Analysis:

1. Apply Lagrange's Corollary: The order $\text{ord}(x)$ of any element must divide the group order $|G| = 33$. $$\text{ord}(x) \in \{1, 3, 11, 33\}$$
2. Eliminate based on constraints:
   • Constraint 1: $x \neq e \implies \text{ord}(x) \neq 1$.
   • Constraint 2: $x^{11} \neq e$. Recall that $a^m = e \iff \text{ord}(a) \mid m$. If the order of $x$ were 11, then $x^{11} = e$ would hold. Since it does not, the order of $x$ cannot be 11 (nor can it be 1). $$\text{ord}(x) \notin \{1, 11\}$$

Conclusion: The only remaining possible orders for $x$ are 3 and 33. ∎

Goal: Prove that any cyclic group $G$ is commutative (abelian) under its binary operation.

Proof:

1. Let $G$ be a cyclic group. By definition, there exists a generator $g \in G$ such that every element in $G$ can be expressed as a power of $g$. $$G = \langle g \rangle = \{g^k : k \in \mathbb{Z}\}$$
2. Choose any two arbitrary elements $x, y \in G$. Since $g$ generates $G$, there must exist integers $a$ and $b$ such that: $$x = g^a \quad \text{and} \quad y = g^b$$
3. Evaluate the group operation $x \cdot y$: $$x \cdot y = g^a \cdot g^b$$ By laws of exponents (since $a,b$ commute under integer addition): $$= g^{a+b} = g^{b+a} = g^b \cdot g^a = y \cdot x$$
4. Since $x \cdot y = y \cdot x$ for all $x,y \in G$, the group is abelian. ∎

Goal: Find the maximum order of elements in the Dihedral group $D_5$ and determine if it is cyclic.

Step-by-Step Analysis:

1. Analyze elements of $D_5$: The group $D_5$ represents the symmetries of a regular pentagon. It contains 10 elements:
   • 5 rotations: $\{e, r, r^2, r^3, r^4\}$. Since $\text{ord}(r) = 5$, the orders of these rotations are: $\text{ord}(e)=1$, $\text{ord}(r)=5$, $\text{ord}(r^2)=5$, $\text{ord}(r^3)=5$, $\text{ord}(r^4)=5$.
   • 5 reflections: $\{s, sr, sr^2, sr^3, sr^4\}$. Every reflection in a dihedral group has order 2 because reflecting twice returns the shape to its original state: $s^2 = e$.
2. Identify Maximum Order: The element orders present are $\{1, 2, 5\}$. Thus, the maximum element order is 5.
3. Determine if Cyclic: For $D_5$ to be cyclic, it would require a generator of order equal to the group order $|D_5| = 10$. Since the maximum element order is 5, no element of order 10 exists. Thus, $D_5$ is not cyclic. (Alternative proof: Cyclic groups are always abelian, but $D_5$ is non-abelian (e.g. $sr \neq rs$), hence not cyclic). ∎

Goal: Prove that if $a^m = e$ for a group element $a$ of order $n$, then $n$ must divide $m$.

Proof (using the division algorithm):

1. By the Division Algorithm, we can write the integer $m$ as: $$m = qn + r \quad \text{where } q, r \in \mathbb{Z} \text{ and } 0 \leq r < n.$$
2. Substitute this expression into the equation $a^m = e$: $$a^{qn + r} = e$$ $$(a^n)^q \cdot a^r = e$$
3. Since $\text{ord}(a) = n$, we know $a^n = e$. Substituting this: $$(e)^q \cdot a^r = e \implies e \cdot a^r = e \implies a^r = e$$
4. We now have $a^r = e$ with $0 \leq r < n$. By definition, the order $n$ is the *smallest positive* integer such that $a^n = e$. If $r$ were positive ($r > 0$), it would contradict $n$ being the smallest positive power since $r < n$. Therefore, the remainder $r$ must be exactly $0$.
5. Since $r = 0$, we have $m = qn$, which proves that $n$ divides $m$ ($n \mid m$). ∎

Goal: Find the additive order of 21 in $\mathbb{Z}_{30}$ and identify all other elements sharing this order.

Step-by-Step Calculation:

1. Calculate $\text{ord}(21)$: In any additive group $\mathbb{Z}_n$, the order of an element $a$ is: $$\text{ord}(a) = \frac{n}{\gcd(a, n)}$$ Here $n = 30$ and $a = 21$. Find the greatest common divisor: $$\gcd(21, 30) = 3$$ Compute the order: $$\text{ord}(21) = \frac{30}{3} = 10$$
2. Find other elements of order 10: An element $x \in \mathbb{Z}_{30}$ has order 10 if and only if: $$\frac{30}{\gcd(x, 30)} = 10 \iff \gcd(x, 30) = 3$$ We must find all elements in $\{0, \dots, 29\}$ that are multiples of 3 but not multiples of 2 or 5 (to avoid $\gcd$ being 6, 15, or 30).
   • Multiples of 3: $\{0, 3, 6, 9, 12, 15, 18, 21, 24, 27\}$
   • Remove multiples of 2 (even numbers): $\{3, 9, 15, 21, 27\}$
   • Remove multiples of 5: $\{3, 9, 21, 27\}$

Conclusion: $\text{ord}(21) = 10$, and the other elements with order 10 are 3, 9, and 27. ∎

Goal: Prove that if $a^2 = a$ for all elements in a ring $R$, then $ab = ba$ for all $a, b \in R$.

Proof:

1. Part 1: Prove that $2x = 0$ (so $x = -x$) for all $x \in R$. For any element $x$, apply the Boolean property to $x+x$: $$(x+x)^2 = x+x$$ Expand the LHS using the distributive laws: $$(x+x)^2 = (x+x)(x+x) = x^2 + x^2 + x^2 + x^2$$ Substitute $x^2 = x$: $$x + x + x + x = x + x \implies 2x = 0 \implies x = -x$$
2. Part 2: Expand $(a+b)^2$: For any $a, b \in R$, apply the Boolean property to $a+b$: $$(a+b)^2 = a+b$$ Expand the LHS: $$(a+b)(a+b) = a^2 + ab + ba + b^2 = a+b$$ Substitute $a^2 = a$ and $b^2 = b$: $$a + ab + ba + b = a + b$$ Subtract $a+b$ from both sides: $$ab + ba = 0 \implies ab = -ba$$
3. Part 3: Substitute $-ba = ba$ (from Part 1): $$ab = ba$$

Since $ab = ba$ for all $a, b \in R$, the ring is commutative. ∎

Goal: Verify the ring properties for the set $R = \{a + ib\sqrt{2} : a, b \in \mathbb{Z}\}$ and find all units (invertible elements).

Solution:

1. Ring Verification: We can show $R$ is a subring of $\mathbb{C}$. Since $\mathbb{C}$ is a ring, we only need to verify closure under subtraction and multiplication:
   • Subtraction: $(a_1 + ib_1\sqrt{2}) - (a_2 + ib_2\sqrt{2}) = (a_1-a_2) + i(b_1-b_2)\sqrt{2} \in R$.
   • Multiplication: $$(a_1 + ib_1\sqrt{2})(a_2 + ib_2\sqrt{2}) = a_1a_2 - 2b_1b_2 + i(a_1b_2 + b_1a_2)\sqrt{2}$$ Since the coefficients are integers, the product lies in $R$.
   Since $R$ is closed under subtraction and multiplication, and inherits ring properties from $\mathbb{C}$, it is a commutative ring with identity $1$.
2. Finding Units: Define the norm function $N(a + ib\sqrt{2}) = a^2 + 2b^2$. The norm is multiplicative: $N(zw) = N(z)N(w)$ for any $z, w \in R$. If $u = a + ib\sqrt{2}$ is a unit, there exists $v \in R$ such that $uv = 1$. $$N(uv) = N(u)N(v) = N(1) = 1^2 + 2(0)^2 = 1$$ Since $N(u), N(v)$ are non-negative integers, we must have: $$a^2 + 2b^2 = 1 \quad \text{where } a,b \in \mathbb{Z}$$
   • If $b \neq 0$, then $2b^2 \geq 2 \implies a^2 + 2b^2 \geq 2$ (no solution).
   • Thus $b = 0$, leaving $a^2 = 1 \implies a = \pm 1$.

Conclusion: The units of the ring are $1$ and $-1$. ∎

Goal: Prove that multiplying any element $a$ in a ring $R$ by the additive inverse of identity $-1$ yields the additive inverse $-a$.

Proof:

1. We evaluate the expression $a + (-1)a$: $$a + (-1)a = 1 \cdot a + (-1) \cdot a \quad \text{[by Multiplicative Identity]}$$ $$= (1 + (-1)) \cdot a \quad \text{[by Distributive Law]}$$
2. By definition of the additive inverse, $1 + (-1) = 0$: $$= 0 \cdot a$$
3. Recall the theorem that $0 \cdot x = 0$ for any ring element: $$0 \cdot a = 0 \implies a + (-1)a = 0$$
4. By uniqueness of the additive inverse in the group $(R, +)$, since $a + (-1)a = 0$, we must have: $$(-1)a = -a \quad \text{∎}$$

Goal: Find the product of the polynomials $(3x^2+2x-4)$ and $(4x^2+2)$, performing all coefficient arithmetic modulo 5.

Step-by-Step Multiplication:

1. Reduce coefficients modulo 5: $-4 \equiv 1 \pmod 5$. The expression simplifies to: $$(3x^2+2x+1)(4x^2+2)$$
2. Distribute terms: $$= 3x^2(4x^2+2) + 2x(4x^2+2) + 1(4x^2+2)$$ $$= (12x^4 + 6x^2) + (8x^3 + 4x) + (4x^2 + 2)$$
3. Combine terms with identical powers: $$= 12x^4 + 8x^3 + (6+4)x^2 + 4x + 2$$ $$= 12x^4 + 8x^3 + 10x^2 + 4x + 2$$
4. Reduce final coefficients modulo 5:
   • $12 \equiv 2 \pmod 5$
   • $8 \equiv 3 \pmod 5$
   • $10 \equiv 0 \pmod 5$
   • $4 \equiv 4 \pmod 5$
   • $2 \equiv 2 \pmod 5$
   Substitute these: $$= 2x^4 + 3x^3 + 4x + 2$$

Conclusion: The product polynomial in $\mathbb{Z}_5[x]$ is: $$2x^4 + 3x^3 + 4x + 2$$ ∎

Goal: Identify the set of elements in each ring that have a multiplicative inverse.

Analysis: An element $k \in \mathbb{Z}_n$ is a unit if and only if $\gcd(k, n) = 1$.

• (a) Units of $\mathbb{Z}_{10}$: Find all $k \in \{1, \dots, 9\}$ coprime to 10. $$\gcd(k, 10) = 1 \implies \mathbf{\{1, 3, 7, 9\}}$$
• (b) Units of $\mathbb{Z}_{12}$: Find all $k \in \{1, \dots, 11\}$ coprime to 12. $$\gcd(k, 12) = 1 \implies \mathbf{\{1, 5, 7, 11\}}$$
• (c) Units of $\mathbb{Z}_7$: Since 7 is a prime number, every nonzero element is coprime to 7. $$\gcd(k, 7) = 1 \implies \mathbf{\{1, 2, 3, 4, 5, 6\}}$$ ∎

Goal: Find the multiplicative inverse of 5, identify a non-unit, and evaluate whether $\mathbb{Z}_6$ is a field.

Step-by-Step Analysis:

1. Find $5^{-1} \pmod 6$: We seek $x \in \{1, \dots, 5\}$ such that $5x \equiv 1 \pmod 6$. $$5 \cdot 5 = 25 \equiv 1 \pmod 6 \implies 5^{-1} = 5$$
2. Find a non-unit: An element $k \neq 0$ is a non-unit if $\gcd(k, 6) \neq 1$. For $k = 2$, $\gcd(2, 6) = 2 \neq 1$. Therefore, 2 has no inverse.
3. Determine if $\mathbb{Z}_6$ is a field: By definition, a field is a commutative ring with identity where *every* nonzero element has a multiplicative inverse. Since $2 \in \mathbb{Z}_6$ is nonzero but has no inverse, $\mathbb{Z}_6$ is not a field.

Goal: Calculate the order of the general linear group of $2 \times 2$ matrices over the field $\mathbb{F}_3 = \mathbb{Z}_3$.

Step-by-Step Calculation:

1. An invertible matrix must have linearly independent rows. We choose the rows sequentially:
   • Row 1 ($v_1$): Can be any nonzero vector in $\mathbb{F}_3^2$. The total number of vectors in $\mathbb{F}_3^2$ is $3^2 = 9$. $$\text{Choices for } v_1 = 9 - 1 = 8$$
   • Row 2 ($v_2$): Must be linearly independent of $v_1$. This means $v_2$ cannot be a scalar multiple of $v_1$. The scalar multiples of $v_1$ in $\mathbb{F}_3$ are $c \cdot v_1$ for $c \in \{0, 1, 2\}$, which gives 3 vectors. $$\text{Choices for } v_2 = 9 - 3 = 6$$
2. Multiply choices to find total matrices: $$|GL_2(\mathbb{F}_3)| = 8 \cdot 6 = 48$$

Conclusion: there are 48 invertible $2\times 2$ matrices over $\mathbb{F}_3$. ∎

Goal: Find a polynomial $q(x) \in \mathbb{Z}_4[x]$ such that $(1+2x)q(x) \equiv 1 \pmod 4$.

Proof:

1. Consider the algebraic identity for difference of squares: $$(1+2x)(1-2x) = 1 - 4x^2$$
2. Perform arithmetic modulo 4: Since $4 \equiv 0 \pmod 4$, the term $4x^2$ becomes 0: $$1 - 4x^2 \equiv 1 - 0x^2 \equiv 1 \pmod 4$$
3. Thus, $(1+2x)(1-2x) = 1$. In $\mathbb{Z}_4$, $-2 \equiv 2$, so $1 - 2x = 1 + 2x$. The polynomial is its own inverse: $(1+2x)^2 = 1 + 4x + 4x^2 \equiv 1 \pmod 4$. Since an inverse exists, $1+2x$ is a unit. ∎

Goal: Compute the modular powers of 2 modulo 13 and check if 2 is a generator of $\mathbb{Z}_{13}^*$.

Step-by-Step Calculation:

1. Compute powers:
   • $2^1 \equiv 2$
   • $2^2 \equiv 4$
   • $2^3 \equiv 8$
   • $2^4 = 16 \equiv 3$
   • $2^5 = 2^4 \cdot 2 \equiv 3 \cdot 2 = 6$
   • $2^6 = 2^5 \cdot 2 \equiv 6 \cdot 2 = 12$
   • $2^7 = 2^6 \cdot 2 \equiv 12 \cdot 2 = 24 \equiv 11$
   • $2^8 = 2^7 \cdot 2 \equiv 11 \cdot 2 = 22 \equiv 9$
   • $2^9 = 2^8 \cdot 2 \equiv 9 \cdot 2 = 18 \equiv 5$
   • $2^{10} = 2^9 \cdot 2 \equiv 5 \cdot 2 = 10$
   • $2^{11} = 2^{10} \cdot 2 \equiv 10 \cdot 2 = 20 \equiv 7$
   • $2^{12} = 2^{11} \cdot 2 \equiv 7 \cdot 2 = 14 \equiv 1$
2. Check if the set of powers matches $\mathbb{Z}_{13}^*$: The set of generated values is $\{2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7, 1\}$. Since this contains all 12 elements of $\mathbb{Z}_{13}^*$ ($|\mathbb{Z}_{13}^*| = 12$), the order of 2 is 12.

Conclusion: Since $\text{ord}(2) = 12 = |\mathbb{Z}_{13}^*|$, 2 is a primitive root mod 13. ∎

Goal: Perform the step-by-step calculations for the Diffie–Hellman key exchange protocol with the given parameters.

Step-by-Step Calculation:

1. Alice computes her public key $A$: $$A = g^a \bmod p = 2^4 \bmod 13 = 16 \bmod 13 = 3$$
2. Bob computes his public key $B$: $$B = g^b \bmod p = 2^3 \bmod 13 = 8$$
3. Alice computes the shared key $K$: $$K = B^a \bmod p = 8^4 \bmod 13$$ Compute $8^2 = 64 \equiv 12 \equiv -1 \pmod{13}$. $$8^4 \equiv (-1)^2 \equiv 1 \pmod{13} \implies K = 1$$
4. Bob computes the shared key $K$: $$K = A^b \bmod p = 3^3 \bmod 13 = 27 \bmod 13 = 1$$

Conclusion: Alice sends $A=3$, Bob sends $B=8$, and both compute the identical shared key $K=1$. ∎

Goal: Crack the DH parameters by solving the Discrete Logarithm Problem and explain the security limitations on large primes.

Solution:

1. Solve for Alice's private key $a$: Eve knows $g^a \equiv A \pmod p \implies 2^a \equiv 3 \pmod{13}$. From the powers-of-2 table calculated previously: $$2^4 \equiv 3 \implies a = 4$$
2. Calculate Shared Key: $$K = B^a \bmod p = 8^4 \bmod 13 \equiv 1 \pmod{13}$$
3. Security for 2048-bit prime: For $p \approx 2^{2048}$, the group size is $\sim 10^{616}$. To find $a$ given $g^a \bmod p$, there is no known polynomial-time algorithm. Algorithms like Baby-step Giant-step or Index Calculus still require exponential or sub-exponential time, which makes brute-force or algebraic extraction computationally impossible on modern computers. ∎

Goal: Determine which of the given algebraic structures are fields, providing formal justifications.

Analysis: A field requires every nonzero element to have a multiplicative inverse.

• (a) $\mathbb{Z}_{18}$: Not a field. The modulus 18 is composite ($2 \cdot 9$), meaning $\mathbb{Z}_{18}$ contains zero divisors (e.g. $2 \cdot 9 \equiv 0$). Zero divisors cannot have inverses, so it is not a field.
• (b) $\mathbb{Q}(\sqrt 2) = \{a + b\sqrt{2} : a,b \in \mathbb{Q}\}$: Field. For any nonzero $a + b\sqrt{2}$, its inverse is: $$\frac{1}{a + b\sqrt{2}} = \frac{a - b\sqrt{2}}{a^2 - 2b^2} = \left(\frac{a}{a^2 - 2b^2}\right) + \left(\frac{-b}{a^2 - 2b^2}\right)\sqrt{2}$$ Since $a^2 - 2b^2 \neq 0$ (as $\sqrt{2}$ is irrational), the rational coefficients are well-defined. Thus, the inverse lies in $\mathbb{Q}(\sqrt 2)$.
• (c) $\mathbb{Z}[\sqrt 3] = \{a + b\sqrt{3} : a,b \in \mathbb{Z}\}$: Not a field. Consider the element $\sqrt{3} \in \mathbb{Z}[\sqrt 3]$. For $\sqrt{3}$ to have an inverse $x + y\sqrt{3}$, we must have: $$\sqrt{3}(x + y\sqrt{3}) = 3y + x\sqrt{3} = 1 \implies 3y = 1 \implies y = 1/3$$ Since $1/3 \notin \mathbb{Z}$, the inverse does not exist in the set.
• (d) $\mathbb{Z}_3[i] \cong \mathbb{Z}_3[x]/(x^2+1)$: Field. This is a quotient polynomial ring. It is a field if and only if $x^2 + 1$ is irreducible over $\mathbb{F}_3$. We check for roots in $\mathbb{Z}_3$:
  • $0^2 + 1 = 1 \neq 0$
  • $1^2 + 1 = 2 \neq 0$
  • $2^2 + 1 = 5 \equiv 2 \neq 0$
  Since there are no roots, the degree-2 polynomial is irreducible, making $\mathbb{Z}_3[i]$ a field of size $3^2 = 9$. ∎