Exercises: Algebraic Structures — Groups, Rings, and Fields

These exercises move from mechanical axiom-checking to full proofs, code, finite-field arithmetic, and modeling. Difficulty: ⭐ foundational, ⭐⭐ intermediate, ⭐⭐⭐ challenging. Worked solutions to the daggered (†) and odd-numbered problems are in the appendix answers-to-selected.md — attempt them before you peek. Throughout, "group," "ring," and "field" mean exactly what §24.2 and §24.4 defined, and "ring" means a commutative ring with unity unless stated otherwise.

Part A — Warm-ups: compute and check (⭐)

24.1 † For each of the following, list the elements and state the order of the group. (a) $(\mathbb{Z}_9, +)$. (b) $\mathbb{Z}_9^*$ under multiplication. (c) $\mathbb{Z}_{15}^*$ under multiplication.

24.2 In $(\mathbb{Z}_{12}, +)$, compute the order of each of the elements $3$, $4$, and $8$ (the smallest $k>0$ with $ka \equiv 0 \pmod{12}$).

24.3 † Find the inverse of $5$ in each group where it exists: (a) $(\mathbb{Z}_8^*, \cdot)$, (b) $(\mathbb{Z}_{11}^*, \cdot)$. If it does not exist, say which axiom or membership condition fails.

24.4 Decide, axiom by axiom, whether $(\mathbb{Z}, -)$ — the integers under subtraction — is a group. Name the first axiom that fails, if any.

24.5 † List the elements of the subgroup of $(\mathbb{Z}_{10}, +)$ generated by $2$ (i.e. the set of all multiples of $2$ mod $10$). What is its order, and does that order divide $10$ as Lagrange requires?

24.6 Using Theorem 24.4, decide which of $\mathbb{Z}_{13}$, $\mathbb{Z}_{14}$, $\mathbb{Z}_{17}$, $\mathbb{Z}_{21}$ are fields. For each non-field, give one nonzero element with no multiplicative inverse and the zero-divisor equation that dooms it.

Part B — Prove it (⭐⭐)

24.7 † (Scaffolded — fill in the missing steps.) Prove the left-cancellation law in a group: if $a \ast b = a \ast c$ then $b = c$. Fill the blanks. - Start from $a \ast b = a \ast c$. Left-multiply both sides by $\underline{\hphantom{xxxx}}$, which exists by the ___ axiom. - The left side becomes $(a^{-1} \ast a)\ast b = \underline{\hphantom{xxxx}} \ast b = b$, using ___ and then the identity axiom. - The right side becomes $\underline{\hphantom{xxxx}}$ by the same two steps. - Therefore $b = c$. $\blacksquare$ Then state in one sentence why this law fails in a general ring under multiplication (give $\mathbb{Z}_6$ as the witness).

24.8 Prove that in any group, $(a \ast b)^{-1} = b^{-1} \ast a^{-1}$ (the "socks-and-shoes" rule). Verify the claim by checking that $(a\ast b)\ast(b^{-1}\ast a^{-1}) = e$.

24.9 † Prove that in any group, $(a^{-1})^{-1} = a$. (Use the uniqueness of inverses from Theorem 24.1: show $a$ behaves as an inverse of $a^{-1}$.)

24.10 Let $G$ be a group in which every element satisfies $a \ast a = e$ (every element is its own inverse). Prove that $G$ is abelian. (Hint: expand $(a\ast b)\ast(a \ast b) = e$ and cancel.) Note that $\mathrm{GF}(2^n)$ under addition is exactly such a group.

24.11 † Prove that a field has no zero divisors: if $x \cdot y = 0$ in a field $F$ and $x \ne 0$, then $y = 0$. (This is the general fact the "$\Rightarrow$" half of Theorem 24.4 used; give it cleanly.)

24.12 Prove that the set $H = \{1, 4\}$ is a subgroup of $(\mathbb{Z}_5^*, \cdot)$ by checking the three subgroup conditions, then confirm Lagrange's theorem on it ($\lvert H\rvert$ divides $\lvert \mathbb{Z}_5^*\rvert$).

Part C — Implement it (⭐⭐)

Write Python for each. Do not execute it — hand-trace and include an # Expected output: comment, matching the book's convention. Reference solutions live in code/exercise-solutions.py.

24.13 † Write element_order(a, n) that returns the order of a in $(\mathbb{Z}_n, +)$ — the smallest $k > 0$ with $ka \equiv 0 \pmod n$. Hand-trace it on element_order(4, 12) and state the expected output.

