Groups, rings and fields

A group needs closure, associativity, an identity and inverses

Every cryptographic scheme this unit covers computes inside one of a small number of algebraic shapes, and which shape it is decides what operations are available. RSA works inside $\mathbb{Z}_n$, which is only a ring: you can add, subtract and multiply, but not always divide, and RSA’s security leans on that gap. AES works inside $\mathrm{GF}(2^8)$, a field, where every nonzero element has a multiplicative inverse, and the AES S-box is built from exactly that inverse (04-07 covers the construction). Diffie-Hellman and the discrete logarithm problem live inside a cyclic group under multiplication. Whether a structure guarantees an inverse for every element is the difference between a scheme that works and one that silently breaks on certain inputs. This page builds the hierarchy from the ground up so those guarantees can be checked rather than assumed.

A group is a set $G$ with a binary operation, written $+$ here, satisfying four properties:

1. Closure. For all $a, b \in G$, $a + b \in G$.
2. Associativity. For all $a, b, c \in G$, $(a + b) + c = a + (b + c)$.
3. Identity element. There exists $0 \in G$ such that $0 + a = a + 0 = a$ for every $a$.
4. Inverse elements. For every $a \in G$, there exists $-a \in G$ with $a + (-a) = (-a) + a = 0$.

The operation does not have to be literal addition. It can be multiplication, or any binary operation meeting these four requirements. When the operation is also commutative ($a + b = b + a$ for all $a, b$), the group is an abelian group, also called a commutative group.

Try it — worked example

Show that the integers Z under addition form an abelian group.

Show answer and steps

AnswerZ is an abelian group under addition

1. Closure. $3, 5 \in \mathbb{Z}$ and $3 + 5 = 8 \in \mathbb{Z}$.
2. Associativity. $(2 + 3) + 4 = 5 + 4 = 9$ and $2 + (3 + 4) = 2 + 7 = 9$. Equal.
3. Identity. $0$ is the additive identity: $7 + 0 = 7$ and $0 + 7 = 7$.
4. Inverse. For $a = 5$, the inverse is $-5$, since $5 + (-5) = 0$.
5. Commutativity. $4 + 6 = 10$ and $6 + 4 = 10$. Equal.
6. All five properties hold, so $(\mathbb{Z}, +)$ is an abelian group.

A ring adds multiplication, and a field also guarantees a multiplicative inverse

A ring adds a second operation, multiplication, on top of the additive group structure:

1. Closure. $a + b$ and $a \cdot b$ are both in the set, for all $a, b$.
2. Associativity. $(a+b)+c = a+(b+c)$ and $(a \cdot b) \cdot c = a \cdot (b \cdot c)$.
3. Additive identity. $a + 0 = a$ for all $a$.
4. Additive inverse. For every $a$, there is $-a$ with $a + (-a) = 0$.
5. Commutativity of addition. $a + b = b + a$.
6. Distributive laws. $a \cdot (b + c) = a \cdot b + a \cdot c$ and $(a+b) \cdot c = a \cdot c + b \cdot c$.

A ring does not require multiplication to be commutative ($a \cdot b = b \cdot a$ can fail), and it does not require a multiplicative identity. $\mathbb{Z}$ satisfies all six properties, so $\mathbb{Z}$ is a ring.

A commutative ring is a ring with one more property:

7. Commutativity of multiplication. $a \cdot b = b \cdot a$ for all $a, b$.

$\mathbb{Z}$ satisfies this too, so $\mathbb{Z}$ is a commutative ring. A ring with a multiplicative identity (an element $1$ with $a \cdot 1 = a$) is called a ring with unity. An integral domain is a commutative ring with unity that has no zero divisors: $a \cdot b = 0$ forces $a = 0$ or $b = 0$. $\mathbb{Z}$ is an integral domain. The supplement names the term without a separate proof; it sits strictly between commutative ring and field.

A field adds the strongest requirement of all, a multiplicative inverse for every nonzero element:

8. Multiplicative inverse. For every $a \neq 0$, there exists $a^{-1}$ with $a \cdot a^{-1} = 1$.

A field is a commutative ring with unity where that eighth property also holds, supporting addition, subtraction, multiplication, and division by anything except zero.

Compare

Z (the integers)

Satisfies every field axiom except the last. Take $a = 4$: its multiplicative inverse would have to be $\frac{1}{4}$, since $4 \times \frac{1}{4} = 1$, but $\frac{1}{4} \notin \mathbb{Z}$. No integer inverse exists for $4$, so $\mathbb{Z}$ is not a field, only a commutative ring.

Q (the rationals)

The same check succeeds: $4$‘s inverse is $\frac{1}{4}$, and $\frac{1}{4} \in \mathbb{Q}$. Every nonzero rational has a rational inverse (flip the fraction), so $\mathbb{Q}$ satisfies all eight field axioms and is a field.

Exam detail

One counter-example is enough to disqualify a structure from being a field: the multiplicative-inverse axiom is universal (“for every nonzero element”), so a single element without an inverse breaks it. Both counter-examples on this page have this shape: one missing inverse for $4$ rules out $\mathbb{Z}$, and one missing inverse for $2$ rules out $\mathbb{Z}_8$ below.

Z_p is a field because p is prime

A prime field, written $F_p$ or $\mathrm{GF}(p)$, is the set $\{0, 1, \ldots, p-1\}$ with addition and multiplication taken modulo a prime $p$. The lecture works through $F_7 = \mathrm{GF}(7) = \{0,1,2,3,4,5,6\}$, checking every field axiom directly against numeric examples.

Try it — worked example

