Abstract Algebra

4.1 Group Axioms

The standard checklist

To prove a structure is a group, verify the four axioms in order. To disprove one, exhibit a failure of one axiom.

Useful basic facts (proved in lecture, used freely)

• The identity is unique.
• Inverses are unique.
• $(a^{-1})^{-1} = a$.
• $(ab)^{-1} = b^{-1}a^{-1}$ (order swaps!).
• Cancellation: $ab = ac \Rightarrow b = c$; $ba = ca \Rightarrow b = c$.

4.2 Addition Modulo Groups $(\mathbb{Z}_n, +_n)$

$\mathbb{Z}_n = \{0, 1, 2, \ldots, n-1\}$ with addition $\pmod n$ is the canonical example of a finite group.

4.3 Multiplication Modulo Groups $(\mathbb{Z}_n^*, \times_n)$

$\mathbb{Z}_n^*$ is the set of elements of $\mathbb{Z}_n$ that are coprime to $n$. With multiplication mod $n$, it forms a group.

4.4 Other Important Groups

The dihedral group $D_4$ (square symmetries)

$D_4$ has 8 elements: 4 rotations $\{e, r, r^2, r^3\}$ (by $0°, 90°, 180°, 270°$) and 4 reflections. It is non-abelian: rotating then reflecting differs from reflecting then rotating.

4.5 Order of an Element / Order of a Group

Properties

• $\text{ord}(e) = 1$.
• $\text{ord}(a) = \text{ord}(a^{-1})$.
• If $a^m = e$, then $\text{ord}(a)$ divides $m$. (Key lemma; comes up in many problems.)
• If $\text{ord}(a) = n$, then $a^k = e \iff n \mid k$.
• $\text{ord}(a^k) = n/\gcd(n, k)$ where $n = \text{ord}(a)$.

4.6 Cyclic Groups

Examples