24.14 Write is_group(elems, op) that takes a set of elements and a two-argument operation, and returns True iff the four group axioms hold. (You may reuse the is_closed / is_associative helpers from §24.1; you must also check for an identity and that every element has an inverse.) Show the output for $(\mathbb{Z}_5, +)$ and for $(\mathbb{Z}_6, \cdot)$ — i.e. all of $\mathbb{Z}_6$ under multiplication.

24.15 † Write is_generator(g, n) that returns True iff g generates $(\mathbb{Z}_n^*, \cdot)$, by listing the distinct powers of g mod n and checking the count equals $\phi(n) = \lvert \mathbb{Z}_n^*\rvert$. (You may reuse powers_mod from §24.3.) Show the outputs for is_generator(3, 7) and is_generator(2, 7).

24.16 Adapt the §24.5 routine gf8_mul into gf_mul(a, b, mod, deg) that multiplies in $\mathrm{GF}(2^{\text{deg}})$ for an arbitrary degree and irreducible modulus. Hand-trace gf_mul(0b10, 0b10, 0b1011, 3) — i.e. $x \cdot x$ in $\mathrm{GF}(2^3)$ — and give the expected output.

Part D — Find the error (⭐⭐)

Each argument below is flawed. State precisely which step fails and why; then give the correct conclusion.

24.17 † Claim: "$(\mathbb{Z}_6, \cdot)$ is a group, because multiplication mod 6 is closed, associative, and has identity $1$." "Proof": "Closure ✓, associativity ✓, identity $1$ ✓, so it's a group." — Find the flaw, and identify a specific element with no inverse.

24.18 Claim: "$\mathrm{GF}(8) = \mathbb{Z}_8$, since both have 8 elements and 8 is a prime power." "Proof": "By Theorem 24.5 a field of order 8 exists, and $\mathbb{Z}_8$ has 8 elements, so it is that field." — Find the flaw. Exhibit a zero divisor in $\mathbb{Z}_8$ to show it is not even a field.

24.19 † Claim: "In any group, if $a^2 = e$ then $a = e$." "Proof": "From $a^2 = e$, take square roots: $a = e^{1/2} = e$." — Find the flaw, and give a concrete counterexample from a group in this chapter.

24.20 Claim: "Every subset of $(\mathbb{Z}_6, +)$ that contains $0$ is a subgroup." "Proof": "It contains the identity, which is what a subgroup needs." — Find the flaw, and give a 2-element subset of $\mathbb{Z}_6$ containing $0$ that is not a subgroup, naming the condition it violates.

Part E — Model it (⭐⭐⭐)

24.21 † (Model it.) A music-sequencer plug-in transposes notes on a 12-tone scale: each note is a number $0$–$11$ (C, C♯, …, B), and "transpose up by $k$ semitones" wraps around the octave. The designer wants to know: (i) which transpositions, applied repeatedly, eventually cycle through all twelve notes? (ii) which ones get "stuck" hitting only some notes? Model the twelve notes and transposition as an algebraic structure, identify it exactly, and answer both questions using the language of generators and subgroups. Which value of $k$ corresponds to the "circle of fifths"?

24.22 (Model it.) A distributed-systems team assigns each of $n$ servers a slot on a logical ring and rotates write-leadership by a fixed step $s$ each round. Leadership must visit every server before repeating, or some server starves. Translate "every server eventually leads" into a statement about the subgroup of $(\mathbb{Z}_n, +)$ generated by $s$, and state the exact condition on $\gcd(s, n)$ that guarantees no starvation. (This is the §24.3 generator idea wearing an ops hat.)

Part F — Conjecture and test (⭐⭐⭐)

For each, use code on many cases to form a conjecture, then prove or disprove it.

24.23 † (Conjecture and test, then prove.) For primes $p = 3, 5, 7, 11, 13$, compute $\lvert \mathbb{Z}_p^*\rvert$ and the order of every element. Conjecture a formula for $\lvert \mathbb{Z}_p^*\rvert$ and a statement about which orders are possible. Then prove the formula for $\lvert \mathbb{Z}_p^*\rvert$, and explain — citing Lagrange — why the only possible element orders are the divisors of $p-1$.

24.24 (Conjecture and test.) Define $f(n) = $ "the number of generators of $(\mathbb{Z}_n, +)$." Compute $f(n)$ for $n = 5, 6, 7, 8, 9, 10, 12$ by listing, for each residue, the subgroup it generates and checking whether it is all of $\mathbb{Z}_n$. Conjecture a closed form for $f(n)$ in terms of a function from Chapter 23, and justify it in one or two sentences. (You are rediscovering a classical identity.)