Show that F7 = {0, ..., 6} with addition and multiplication mod 7 is a field.

Show answer and steps

AnswerF7 satisfies all eight field axioms

1. Closure. $5, 6 \in F_7$: $5 + 6 \bmod 7 = 4 \in F_7$, and $5 \cdot 6 \bmod 7 = 30 \bmod 7 = 2 \in F_7$.
2. Associativity (addition). $(5+6)+4 \bmod 7$: $5+6=11 \bmod 7=4$; $4+4=8 \bmod 7=1$. $5+(6+4) \bmod 7$: $6+4=10 \bmod 7=3$; $5+3=8 \bmod 7=1$. Both equal $1$.
3. Associativity (multiplication). $(5 \cdot 6) \cdot 4 \bmod 7$: $5 \cdot 6=30 \bmod 7=2$; $2 \cdot 4=8 \bmod 7=1$. $5 \cdot (6 \cdot 4) \bmod 7$: $6 \cdot 4=24 \bmod 7=3$; $5 \cdot 3=15 \bmod 7=1$. Both equal $1$.
4. Additive identity. $0, 5 \in F_7$: $5 + 0 \bmod 7 = 5$.
5. Additive inverse. $5 + 2 \bmod 7 = 7 \bmod 7 = 0$, so $2$ is the additive inverse of $5$. Likewise $4 + 3 \bmod 7 = 7 \bmod 7 = 0$, so $3$ is the additive inverse of $4$.
6. Commutativity of addition. $5 + 2 \bmod 7 = 0$ and $2 + 5 \bmod 7 = 0$. Equal.
7. Distributive laws. $5(2+4) \bmod 7$: $2+4=6$; $5 \cdot 6=30 \bmod 7=2$. $5 \cdot 2 + 5 \cdot 4 \bmod 7$: $10 \bmod 7=3$, $20 \bmod 7=6$, $3+6=9 \bmod 7=2$. Both equal $2$.
8. Commutativity of multiplication. $5 \cdot 2 \bmod 7 = 10 \bmod 7 = 3$ and $2 \cdot 5 \bmod 7 = 10 \bmod 7 = 3$. Equal.
9. Multiplicative inverse. $5 \cdot 3 \bmod 7 = 15 \bmod 7 = 1$, so $3$ is the multiplicative inverse of $5$. And $6 \cdot 6 \bmod 7 = 36 \bmod 7 = 1$, so $6$ is its own inverse.
10. All eight axioms hold for every element checked, so $F_7$ is a field.

Finding an inverse by testing every element of $F_7$, as the last step does for $5$ and $6$, works at this size. For a larger prime it does not. That is the job of the extended Euclidean algorithm on extended Euclid and modular inverses, which computes a modular inverse directly rather than by search.

Z_8 is only a commutative ring, because 2 has no inverse mod 8

A prime field is only a field because $p$ is prime. The general set $\mathbb{Z}_n = \{0, 1, \ldots, n-1\}$ under addition and multiplication modulo $n$ is always a commutative ring, but it is only a field when $n$ is prime. $\mathbb{Z}_8$ makes the gap concrete: $8$ is not prime, and $2$ has no multiplicative inverse mod $8$.

Try it — worked example

Is Z8 a field? If not, find an element with no multiplicative inverse.

Show answer and steps

AnswerZ8 is a commutative ring, not a field, because 2 has no multiplicative inverse mod 8

Checking every possible inverse for $2$ by scanning $\mathbb{Z}_8 = \{0, 1, \ldots, 7\}$:

1. $2 \times 0 \bmod 8 = 0$
2. $2 \times 1 \bmod 8 = 2$
3. $2 \times 2 \bmod 8 = 4$
4. $2 \times 3 \bmod 8 = 6$
5. $2 \times 4 \bmod 8 = 0$
6. $2 \times 5 \bmod 8 = 2$
7. $2 \times 6 \bmod 8 = 4$
8. $2 \times 7 \bmod 8 = 6$
9. Every product is even, and $1$ is odd, so none of these ever equals $1$. $2$ has no multiplicative inverse in $\mathbb{Z}_8$, so $\mathbb{Z}_8$ is not a field. It is a commutative ring only.

Pitfall

The Week 4 abstract-algebra supplement prints row $3$ above as $2 \times 2 \bmod 8 = 0$. That is wrong: $2 \times 2 = 4$, and 04-02 flags the same slip. The conclusion is unaffected, since neither $4$ nor $0$ is $1$, but if this table is reproduced from the source, the printed $0$ in that one row is the error.

Exam detail

The reason $2$ fails and, say, $3$ would not: a multiplicative inverse for $a$ mod $n$ exists exactly when $\gcd(a, n) = 1$, the same condition 04-03 establishes for modular inverses in general. $\gcd(2, 8) = 2 \neq 1$, so $2$ is disqualified before any scanning is needed. This is also why $\mathbb{Z}_n$ is a field precisely when $n$ is prime: for a prime modulus, every nonzero element is automatically coprime to it, so every nonzero element has an inverse. For $\mathrm{GF}(2^n)$, where the underlying set is polynomials rather than the integers mod $n$, 04-07 builds the fix.

Recall

A set satisfies every ring axiom, is commutative under multiplication, and has a multiplicative identity. Is it necessarily a field?

No. That description is a commutative ring with unity, possibly an integral domain if it also has no zero divisors, but a field requires one more property: every nonzero element must have a multiplicative inverse. $\mathbb{Z}_8$ satisfies everything up to and including commutativity of multiplication and has a multiplicative identity ($1$), yet is not a field, because $2$ has no inverse mod $8$.