Week 19 — Groups, Rings, and Fields

Overview

Abstract algebra studies sets equipped with operations satisfying specified axioms — and asks what must follow from those axioms alone, without reference to the particular objects involved. The payoff is enormous: the same theorems apply simultaneously to the symmetries of a geometric object, the integers modulo \(n\), the invertible matrices over a field, and the roots of a polynomial. This week builds the three-level hierarchy: groups (one operation, capturing symmetry and invertibility), rings (two operations linked by distributivity, capturing arithmetic), and fields (rings in which every nonzero element has a multiplicative inverse, capturing division). Homomorphisms — structure-preserving maps — and the quotient constructions they generate are the central tools. Everything here feeds directly into Week 20, where the same machinery is applied to polynomial rings to construct the finite fields underlying cryptography and coding theory.

Readings

Pinter Ch 2–4 — Operations and groups. Binary operations, the group axioms, elementary consequences, and the first examples: \(\mathbb{Z}\), \(\mathbb{Z}_n\), \(S_n\), \(GL_n(F)\).
Pinter Ch 5, 9–11 — Subgroups, isomorphisms, order, and cyclic groups. Subgroup criterion; isomorphisms and structural identity; order of an element; cyclic groups and their classification.
Pinter Ch 13–16 — Cosets, Lagrange, homomorphisms, and quotient groups. Coset partition; Lagrange’s theorem (\(|H|\) divides \(|G|\)); group homomorphisms and their kernels; normal subgroups and quotient groups \(G/N\); the fundamental homomorphism theorem.
Pinter Ch 17–21 — Rings, ideals, and fields. Ring axioms and examples (\(\mathbb{Z}\), \(\mathbb{Z}_n\), \(F[x]\)); ideals and quotient rings; integral domains (no zero divisors); the field of quotients of an integral domain.

Key Concepts

Groups and the axioms

A group \((G, \cdot)\) is a set with a binary operation satisfying four axioms: closure, associativity, a unique identity \(e\) (\(ea = ae = a\)), and an inverse \(a^{-1}\) for each \(a\) (\(aa^{-1} = a^{-1}a = e\)). The group is abelian if the operation commutes. The canonical examples span the course:

\[(\mathbb{Z}, +), \quad (\mathbb{Z}_n, +), \quad (\mathbb{Z}_n^*, \cdot), \quad (S_n, \circ), \quad (GL_n(F), \cdot).\]

The first three are abelian; \(S_n\) (permutations of \(n\) symbols) and \(GL_n(F)\) (invertible matrices) are not for \(n \ge 3\), \(n \ge 2\). Note \(\mathbb{Z}_n^*\) — the units mod \(n\), i.e. residues coprime to \(n\) — is the group RSA lives in.

Subgroups, cosets, and Lagrange’s theorem

A subgroup \(H \le G\) is a subset closed under the operation and inverses. Its left cosets \(gH\) partition \(G\) into blocks of equal size \(|H|\), which forces Lagrange’s theorem:

\[|G| = [G:H]\,|H|, \qquad \text{so } |H| \text{ divides } |G|.\]

The index \([G:H]\) is the number of cosets. The immediate corollary — the order of every element divides \(|G|\), hence \(a^{|G|} = e\) — is the algebraic engine behind number theory: applied to \(\mathbb{Z}_p^*\) (order \(p-1\)) it gives Fermat’s little theorem \(a^{p-1} \equiv 1 \pmod p\), and applied to \(\mathbb{Z}_n^*\) (order \(\phi(n)\)) it gives Euler’s theorem \(a^{\phi(n)} \equiv 1 \pmod n\) — the identity RSA decryption relies on.

Cyclic groups and generators

\(G\) is cyclic if a single element generates it: \(G = \langle a\rangle = \{a^k : k \in \mathbb{Z}\}\). Up to isomorphism the only cyclic groups are

\[\mathbb{Z} \ (\text{infinite}) \qquad \text{and} \qquad \mathbb{Z}_n \ (\text{order } n).\]

Every group of prime order is cyclic. Crucially, \(\mathbb{Z}_p^*\) is cyclic of order \(p-1\): a generator is a primitive root mod \(p\), and writing every nonzero residue as a power of it is exactly what makes the discrete logarithm well-defined — the hard problem behind Diffie–Hellman and the multiplicative-group setting that elliptic curves later replace.

Homomorphisms, normal subgroups, and quotient groups

A homomorphism \(\phi: G \to H\) preserves the operation, \(\phi(ab) = \phi(a)\phi(b)\). Its kernel \(\ker\phi = \{g : \phi(g) = e_H\}\) is always a normal subgroup (\(gNg^{-1} = N\) for all \(g\)), and normal subgroups are exactly the kernels. Modding out by one produces the quotient group \(G/N\), whose elements are cosets multiplied by \((gN)(hN) = (gh)N\). The first isomorphism theorem ties these together:

\[G/\ker\phi \;\cong\; \operatorname{im}\phi.\]

This is the group-theoretic template for the ring quotient that builds finite fields next week.

Rings, integral domains, and fields

A ring \((R, +, \cdot)\) is an abelian group under \(+\) with an associative multiplication distributing over \(+\). Adding hypotheses narrows the hierarchy:

\[\text{ring} \;\supset\; \text{integral domain} \;\supset\; \text{field},\]

where an integral domain is a commutative ring with \(1 \ne 0\) and no zero divisors (\(ab = 0 \Rightarrow a = 0\) or \(b = 0\)), and a field additionally has a multiplicative inverse for every nonzero element. Every field is an integral domain; conversely every finite integral domain is a field — the fact that makes \(\mathbb{Z}_p\) and all the finite fields of Week 20 fields at all.

Ideals and quotient rings

An ideal \(I \subseteq R\) is an additive subgroup absorbing multiplication (\(rI \subseteq I\) for all \(r \in R\)) — the ring analogue of a normal subgroup, and exactly what you can quotient by to form \(R/I\). The quotient’s structure is governed by the ideal:

\[R/I \text{ is a field} \iff I \text{ is a maximal ideal}.\]

In \(\mathbb{Z}\) the maximal ideals are \((p)\) for \(p\) prime, recovering \(\mathbb{Z}/(p) \cong \mathbb{F}_p\). In \(F[x]\) the maximal ideals are \((p(x))\) for \(p\) irreducible — the construction that yields every finite field in Week 20.

Connections

Forward: Week 20 applies the quotient-ring construction to polynomial rings: \(F[x]/(p(x))\) is a field extension of \(F\) when \(p(x)\) is irreducible — the factory for all finite fields.
Backward: Lagrange’s theorem underlies Fermat’s little theorem and Euler’s theorem (Week 15’s complexity theory assumed these; this week makes the algebra rigorous). The group \((\mathbb{Z}_n^*, \cdot)\) was implicit throughout number-theoretic reasoning in Weeks 6–7.
Across courses: Not tied to the applied courses directly, but the group-theoretic and ring-theoretic framework here underlies every cryptographic primitive (RSA, Diffie-Hellman, elliptic curve) and the algebraic error correcting codes (Reed-Solomon, BCH) used in communications and storage.