24.25 † (Conjecture and test, then prove.) In $(\mathbb{Z}_p^*, \cdot)$ for an odd prime $p$, compute $a^{(p-1)/2} \bmod p$ for several $a$ and several primes. You will find the result is always $1$ or $p-1$. Conjecture which it is in terms of whether $a$ is a perfect square mod $p$, and prove the weaker fact that $\left(a^{(p-1)/2}\right)^2 \equiv 1 \pmod p$ always — hence $a^{(p-1)/2} \equiv \pm 1$. (Use Corollary 24.3; the full criterion is Euler's, a preview of quadratic residues.)

Part G — Finite fields by hand (⭐⭐⭐)

24.26 In $\mathrm{GF}(2^3)$ with irreducible $m(x) = x^3 + x + 1$ (so $x^3 \equiv x+1$), build the addition table for the four elements $\{0,\ 1,\ x,\ x+1\}$ using bitwise XOR, and confirm every element is its own additive inverse.

24.27 † In $\mathrm{GF}(2^3)$ with $x^3 \equiv x+1$, compute $(x^2 + 1)\cdot(x + 1)$ by multiplying the polynomials and reducing. Show every step.

24.28 Using the power table for the primitive element $g = x$ in §24.5 (where $g^1=x,\ \dots,\ g^7=1$), multiply $(x^2+x)\cdot(x^2+1)$ by converting to exponents, adding mod 7, and converting back — the "log-table" method. Confirm your answer by direct polynomial multiplication and reduction.

Part H — Interleaved & Deep Dive

Mixing techniques from earlier chapters keeps them sharp.

24.29 † (Ch. 23 + 24.) Restate Fermat's little theorem ($a^{p-1}\equiv 1 \pmod p$ for $p \nmid a$) as the special case of Corollary 24.3 in a specific group. Name the group, state its order, and write the one line that turns Corollary 24.3 into Fermat.

24.30 (Ch. 22 + 24.) The membership test for $\mathbb{Z}_n^*$ is "$\gcd(a,n)=1$." Using the extended Euclidean algorithm from Chapter 22, explain in two-to-three sentences why $\gcd(a,n)=1$ is exactly the condition for $a$ to have a multiplicative inverse mod $n$ — i.e. why the units of the ring $\mathbb{Z}_n$ are precisely the residues coprime to $n$.

24.31 † (Ch. 8 + 24.) Write $\mathbb{Z}_{20}^*$ in set-builder notation, give its cardinality $\phi(20)$, and — using only Lagrange's theorem — list every possible order an element of $\mathbb{Z}_{20}^*$ could have. (You need not find an element of each order.)

24.32 (Ch. 15 + 24.) A toy RSA modulus is $n = pq = 7 \cdot 11$. Compute $\phi(n) = \lvert \mathbb{Z}_n^\rvert$, and explain — in terms of the *order of the group* $\mathbb{Z}_n^$ and Corollary 24.3 — why an RSA public exponent $e$ must be chosen with $\gcd(e, \phi(n)) = 1$ and why the private exponent satisfies $ed \equiv 1 \pmod{\phi(n)}$ rather than $\pmod n$.

24.33 † (Deep Dive.) Prove Corollary 24.3 directly for abelian groups without citing Lagrange, by the "product of all elements" trick: in a finite abelian group $G = \{g_1,\dots,g_N\}$, show that for any $a$, the map $g \mapsto a \ast g$ is a bijection, so multiplying all elements together two ways gives $\prod_i g_i = a^N \ast \prod_i g_i$; then cancel to get $a^N = e$. State where commutativity is used.

24.34 (Deep Dive.) The classification theorem (24.5) says no field has exactly 6 elements. Give a short argument for why the integers mod 6 specifically fail to be a field, and explain why that single example does not by itself prove "no 6-element field exists" — what extra work would the full classification require?

24.35 (Deep Dive — connects to Ch. 38.) A Reed–Solomon code treats data as coefficients of a polynomial over $\mathrm{GF}(2^8)$ and relies on being able to divide. In two-to-three sentences, explain why a ring with zero divisors (such as $\mathbb{Z}_{256}$) could not replace the field $\mathrm{GF}(2^8)$ here — i.e. which step of error-correction would break, and connect it to the no-zero-divisors fact of Exercise 24.11.

Solutions to † and odd-numbered exercises: see appendices/answers-to-selected.md. For each proof, the rubric rewards: explicit use of the named axiom at each step, no appeal to commutativity unless the group is stated abelian, and a clean conclusion ending in $\blacksquare$.