• $\mathbb{Z}$ is cyclic, generated by $1$ (also by $-1$).
• $\mathbb{Z}_n$ is cyclic for every $n$. Generators are the elements coprime to $n$. There are $\varphi(n)$ generators.
• $\mathbb{Z}_p^*$ for prime $p$ is cyclic of order $p - 1$.
• $D_4$ is NOT cyclic (it's non-abelian, but cyclic groups are always abelian).

Key theorems about cyclic groups

• Every cyclic group is abelian. Because $g^a \cdot g^b = g^{a+b} = g^b \cdot g^a$.
• Every subgroup of a cyclic group is cyclic.
• In a cyclic group of order $n$ generated by $g$, the subgroup generated by $g^k$ has order $n/\gcd(n,k)$.
• The generators of $\mathbb{Z}_n$ are exactly $\{k : \gcd(k, n) = 1\}$.

4.7 Lagrange's Theorem

Two crucial corollaries

Proof sketch of Corollary 1: $\langle a \rangle$ is a subgroup with $|\langle a \rangle| = \text{ord}(a)$. By Lagrange, this divides $|G|$.

4.8 Rings

Standard examples

• $\mathbb{Z}, \mathbb{Q}, \mathbb{R}, \mathbb{C}$ are commutative rings with identity.
• $\mathbb{Z}_n$ for any $n$.
• $M_n(\mathbb{R})$, $n \times n$ real matrices, is a non-commutative ring with identity.
• $R[x]$ — polynomials over a ring $R$ — is a ring.
• $n\mathbb{Z} = \{0, \pm n, \pm 2n, \ldots\}$: ring without identity (for $n \neq 1$).

Units, zero-divisors, integral domains

• A unit is an element $a$ with a multiplicative inverse. The units of $\mathbb{Z}_n$ are $\mathbb{Z}_n^*$.
• A zero divisor is a nonzero $a$ with $ab = 0$ for some nonzero $b$. e.g., $2\cdot 3 = 0$ in $\mathbb{Z}_6$ — both 2 and 3 are zero divisors.
• An integral domain is a commutative ring with identity and no zero divisors.
• A field is a commutative ring with identity where every nonzero element is a unit.

4.9 Polynomial Rings $R[x]$

$R[x]$ is the set of polynomials $a_n x^n + \cdots + a_1 x + a_0$ with coefficients in $R$. Operations are the usual sum and product, with coefficient arithmetic in $R$.

Listing polynomials in $\mathbb{Z}_2[x]$ of degree $\leq 3$

Coefficients are 0 or 1. We have $a_3, a_2, a_1, a_0 \in \{0,1\}$ — that's $2^4 = 16$ polynomials. Examples: $0, 1, x, x+1, x^2, x^2+1, \ldots, x^3+x^2+x+1$.

Key facts

• If $R$ is a commutative ring with identity, so is $R[x]$.
• If $R$ is an integral domain, so is $R[x]$.
• $R[x]$ is never a field, even when $R$ is — because $x$ is not a unit (no polynomial $q(x)$ satisfies $x \cdot q(x) = 1$, since degrees don't match).
• In $F[x]$ where $F$ is a field, every polynomial of degree $n$ has at most $n$ roots in $F$.

4.10 Fields

Examples and non-examples

• ✓ $\mathbb{Q}, \mathbb{R}, \mathbb{C}$ — classic infinite fields.
• ✓ $\mathbb{Z}_p$ for $p$ prime. (Because every nonzero element is coprime to $p$, so invertible.) These are called $\mathbb{F}_p$.
• ✗ $\mathbb{Z}$ — only $\pm 1$ have inverses, so it's an integral domain but not a field.
• ✗ $\mathbb{Z}_n$ for $n$ composite — has zero divisors. e.g., $\mathbb{Z}_6$: $2\cdot 3 = 0$.
• ✓ $\mathbb{Q}(\sqrt 2) = \{a + b\sqrt 2 : a, b \in \mathbb{Q}\}$ — a field.
• ✗ $\mathbb{Z}[\sqrt 2]$ — not a field (e.g., $\sqrt 2$ has no inverse here).

Finite fields

A finite field has $p^k$ elements for some prime $p$ and $k \geq 1$. The simplest example is $\mathbb{F}_p = \mathbb{Z}_p$. For $p^k$ with $k\geq 2$, you build the field as $\mathbb{F}_p[x]/(f(x))$ where $f$ is an irreducible polynomial of degree $k$.

4.11 Primitive Elements (Generators of $\mathbb{Z}_p^*$)

How to test primitivity

To check if $g$ is a primitive root mod $p$:

1. Factor $p - 1 = q_1^{a_1} q_2^{a_2} \cdots q_k^{a_k}$.
2. For each prime factor $q_i$, compute $g^{(p-1)/q_i} \pmod p$.
3. If any of these equals $1$, $g$ is NOT primitive. Otherwise, $g$ IS primitive.

4.12 Cryptography: Discrete Log & Diffie–Hellman

The Discrete Logarithm Problem (DLP)

For small $p$ this is easy by exhaustive search. For $p$ a 2048-bit prime, this is currently infeasible — no known polynomial-time algorithm. This asymmetry (easy to exponentiate, hard to invert) is what cryptography relies on.

Diffie–Hellman Key Exchange

Allows Alice and Bob to establish a shared secret over an insecure channel.

1. Public agreement. Both agree on a prime $p$ and a primitive root $g$. These are public.
2. Alice picks a private $a$, sends Bob $A = g^a \bmod p$.
3. Bob picks a private $b$, sends Alice $B = g^b \bmod p$.
4. Alice computes $K = B^a \bmod p$.
5. Bob computes $K = A^b \bmod p$.
6. Both have $K = g^{ab} \bmod p$ as their shared secret.

Modular arithmetic playground

Enter any modulus $n$ (2–100) and see Euler's totient, units, generators, element orders, and primitive roots — all computed instantly.

Interactive — Cayley table generator

Pick a group; see its full Cayley table and the order of each element. Hover any cell to highlight its row, column, and the result.

Interactive — Diffie–Hellman walkthrough

Pick a small prime $p$, primitive root $g$, and the private keys $a$ and $b$. Step through the protocol and see what Alice, Bob, and Eve each know at every stage.

Problem Bank — Abstract Algebra