3.9 Groups, rings and fields: a preview built from what you know

Take the axiom idea of 2.1 and apply it to a single operation, and you get a group. Cosets give Lagrange's theorem, that the size of a subgroup divides the size of the group. A second operation gives a ring, and a ring in which every non-zero element can be divided by is a field, such as the integers mod a prime. Fields are the scalars that vector spaces always needed.

Chapter 2.1 asked what rules addition and scaling must obey for linear algebra to work, and answered with ten axioms. Here is the same question for one operation at a time. The integers under $+$ , the non-zero reals under $\times$ , the rotations of a plane under “do one, then the other”, the invertible matrices under multiplication and the permutations of a list under composition are different objects with one shared shape: two elements combine to give a third, there is an element that does nothing, and every element can be undone. The list of rules that captures this shape is called a group. This chapter is a preview of the first weeks of MATH 541, built from things you already know. It defines groups, proves one theorem with real content (Lagrange’s), looks at maps between groups, then adds a second operation to reach rings, and division to reach fields: the number systems from which vector spaces always secretly drew their scalars.

Before you start

0.5 (inverses mod $n$ , Euclid and Bézout), 0.4 and 3.7 (cosets and partitions), and 2.5 (matrix multiplication). Three quick checks.

Quick checkWhich of

4

5

3

has an inverse mod

10

Quick checkIn

\mathbb R^2

let

U

be the

x

-axis. Which coset equals

(2, 3) + U

Quick checkFor

A = \begin{bmatrix}1&1\\0&1\end{bmatrix}

and

B = \begin{bmatrix}1&0\\1&1\end{bmatrix}

, is

AB = BA

The picture

Here is the addition table of the integers mod $4$ : the entry in row $a$ and column $b$ is $a + b \bmod 4$ .

$+$	0	1	2	3
0	0	1	2	3
1	1	2	3	0
2	2	3	0	1
3	3	0	1	2

Now think of the four rotations of a square that map it to itself, by $0^\circ, 90^\circ, 180^\circ, 270^\circ$ , with ” $a$ then $b$ ” as the operation. Rotating by $90^\circ$ and then $180^\circ$ gives $270^\circ$ , in the same way that $1 + 2 = 3$ . Or take the four complex numbers $1, i, -1, -i$ under multiplication: $i \cdot (-1) = -i$ , matching $1 + 2 = 3$ again once you read $k$ as $i^k$ . Three different objects (remainders, rotations, complex numbers), one table, up to renaming. That sameness of structure is what a group captures.

Here is a second table with four elements: the multiplication table of $\{1, 3, 5, 7\}$ mod $8$ .

$\times$ mod 8	1	3	5	7
1	1	3	5	7
3	3	1	7	5
5	5	7	1	3
7	7	5	3	1

Both tables share a feature. Every row and every column contains every element exactly once, which says that you can always solve " $a \ast x = b$ " for $x$ in exactly one way: every move can be undone. But the tables have different structure. In the second, every element multiplied by itself gives $1$ (the diagonal is all $1$ s). In the first, $1 + 1 = 2 \ne 0$ . Same size, different groups. The rest of the chapter says exactly what “the same structure” means, and what follows from a few rules.

Where this came from· Lagrange, Galois and Cayley: from equations to groups

Joseph-Louis Lagrange (memoir of 1770–71) asked why the formulas for cubic and quartic equations work, and why nobody could find one for the quintic. He studied how many different values an expression in the roots takes when the roots are permuted, and stated that for $n$ roots this number always divides $n!$ . That is the seed of the theorem that carries his name; the statement for subgroups of an abstract group, and its proof by cosets, came later. Évariste Galois, around 1830 to 1832, attached to each equation the group of permutations of its roots and showed that solvability by radicals is a property of that group. He died in a duel in 1832 at the age of twenty, and Joseph Liouville published his papers in 1846. Arthur Cayley, in 1854, was among the first to define an abstract group: a set with a multiplication table obeying the rules, whatever its elements are. That is the definition below.

The idea, in words

Why· A group is a family of reversible moves

In 2.1 you listed the properties that all vector spaces share, and theorems proved from the list held everywhere at once. A group is the same move for one operation. Think of each element as a move that changes something: a rotation, a swap of two cards, adding $3$ on a clock. Two moves in a row make a move (the operation). Doing nothing is a move (the identity). Every move can be reversed (inverses). And the order in which three moves are grouped does not change what happens overall (associativity). Nothing is said about whether doing $a$ then $b$ equals doing $b$ then $a$ , because for rotations of a cube and shuffles of a deck it does not.

These four rules are enough to prove that the identity is unique, that every move has exactly one reverse, that you can cancel, and that every equation $ax = b$ has exactly one solution. They also give a counting theorem, Lagrange’s, which restricts what groups of a given size can contain.

Groups

Definition B

Group

A group is a set $G$ together with an operation $\ast$ , a rule that takes any two elements $a, b \in G$ to an element $a \ast b$ that is again in $G$ (so $G$ is closed under the operation), such that:

Associative. $(a \ast b) \ast c = a \ast (b \ast c)$ for all $a, b, c \in G$ .
Identity. There is an element $e \in G$ with $e \ast a = a \ast e = a$ for all $a \in G$ .
Inverses. For every $a \in G$ there is $a^{-1} \in G$ with $a \ast a^{-1} = a^{-1} \ast a = e$ .

We usually drop the symbol and write $ab$ . In additive groups we write $a + b$ , the identity $0$ and the inverse $-a$ . The number of elements of $G$ is its order $\lvert G\rvert$ ; it may be infinite.

In one lineA set G with an operation that combines any two elements into one, such that: the operation is associative, there is an identity element, and every element has an inverse.

Why it existsIt is the minimal list of rules for a set of reversible moves, and it covers numbers, matrices, permutations and symmetries at once.

Definition B

Abelian group

A group is abelian (after Niels Henrik Abel) if $ab = ba$ for all $a, b \in G$ . A vector space $(V, +)$ is an abelian group: the axioms of 2.1 that mention only addition (closure, associativity, commutativity, the zero vector, negatives) are exactly the abelian group axioms. The scalar-multiplication axioms are extra.

In one lineA group in which ab = ba for all a and b.

Why it existsMost number systems are abelian, but symmetry groups and matrix groups are not, and the difference shapes every theorem.

Here are the examples you already know, each with its identity and inverse.

Group	Elements	Operation	Identity	Inverse of $a$	Abelian?
$(\mathbb Z, +)$	integers	addition	$0$	$-a$	yes
$(\mathbb R \setminus \{0\}, \times)$	non-zero reals	multiplication	$1$	$1/a$	yes
$(\mathbb Z_n, +)$	residue classes mod $n$ (0.5)	addition	$[0]$	$[-a]$	yes
$(\mathbb Z_n^{\times}, \times)$	classes with $\gcd(a, n) = 1$ (0.5)	multiplication	$[1]$	$a^{-1}$ mod $n$	yes
$\mathrm{GL}_n(\mathbb R)$	invertible $n \times n$ matrices	matrix product	$I$	$A^{-1}$	no, for $n \ge 2$
$\mathrm{SO}(2)$ , $\mathrm{SO}(3)$	rotation matrices (3.3)	matrix product	$I$	$Q^{\mathsf T}$	$\mathrm{SO}(2)$ yes, $\mathrm{SO}(3)$ no
$S_n$	permutations of $\{1, \dots, n\}$ (2.7)	composition	the identity map	the inverse function	no, for $n \ge 3$

Why each is a group. For $\mathrm{GL}_n$ , the product of invertible matrices is invertible, since $(AB)^{-1} = B^{-1}A^{-1}$ (2.4); matrix multiplication is associative (2.5); $I$ is the identity; inverses exist by definition. For $\mathrm{SO}(n)$ , the orthogonal matrices with determinant $1$ (3.3): if $P^{\mathsf T}P = I$ and $Q^{\mathsf T}Q = I$ then $(PQ)^{\mathsf T}(PQ) = Q^{\mathsf T}P^{\mathsf T}PQ = Q^{\mathsf T}Q = I$ and $\det(PQ) = \det P\det Q = 1$ ; the inverse of $Q$ is $Q^{\mathsf T}$ , also orthogonal with determinant $1$ . For $S_n$ , a composition of bijections is a bijection, composition of functions is associative, and a bijection has an inverse function (0.3). For $\mathbb Z_n^\times$ , 0.5 shows that arithmetic respects congruence, that a product of invertible classes is invertible, and that $\gcd(a, n) = 1$ is exactly the condition for an inverse. The group $S_3$ has $3! = 6$ elements and is the smallest non-abelian group.

Quick checkWhich of these is a group?

Worked example

Which of these are groups? (a)

(\{1, 3, 5, 7\}, \times \bmod 8)

(b)

(\mathbb Z_6\setminus\{0\}, \times \bmod 6)

(c)

(\mathbb Z, -)

(d)

(\mathbb Q_{>0}, \times)

Solution.

(a) Closure, identity, inverses. The table in the picture has only entries from $\{1, 3, 5, 7\}$ , so the set is closed. The identity is $1$ . Every row contains a $1$ , so every element has an inverse (in fact each is its own inverse). Associativity holds because it holds for ordinary multiplication. A finite table lets us check closure and inverses by looking.
(b) Closure fails. $[2] \cdot [3] = [6] = [0]$ , which is not in the set. The set is not closed. Also $[2]$ has no inverse, since $\gcd(2, 6) = 2$ . Either failure is enough.
(c) Associativity fails. $(5 - 3) - 1 = 1$ but $5 - (3 - 1) = 3$ . A single instance that breaks an axiom disproves it. There is also no identity: $a - e = a$ forces $e = 0$ , but $e - a = a$ would need $a = 0$ .
(d) Positive rationals. The product and the quotient of positive rationals are positive rationals, $1$ is the identity, and the inverse of $p/q$ is $q/p$ . Associativity is that of multiplication. All three conditions hold, so it is a group (abelian).

Answer. (a) and (d) are groups; (b) and (c) are not.

What the rules force

Exactly as in 2.1, where the axioms gave unique zero vectors and unique negatives, the four group rules already give several facts that hold in every group.

Theorem B standard; Judson and Dummit and Foote, the opening group chapters

Consequences of the group axioms

Let $G$ be a group and $a, b, c \in G$ .

The identity $e$ is unique.
The inverse of $a$ is unique.
$(ab)^{-1} = b^{-1}a^{-1}$ .
If $ab = ac$ then $b = c$ . If $ba = ca$ then $b = c$ .
The equation $ax = b$ has exactly one solution, $x = a^{-1}b$ .

In one lineIn any group: the identity is unique; each element has exactly one inverse; (ab)⁻¹ = b⁻¹a⁻¹; ab = ac implies b = c (and ba = ca implies b = c); and ax = b has the unique solution x = a⁻¹b.

Why it is trueEach fact is the proof of the matching fact in 2.1 (unique zero vector, unique negative), written for a non-commutative operation. The key is to multiply by an inverse on the correct side.

Proofstandard

The idea: Each statement is proved by writing the element in two ways and using associativity. The most important idea: to undo an element, multiply by its inverse, on the same side.

e = ee' = e'

. The identity is unique.

(1) If

e

and

e'

are both identities, compute

ee'

in two ways. As

e'

is an identity,

ee' = e

. As

e

is an identity,

ee' = e'

b = be = b(ac) = (ba)c = ec = c

. The inverse is unique.

(2) Suppose

b

and

c

are both inverses of

a

, so

ab = ba = e

and

ac = ca = e

. Use

b = be

, then

e = ac

, then associativity, then

ba = e

(ab)(b^{-1}a^{-1}) = a(bb^{-1})a^{-1} = aea^{-1} = aa^{-1} = e

, and in the same way

(b^{-1}a^{-1})(ab) = e

(3) The inverse is unique by (2), so it is enough to show that

b^{-1}a^{-1}

behaves as an inverse of

ab

on both sides.

(ab)^{-1} = b^{-1}a^{-1}

Order is reversed, as when you take off shoes and socks: undo the last move first. Compare the rule

(AB)^{-1} = B^{-1}A^{-1}

for matrices, which is the case

G = \mathrm{GL}_n

b = (a^{-1}a)b = a^{-1}(ab) = a^{-1}(ac) = (a^{-1}a)c = c

. The case

ba = ca

is the same with multiplication on the right.

(4) Multiply

ab = ac

on the left by

a^{-1}

and use associativity.

a(a^{-1}b) = (aa^{-1})b = b

, so

x = a^{-1}b

works; if

ax = b

then

x = a^{-1}(ax) = a^{-1}b

(5) Existence: substitute. Uniqueness: multiply

ax = b

on the left by

a^{-1}

\blacksquare

Quick checkIn a group, which of these is always equal to

(ab)^{-1}

Worked example

\mathrm{GL}_2(\mathbb R)

with

A = \begin{bmatrix}1&1\\0&1\end{bmatrix}

and

B = \begin{bmatrix}1&0\\1&1\end{bmatrix}

, show that

AB \ne BA

and that

(AB)^{-1} = B^{-1}A^{-1}

but not

A^{-1}B^{-1}

. Then show that

S_3

is non-abelian.

Solution.

Multiply both ways. $AB = \begin{bmatrix}2&1\\1&1\end{bmatrix}$ and $BA = \begin{bmatrix}1&1\\1&2\end{bmatrix}$ . Row times column. The two products differ, so $\mathrm{GL}_2$ is not abelian.
Inverses of the factors. $A^{-1} = \begin{bmatrix}1&-1\\0&1\end{bmatrix}$ and $B^{-1} = \begin{bmatrix}1&0\\-1&1\end{bmatrix}$ . Undo the shear: use the $2\times2$ inverse formula from 2.5, with determinant $1$ .
Inverse of the product. $\det(AB) = 1$ , so $(AB)^{-1} = \begin{bmatrix}1&-1\\-1&2\end{bmatrix}$ . The $2\times2$ inverse formula applied to $AB$ .
Compare with the two candidates. $B^{-1}A^{-1} = \begin{bmatrix}1&0\\-1&1\end{bmatrix}\begin{bmatrix}1&-1\\0&1\end{bmatrix} = \begin{bmatrix}1&-1\\-1&2\end{bmatrix}$ , which is $(AB)^{-1}$ . But $A^{-1}B^{-1} = \begin{bmatrix}2&-1\\-1&1\end{bmatrix}$ is not. The reversed order is the correct one.
$S_3$ . Write a permutation as the list $(\sigma(1), \sigma(2), \sigma(3))$ and compose as $(\sigma\circ\tau)(i) = \sigma(\tau(i))$ . Let $\sigma = (2, 1, 3)$ (swap $1, 2$ ) and $\tau = (1, 3, 2)$ (swap $2, 3$ ). Then $\sigma\circ\tau = (2, 3, 1)$ , since $1 \mapsto 1 \mapsto 2$ , $2 \mapsto 3 \mapsto 3$ , $3 \mapsto 2 \mapsto 1$ . And $\tau\circ\sigma = (3, 1, 2)$ , since $1 \mapsto 2 \mapsto 3$ , $2 \mapsto 1 \mapsto 1$ , $3 \mapsto 3 \mapsto 2$ . The two compositions differ: swapping cards 1,2 then 2,3 gives a different arrangement from swapping 2,3 then 1,2.

Answer. $\mathrm{GL}_2(\mathbb R)$ and $S_3$ are non-abelian, and $(AB)^{-1} = B^{-1}A^{-1}$ with the order reversed.

Subgroups and orders of elements

Definition B

Subgroup

A subset $H$ of a group $G$ is a subgroup, written $H \le G$ , if $H$ is a group under the operation of $G$ : it contains the identity of $G$ , it is closed under the operation, and it contains $h^{-1}$ for every $h \in H$ . Examples: $n\mathbb Z \le \mathbb Z$ (the multiples of $n$ ); the four rotations by multiples of $90^\circ$ in $\mathrm{SO}(2)$ ; $\mathrm{SL}_n(\mathbb R) \le \mathrm{GL}_n(\mathbb R)$ , the matrices of determinant $1$ . Non-examples: the odd integers (no $0$ , and not closed under $+$ ), $\mathbb N \subset \mathbb Z$ (no negatives), and $\{0, 1, \dots, n-1\}$ is not a subgroup of $\mathbb Z$ (not closed under addition: the group $\mathbb Z_n$ is not a part of $\mathbb Z$ ).

In one lineA subset H of a group G that is itself a group under the same operation.

Why it existsSubgroups are the parts of a group that are closed under combining and undoing, and Lagrange's theorem is about their sizes.

Proposition B standard; Judson, the group chapters

Subgroup test

Let $H$ be a non-empty subset of a group $G$ . If $ab^{-1} \in H$ for all $a, b \in H$ , then $H \le G$ .

In one lineA non-empty subset H of a group G is a subgroup as soon as ab⁻¹ is in H whenever a and b are in H.

Why it is trueTaking a = b gives the identity, then b = identity gives inverses, then replacing b by its inverse gives products. The associative law is inherited from G.

Proofstandard

The idea: Use the one condition three times, with well-chosen elements, to get identity, inverses, and closure.

e = aa^{-1} \in H

H

is non-empty, so pick some

a \in H

. Apply the condition to

a

and

a

b^{-1} = eb^{-1} \in H

Apply the condition to

e

and

b

, for any

b \in H

ab = a(b^{-1})^{-1} \in H

, so

H

is closed under the operation.

Apply the condition to

a

and

b^{-1}

(which is in

H

by the last step), using

(b^{-1})^{-1} = b

H

is a group.

Associativity holds for all elements of

G

, so for those in

H

\blacksquare

Worked example

Which are subgroups of

\mathrm{GL}_2(\mathbb R)

: (a)

H_1 = \{A : \det A = 1\}

, (b)

H_2 = \{A : \det A = \pm1\}

, (c)

H_3 = \{A : \det A = 2\}

? Also: is

E = \{\ldots, -4, -2, 0, 2, 4, \ldots\}

a subgroup of

(\mathbb Z, +)

Solution.

(a) Apply the subgroup test. $H_1$ is not empty ( $I$ ). If $\det A = \det B = 1$ then $\det(AB^{-1}) = \det A \cdot (\det B)^{-1} = 1$ . The product rule for determinants (2.7) and $\det B^{-1} = 1/\det B$ .
(b) Same. If $\det A, \det B \in \{1, -1\}$ then $\det(AB^{-1}) = \det A/\det B \in \{1, -1\}$ . A quotient of two numbers each equal to $\pm1$ is $\pm1$ .
(c) Fails. $I$ has determinant $1 \ne 2$ , so $I \notin H_3$ . A subgroup contains the identity. (Also $\det(AB) = 4 \ne 2$ for $A, B \in H_3$ : not closed.)
The even integers. The condition becomes $a - b \in E$ for $a, b \in E$ (additive notation), and the difference of two even numbers is even. In additive notation $ab^{-1}$ reads $a + (-b) = a - b$ .

Answer. $H_1$ and $H_2$ are subgroups; $H_3$ is not; $E \le \mathbb Z$ .

Definition B

Order of an element

For $g \in G$ write $g^k = g \cdots g$ ( $k$ factors), $g^0 = e$ and $g^{-k} = (g^{-1})^k$ . The order of $g$ , $\operatorname{ord}(g)$ , is the smallest $k \ge 1$ such that $g^k = e$ . In an additive group the condition is $g + \dots + g = k\cdot g = 0$ . The subgroup generated by $g$ is $\langle g\rangle = \{g^m : m \in \mathbb Z\}$ . A group $G$ is cyclic if $G = \langle g\rangle$ for some $g$ , which is then called a generator.

In one lineThe order of g is the smallest k ≥ 1 with gᵏ = e (in additive notation k·g = 0), or infinity if there is none.

Why it existsIt measures how many steps it takes to come back to the start by repeating one move, and it is the size of the subgroup generated by g.

Theorem B standard; Judson, the cyclic groups chapter

A repeated move has as many positions as its order

If $\operatorname{ord}(g) = k < \infty$ , then $\langle g\rangle$ is a subgroup of $G$ with exactly $k$ elements, namely $e, g, \dots, g^{k-1}$ , and $g^m = e \iff k \mid m$ .

In one lineIf g has finite order k then ⟨g⟩ = {e, g, g², …, g^(k−1)} has exactly k elements, and gᵐ = e exactly when k divides m.

Why it is trueDividing m by k with remainder (0.5) reduces every power to one of the first k, and the first k are all different by the minimality of k.

Proofstandard

The idea: Use the division algorithm on the exponent. This reduces every power g^m to g^r with r between 0 and k − 1, and then show that no two of these are equal.

Take any integer

m

and write

m = qk + r

with

0 \le r < k

Division algorithm (0.5):

m = qk + r

with

0 \le r < k

(the quotient

q

may be negative).

g^m = (g^k)^q g^r = e^q g^r = g^r

Exponent rules in a group, and

g^k = e

Hence

g^m = e

iff

r = 0

iff

k \mid m

So every element of

\langle g\rangle

is one of

e, g, \dots, g^{k-1}

. Also

g^m = e

iff

g^r = e

, and

r < k

with

k

the least positive exponent forces

r = 0

Then

g^{j-i} = e

with

0 < j - i < k

Suppose

g^i = g^j

with

0 \le i < j < k

. Multiply both sides by

g^{-i}

(cancellation).

e, g, \dots, g^{k-1}

are all different, and

\lvert\langle g\rangle\rvert = k

This contradicts

k

being the smallest positive exponent with

g^k = e

\langle g\rangle

is a subgroup.

\langle g\rangle

contains

e = g^0

, is closed since

g^ag^b = g^{a+b}

, and contains

g^{-a}

as the inverse of

g^a

\blacksquare

Worked example

List the order of every element of

(\mathbb Z_{12}, +)

and the subgroup each element generates.

Solution.

Order of $a$ . The order is the least $k \ge 1$ with $ka \equiv 0 \pmod{12}$ , which is $12/\gcd(a, 12)$ . Put $g = \gcd(a, 12)$ . Then $12 \mid ka$ means $\frac{12}{g} \mid k\cdot\frac ag$ , and $\frac{12}{g}$ and $\frac ag$ are coprime, so $\frac{12}{g} \mid k$ (the coprime-divisor fact of 0.5, a consequence of Bézout). The smallest such $k$ is $\frac{12}{g}$ .
Table of orders. $a = 0, 1, 2, \dots, 11$ have orders $1, 12, 6, 4, 3, 12, 2, 12, 3, 4, 6, 12$ . For instance $a = 8$ : $\gcd(8, 12) = 4$ , so the order is $3$ (indeed $8 + 8 + 8 = 24 \equiv 0$ and $8 + 8 = 16 \equiv 4 \ne 0$ ).
The subgroups $\langle a\rangle$ . $\{0\}$ , $\{0, 6\}$ , $\{0, 4, 8\}$ , $\{0, 3, 6, 9\}$ , $\{0, 2, 4, 6, 8, 10\}$ and $\mathbb Z_{12}$ . Generated by $a = 0, 6, 4, 3, 2, 1$ . Other generators repeat these sets: $\langle 8\rangle = \langle 4\rangle$ and $\langle 5\rangle = \langle 1\rangle$ .
Sizes. $1, 2, 3, 4, 6, 12$ . Exactly the divisors of $12$ . This is no accident: it is Lagrange’s theorem below.

Answer. Orders as in step 2. The subgroups generated by single elements are the six listed, with sizes the six divisors of $12$ (they are in fact all the subgroups of $\mathbb Z_{12}$ , a fact proved in 541).

Your answerWhat is the order of

8

(\mathbb Z_{12}, +)

Lagrange’s theorem

Look back at the list of subgroup sizes of $\mathbb Z_{12}$ : $1, 2, 3, 4, 6, 12$ . Every size divides the order $12$ . This holds in every finite group, and the reason is the idea of 3.7: a subgroup chops the group into equal-sized parallel pieces.

For a subgroup $H \le G$ and $g \in G$ , the left coset of $g$ is $gH = \{gh : h \in H\}$ . In an additive group it is $g + H = \{g + h : h \in H\}$ . When $G$ is a vector space and $H$ is a subspace, this is exactly the coset $v + U$ of 3.7: $U$ moved by $v$ . The index $[G : H]$ is the number of distinct left cosets.

Take $H = \{0, 4, 8\}$ in $\mathbb Z_{12}$ . Its cosets are $H$ , $1 + H = \{1, 5, 9\}$ , $2 + H = \{2, 6, 10\}$ and $3 + H = \{3, 7, 11\}$ : four pieces of size $3$ that cover the twelve elements with no overlaps. $12 = 4 \times 3$ . For a non-abelian example, take $G = S_3$ and $H = \{e, \sigma\}$ with $\sigma = (2, 1, 3)$ . The left cosets $gH = \{g, g\circ\sigma\}$ are $\{(1,2,3), (2,1,3)\}$ , $\{(1,3,2), (3,1,2)\}$ and $\{(2,3,1), (3,2,1)\}$ : three pieces of size $2$ , and $6 = 3 \times 2$ . The right cosets $Hg = \{g, \sigma\circ g\}$ are $\{(1,2,3), (2,1,3)\}$ , $\{(1,3,2), (2,3,1)\}$ and $\{(3,1,2), (3,2,1)\}$ . They are also three pieces of size $2$ , but they are different sets from the left cosets, so in a non-abelian group the side matters. This is the entry point to normal subgroups in 541.

Theorem B Judson, the cosets and Lagrange chapter; Dummit and Foote

Lagrange's theorem

Let $G$ be a finite group and $H \le G$ . Then $\lvert H\rvert$ divides $\lvert G\rvert$ , and $\lvert G\rvert = [G:H]\cdot\lvert H\rvert$ .

In one lineIf H is a subgroup of a finite group G, then the order of H divides the order of G: |G| = [G : H] · |H|.

Why it is trueThe left cosets of H partition G (they are the classes of an equivalence relation, 0.4) and each has exactly |H| elements, so |G| is the number of cosets times |H|.

ProofJudson, the cosets and Lagrange chapter

The idea: Define a ~ b to mean a⁻¹b is in H. It is an equivalence relation whose classes are the cosets aH, so cosets partition G. Each coset has |H| elements because h ↦ ah is a bijection from H onto aH. Count.

The relation

\sim

is reflexive.

Relation:

a \sim b

iff

a^{-1}b \in H

. Reflexive:

a^{-1}a = e \in H

The relation

\sim

is symmetric.

Symmetric: if

a^{-1}b \in H

then its inverse

(a^{-1}b)^{-1} = b^{-1}a \in H

, because a subgroup contains inverses.

The relation

\sim

is transitive. So it is an equivalence relation.

Transitive: if

a^{-1}b \in H

and

b^{-1}c \in H

then the product

(a^{-1}b)(b^{-1}c) = a^{-1}c \in H

, because a subgroup is closed under products.

The class of

a

aH

The class of

a

\{b : a^{-1}b \in H\}

. If

a^{-1}b = h \in H

then

b = ah

; conversely

b = ah

gives

a^{-1}b = h \in H

. This is the same step as in the cosets theorem of 3.7.

So the distinct left cosets are disjoint and their union is

G

Classes of an equivalence relation partition the set (0.4): any two classes are equal or disjoint, and every element lies in one.

Every coset

aH

has exactly

\lvert H\rvert

elements.

The map

H \to aH

h \mapsto ah

, is onto by the definition of

aH

. It is one-to-one by cancellation:

ah = ah'

implies

h = h'

(consequences of the axioms, part 4).

\lvert G\rvert = [G:H]\cdot\lvert H\rvert

, so

\lvert H\rvert

divides

\lvert G\rvert

Counting a disjoint union: add up the sizes of the pieces. There are

[G:H]

pieces, each of size

\lvert H\rvert

\blacksquare

Why· The picture behind the proof

In the plane with $G = \mathbb R^2$ and $H$ a line through $O$ , the cosets are the parallel lines. Each line is a translate of $H$ , so every line looks the same, and the lines tile the plane with no overlaps. Lagrange’s theorem is that picture for a finite group: the cosets tile $G$ , each a translated copy of $H$ . For $\mathbb Z_{12}$ and $H = \{0, 4, 8\}$ the “lines” are the four triples listed above. The same picture, with $V$ and a subspace $U$ , gave $\dim V/U = \dim V - \dim U$ in 3.7: for vector spaces the count of cosets is not a number but a dimension.

Proof workshopRebuild: Lagrange's theoremJudson, the cosets and Lagrange chapter

Tap the lines in the order a proof would write them. Each line can only use what is already above it.

Quick checkA group has

21

elements. Which of these could be the size of a subgroup?

Corollary B Judson, the cosets and Lagrange chapter

Consequences of Lagrange's theorem

Let $G$ be a finite group of order $N$ .

For every $g \in G$ , $\operatorname{ord}(g)$ divides $N$ , and $g^N = e$ .
If $N = p$ is prime, every $g \ne e$ generates $G$ .
(Euler.) If $\gcd(a, n) = 1$ then $a^{\varphi(n)} \equiv 1 \pmod n$ , where $\varphi(n)$ is the number of integers from $1$ to $n$ coprime to $n$ . (Fermat.) If $p$ is prime and $p \nmid a$ then $a^{p-1} \equiv 1 \pmod p$ .

In one lineIn a finite group G: the order of every element divides |G|, so g^|G| = e; a group of prime order p is cyclic; and, for the group of invertible classes mod n, a^φ(n) ≡ 1 (Euler), in particular a^(p−1) ≡ 1 for prime p (Fermat).

Why it is trueThe cyclic subgroup generated by g has ord(g) elements, so Lagrange applies to it. In Z_n^× the group has φ(n) elements.

Proofstandard

The idea: Apply Lagrange to the subgroup generated by one element, and read off the three consequences.

(1)

\operatorname{ord}(g)

divides

N

The subgroup

\langle g\rangle

has exactly

\operatorname{ord}(g)

elements (the repeated-move theorem), and Lagrange's theorem applies to it.

g^N = (g^{\operatorname{ord}(g)})^k = e

Write

N = k\cdot\operatorname{ord}(g)

and use

g^{\operatorname{ord}(g)} = e

Then

\langle g\rangle

has

p

elements, so

\langle g\rangle = G

(2) If

g \ne e

then

\operatorname{ord}(g) > 1

and divides the prime

p

, so

\operatorname{ord}(g) = p

The classes coprime to

n

form a group of order

\varphi(n)

(3)

\mathbb Z_n^\times

, the classes

[a]

with

\gcd(a, n) = 1

under multiplication, is a group of order

\varphi(n)

(the table above and 0.5).

[a]^{\varphi(n)} = [1]

, which says

a^{\varphi(n)} \equiv 1 \pmod n

Apply part 1 to the class

[a]

With

n = p

a^{p-1} \equiv 1 \pmod p

For

n = p

prime,

\varphi(p) = p - 1

, because every integer from

1

p-1

is coprime to

p

\blacksquare

0.5 proved Fermat’s little theorem by a separate argument, the shuffle of $a, 2a, \dots, (p-1)a$ . Lagrange gives a second proof. The two are the same idea in different clothes: multiplying every element of the group by $a$ is a one-to-one rearrangement of the group, in the same way that multiplying by $g$ moves a subgroup to a coset of equal size.

Worked example

Find all element orders in

\mathbb Z_{15}^\times

and check that they divide the group order. Use this to compute

7^{222} \bmod 15

Solution.

The group. $\mathbb Z_{15}^\times = \{1, 2, 4, 7, 8, 11, 13, 14\}$ (the numbers coprime to $15$ ), so $\varphi(15) = 8$ . Remove multiples of $3$ and $5$ from $1, \dots, 14$ .
Compute orders. $2$ : $2, 4, 8, 1$ , order $4$ . $4$ : $4, 16 \equiv 1$ , order $2$ . $7$ : $7, 49 \equiv 4, 28 \equiv 13, 91 \equiv 1$ , order $4$ . $8$ : $8, 64 \equiv 4, 32 \equiv 2, 16 \equiv 1$ , order $4$ . $11$ : $11, 121 \equiv 1$ , order $2$ . $13$ : $13, 169 \equiv 4, 52 \equiv 7, 91 \equiv 1$ , order $4$ . $14$ : $14, 196 \equiv 1$ , order $2$ . Multiply repeatedly mod $15$ until $1$ appears.
Check Lagrange. Orders $1, 2, 4$ all divide $8$ . No element has order $8$ , so the group is not cyclic. If it were cyclic, a generator would have order $8$ . Compare $\mathbb Z_7^\times$ , where $3$ has order $6$ : $3, 2, 6, 4, 5, 1$ .
Use it. $\operatorname{ord}(7) = 4$ , and $222 = 4 \cdot 55 + 2$ , so $7^{222} = (7^4)^{55}\cdot 7^2 \equiv 7^2 = 49 \equiv 4 \pmod{15}$ . The repeated-move theorem: powers repeat with period $\operatorname{ord}(7) = 4$ . (Euler would also allow exponent reduction mod $8$ , but the true period is $4$ .)

Answer. Orders: $1,2,4,7,8,11,13,14$ have orders $1,4,2,4,4,2,4,2$ . And $7^{222} \equiv 4 \pmod{15}$ .

Your answerHow many elements does the group

\mathbb Z_{20}^\times

of invertible classes mod

20

have?

Your answerA group has

60

elements and a subgroup

H

of order

12

. How many left cosets of

H

are there?

Your answerUse Lagrange to compute

4^{101} \bmod 13

(a number from

0

12

Watch out· The converse of Lagrange is false

If $d$ divides $\lvert G\rvert$ there need not be a subgroup of order $d$ . The group $A_4$ of the $12$ even permutations of $\{1,2,3,4\}$ has no subgroup of order $6$ , although $6 \mid 12$ (checked by listing all subgroups: their orders are $1, 2, 3, 4, 12$ ). A partial converse holds: if a prime $p$ divides $\lvert G\rvert$ then there is a subgroup of order $p$ (Cauchy’s theorem), and a subgroup of order $p^k$ for the largest power of $p$ dividing $\lvert G\rvert$ (Sylow). These are MATH 541 theorems.

Python labFind every subgroup by brute force and watch Lagrange hold

from itertools import permutations, combinations

def compose(s, t):                       # (s o t)(i) = s(t(i))
    return tuple(s[t[i]] for i in range(len(t)))

def closure(gens, e):                    # smallest set holding e and gens, closed under products
    S = {e} | set(gens)
    while True:
        new = {compose(a, b) for a in S for b in S} | S
        if new == S:
            return frozenset(S)
        S = new

def sign(p):                             # (-1)^(number of inversions)
    return (-1) ** sum(p[i] > p[j] for i in range(len(p)) for j in range(i + 1, len(p)))

def subgroup_sizes(G, e):                # these small groups need at most 2 generators
    subs = {closure(g, e) for r in range(3) for g in combinations(G, r)}
    return sorted(len(H) for H in subs)

S3 = list(permutations(range(3)))
A4 = [p for p in permutations(range(4)) if sign(p) == 1]
print("S3:", subgroup_sizes(S3, (0, 1, 2)))
print("A4:", subgroup_sizes(A4, (0, 1, 2, 3)))

Try this. Run it. S3 should show sizes 1, 2, 2, 2, 3, 6 and A4 sizes 1, 2, 2, 2, 3, 3, 3, 3, 4, 12: every size divides the group order, and A4 has no subgroup of size 6 although 6 divides 12. Next add S4 = list(permutations(range(4))) and print subgroup_sizes(S4, (0, 1, 2, 3)): you should see the sizes 1, 2, 3, 4, 6, 8, 12 and 24 appear, 30 subgroups in all.

Homomorphisms

A linear map is a function that respects addition and scaling. For groups, the structure is one operation, so we ask for a function that respects it.

Definition B

Homomorphism

A homomorphism from a group $G$ to a group $H$ is a function $\varphi: G \to H$ such that $\varphi(ab) = \varphi(a)\varphi(b)$ for all $a, b \in G$ (the product on the left is in $G$ , on the right in $H$ ). The kernel of $\varphi$ is the set $\ker\varphi = \{g \in G : \varphi(g) = e_H\}$ of elements sent to the identity of $H$ . It is the null space of 2.3, in group language: a linear map $T$ is a homomorphism of the groups $(V, +) \to (W, +)$ , and $N(T) = \ker T$ . A bijective homomorphism is an isomorphism; groups with an isomorphism between them have the same structure.

In one lineA function φ: G → H between groups with φ(ab) = φ(a)φ(b): doing the operation before or after φ gives the same result.

Why it existsIt is a structure-respecting map for groups, as a linear map is for vector spaces; kernels and images of homomorphisms are the main tools in group theory.

Examples:

A linear map $T: V \to W$ is a homomorphism $(V,+) \to (W,+)$ , since $T(v + w) = T(v) + T(w)$ .
$\det: \mathrm{GL}_n(\mathbb R) \to (\mathbb R\setminus\{0\}, \times)$ . It is a homomorphism by the product rule $\det(AB) = \det A\det B$ (2.7). Its kernel is $\mathrm{SL}_n(\mathbb R)$ , the matrices of determinant $1$ .
$\exp: (\mathbb R, +) \to (\mathbb R_{>0}, \times)$ , since $e^{a+b} = e^ae^b$ . Its kernel is $\{0\}$ , and it is bijective with inverse $\ln$ , so it is an isomorphism: addition of exponents is multiplication of numbers, which is what a slide rule did.
Reduction mod $n$ : $\mathbb Z \to \mathbb Z_n$ , $a \mapsto [a]$ . By 0.5 it respects $+$ . Its kernel is $n\mathbb Z$ .
$\theta \mapsto R_\theta$ from $(\mathbb R, +)$ to $\mathrm{SO}(2)$ , since $R_\theta R_\varphi = R_{\theta+\varphi}$ (the angle-addition formulas). Its kernel is $\{2\pi k\}$ .
$k \mapsto i^k$ from $(\mathbb Z_4, +)$ to $(\{1, i, -1, -i\}, \times)$ : an isomorphism, the renaming in the picture.

Proposition B standard

Homomorphisms preserve identity and inverses

Let $\varphi: G \to H$ be a homomorphism. Then (a) $\varphi(e_G) = e_H$ ; (b) $\varphi(a^{-1}) = \varphi(a)^{-1}$ ; (c) $\ker\varphi \le G$ and the image $\varphi(G) \le H$ ; (d) $\varphi$ is one-to-one iff $\ker\varphi = \{e_G\}$ .

In one lineA homomorphism sends the identity to the identity and inverses to inverses: φ(e) = e and φ(a⁻¹) = φ(a)⁻¹. Its kernel is a subgroup, and φ is one-to-one iff the kernel contains only the identity.

Why it is trueApply φ to e·e = e and cancel; apply it to a·a⁻¹ = e. The kernel claim is the same argument as 'T is one-to-one iff N(T) = {O}' from 2.3.

Proofstandard

The idea: (a) and (b) by applying φ to an identity in G and cancelling in H. (c) by the subgroup test. (d): φ(a) = φ(b) says φ(ab⁻¹) = e.

Cancel one factor

\varphi(e_G)

on the left (cancellation in

H

e_H = \varphi(e_G)

(a)

e_G = e_Ge_G

, so

\varphi(e_G) = \varphi(e_G)\varphi(e_G)

\varphi(a^{-1})

is the inverse of

\varphi(a)

(b)

\varphi(a)\varphi(a^{-1}) = \varphi(aa^{-1}) = \varphi(e_G) = e_H

. The inverse is unique (consequences of the axioms).

\ker\varphi

and

\varphi(G)

are subgroups.

(c)

e_G \in \ker\varphi

by (a). For

a, b \in \ker\varphi

\varphi(ab^{-1}) = \varphi(a)\varphi(b)^{-1} = e_He_H^{-1} = e_H

, by (b). Subgroup test. The image:

\varphi(a)\varphi(b)^{-1} = \varphi(ab^{-1})

is in the image.

(

\Rightarrow

) the kernel contains only

e_G

(d) If

\varphi

is one-to-one and

a \in \ker\varphi

, then

\varphi(a) = e_H = \varphi(e_G)

, so

a = e_G

(

\Leftarrow

)

\varphi

is one-to-one.

(

\Leftarrow

) If

\varphi(a) = \varphi(b)

then

\varphi(ab^{-1}) = \varphi(a)\varphi(b)^{-1} = e_H

, so

ab^{-1} \in \ker\varphi = \{e_G\}

and

a = b

\blacksquare

Worked example

Check that

\det

is a homomorphism on the matrices

M = \begin{bmatrix}1&2\\3&4\end{bmatrix}

and

N = \begin{bmatrix}0&1\\1&1\end{bmatrix}

, and describe the kernel. Then show

\mathbb Z_4

and the group

\{1,3,5,7\}

mod 8 are not isomorphic.

Solution.

Determinants. $\det M = 4 - 6 = -2$ and $\det N = 0 - 1 = -1$ . The $2\times2$ formula $ad - bc$ .
The product. $MN = \begin{bmatrix}2&3\\4&7\end{bmatrix}$ and $\det(MN) = 14 - 12 = 2 = (-2)(-1)$ . The homomorphism property $\det(MN) = \det M\cdot\det N$ for these matrices.
The kernel. $\ker\det = \{A : \det A = 1\} = \mathrm{SL}_2(\mathbb R)$ , a subgroup by the proposition. The identity of $(\mathbb R\setminus\{0\}, \times)$ is $1$ , not $0$ . The kernel is the set sent to the identity.
Not one-to-one. $\det$ sends both $I$ and $\begin{bmatrix}1&1\\0&1\end{bmatrix}$ to $1$ , and the kernel is more than $\{I\}$ . Part (d): a larger kernel means not injective.
Non-isomorphic groups. An isomorphism $\varphi$ preserves orders of elements, since $\varphi(g)^k = \varphi(g^k)$ and $\varphi$ is one-to-one. In $\mathbb Z_4$ the element $1$ has order $4$ . In $\{1,3,5,7\}$ every element squares to $1$ , so every order is at most $2$ . The orders differ, so no bijective homomorphism exists, even though both groups have $4$ elements.

Answer. $\det$ is a homomorphism with kernel $\mathrm{SL}_2(\mathbb R)$ , and $\mathbb Z_4 \not\cong \{1,3,5,7\}$ .

Quick checkWhich of these is a homomorphism from

(\mathbb Z, +)

(\mathbb Z, +)

The sign of a permutation

In 2.7, the sign of a permutation was $+1$ or $-1$ and was used to build the determinant. It is actually a homomorphism, and that is why the determinant of a product works out.

Theorem B standard; 2.7

The sign is a homomorphism

For permutations $\sigma, \tau$ of $\{1, \dots, n\}$ , $\operatorname{sgn}(\tau\circ\sigma) = \operatorname{sgn}(\tau)\operatorname{sgn}(\sigma)$ (the sign as defined in 2.7). The kernel $A_n$ of $\operatorname{sgn}: S_n \to \{1, -1\}$ is the group of even permutations.

In one lineFor permutations σ and τ of {1,…,n}, sgn(τ∘σ) = sgn(τ)·sgn(σ). So sgn: Sₙ → ({1, −1}, ×) is a homomorphism, whose kernel is the group Aₙ of even permutations.

Why it is trueWrite σ as a permutation matrix. The determinant of that matrix is its sign (the permutation formula, 2.7), and permutation matrices multiply like permutations compose, so the product rule for determinants gives the result.

Proofstandard

The idea: Attach to each permutation σ the matrix P_σ with a 1 in position (i, σ(i)) of row i and 0 elsewhere. Then det P_σ = sgn σ and P_σ P_τ = P_{τ∘σ}. Take determinants.

For a permutation

\sigma

, let

P_\sigma

be the permutation matrix with

1

in row

i

, column

\sigma(i)

Define

P_\sigma

(P_\sigma)_{i,\sigma(i)} = 1

for each row

i

and all other entries

0

. It is a matrix with exactly one

1

in each row and column.

\det P_\sigma = \operatorname{sgn}(\sigma)

The permutation formula of 2.7:

\det A = \sum_\pi \operatorname{sgn}(\pi)\,a_{1\pi(1)}\cdots a_{n\pi(n)}

. For

P_\sigma

the product is

1

\pi = \sigma

and

0

for every other

\pi

(some factor

a_{i\pi(i)}

0

P_\sigma P_\tau = P_{\tau\circ\sigma}

Entry

(i, k)

P_\sigma P_\tau

\sum_j (P_\sigma)_{ij}(P_\tau)_{jk}

. Only

j = \sigma(i)

contributes, giving

(P_\tau)_{\sigma(i),k}

, which is

1

exactly when

k = \tau(\sigma(i))

\operatorname{sgn}(\tau\circ\sigma) = \det(P_\sigma P_\tau) = \det P_\sigma\det P_\tau = \operatorname{sgn}(\sigma)\operatorname{sgn}(\tau)

\blacksquare

Take determinants of

P_\sigma P_\tau = P_{\tau\circ\sigma}

and use the product rule for determinants (2.7) on the left.

For example, in $S_3$ the permutation $\sigma = (2, 3, 1)$ has two inversions (sign $+1$ ), $\tau = (3, 2, 1)$ has three (sign $-1$ ), and $\sigma\circ\tau = (1, 3, 2)$ has one inversion (sign $-1$ ). Indeed $(+1)(-1) = -1$ . A transposition has sign $-1$ , so $\operatorname{sgn}$ is onto $\{1, -1\}$ , and by Lagrange the kernel $A_n$ has half the elements of $S_n$ : $\lvert A_n\rvert = n!/2$ (Problem below). For $S_4$ that is $12$ , the group $A_4$ of the warning above.

A preview· Preview: the first isomorphism theorem for groups

In 3.7 the first isomorphism theorem said $V/N(T) \cong \operatorname{range}T$ . For groups the same theorem holds: $G/\ker\varphi \cong \operatorname{im}\varphi$ . To state it you need a group structure on the cosets of the kernel. In an abelian group $(g + K) + (h + K) = (g + h) + K$ works exactly as in 3.7, and the proof of well-definedness is the same. In a non-abelian group, left and right cosets can differ (we saw this in $S_3$ ), and the construction needs the subgroup to be normal ( $gKg^{-1} = K$ for all $g$ ). Kernels are always normal: if $k \in \ker\varphi$ then $\varphi(gkg^{-1}) = \varphi(g)\,e\,\varphi(g)^{-1} = e$ (Problem below). That is the full story of MATH 541’s first chapters. The example you have already seen: $\mathbb Z/n\mathbb Z$ , the quotient of the group $\mathbb Z$ by the subgroup $n\mathbb Z$ , is the group $(\mathbb Z_n, +)$ of 0.5.

Rings

Groups have one operation. Number systems have two, linked by the distributive law. We write the rules once.

Definition B

Ring

A ring is a set $R$ with two operations, addition and multiplication, such that:

$(R, +)$ is an abelian group, with identity $0$ and negatives $-a$ .
Multiplication is associative, and there is an element $1$ with $1a = a1 = a$ .
Distributive laws: $a(b + c) = ab + ac$ and $(a + b)c = ac + bc$ .

The ring is commutative if $ab = ba$ for all $a, b$ .

In one lineA set with addition and multiplication where addition makes it an abelian group, multiplication is associative with an identity 1, and multiplication distributes over addition.

Why it existsIt is the minimal setting for 'adding and multiplying', and it covers the integers, residues mod n, polynomials and square matrices at once.

Examples: $\mathbb Z$ ; $\mathbb Z_n$ (0.5 shows that addition and multiplication of classes are well defined); $\mathbb Q$ , $\mathbb R$ , $\mathbb C$ (0.6); the polynomials with real coefficients $\mathbb R[x]$ (0.6); and the $n \times n$ real matrices $M_n(\mathbb R)$ , which are a ring that is not commutative. Non-example: $\mathbb N$ (no negatives, so $(\mathbb N, +)$ is not a group). Warning on conventions: many textbooks do not require the identity $1$ , and some require commutativity; this book follows the convention above, with $1$ and not necessarily commutative.

Two ring-theoretic ideas matter below. A unit is an element with a multiplicative inverse; the units of $\mathbb Z_n$ are the classes of 0.5 with $\gcd(a, n) = 1$ , the group $\mathbb Z_n^\times$ . A zero divisor is a non-zero $a$ for which $ab = 0$ for some non-zero $b$ : in $\mathbb Z_6$ , $[2][3] = [0]$ ; in $M_2(\mathbb R)$ , $\begin{bmatrix}0&1\\0&0\end{bmatrix}^2 = 0$ .

Proposition B standard

Zero times anything in a ring

In any ring, $0\cdot a = 0$ and $(-1)\cdot a = -a$ for every $a$ .

In one lineIn any ring, 0·a = 0 and (−1)·a = −a.

Why it is trueIt is the ring version of 'scaling by zero' in 2.1: the distributive law applied to 0 = 0 + 0, then cancel in the additive group.

Proofstandard

The idea: Use the distributive law on 0 = 0 + 0 and cancel in the additive group. For the second part show (−1)a is the additive inverse of a.

0a = (0 + 0)a = 0a + 0a

0 = 0 + 0

, and the distributive law.

0a = 0

Add

-(0a)

to both sides; cancellation in the group

(R, +)

(part 4 of the consequences).

(-1)a

is an additive inverse of

a

, and by uniqueness of inverses

(-1)a = -a

\blacksquare

a + (-1)a = 1a + (-1)a = (1 + (-1))a = 0a = 0

, by the distributive law and the first part.

Fields

Definition B

Field

A field is a commutative ring $F$ in which $1 \ne 0$ and every non-zero element $a$ has an inverse $a^{-1}$ with $aa^{-1} = 1$ . Equivalently: $(F, +)$ and $(F\setminus\{0\}, \times)$ are both abelian groups and the distributive law links them. Examples: $\mathbb Q$ , $\mathbb R$ , $\mathbb C$ , and $\mathbb Z_p$ for $p$ prime. Non-examples: $\mathbb Z$ (the number $2$ has no inverse in $\mathbb Z$ ), $\mathbb R[x]$ (the polynomial $x$ has no inverse), $M_2(\mathbb R)$ (not commutative, and it has zero divisors), and $\mathbb Z_6$ .

In one lineA commutative ring where 1 ≠ 0 and every non-zero element has a multiplicative inverse: a number system where you can add, subtract, multiply and divide by anything non-zero.

Why it existsDivision is what linear algebra needs: scaling a vector by 1/c, dividing by a pivot in elimination, and normalising a vector all divide by a scalar.

Lemma B standard

A field has no zero divisors

If $F$ is a field and $ab = 0$ in $F$ , then $a = 0$ or $b = 0$ .

In one lineIn a field, ab = 0 implies a = 0 or b = 0.

Why it is trueIf a ≠ 0, multiply ab = 0 by a⁻¹.

Proofstandard

The idea: Suppose a is not zero, and show that b is.

Suppose

a \ne 0

Proof by cases (0.2): either

a = 0

, done, or

a \ne 0

b = (a^{-1}a)b = a^{-1}(ab) = a^{-1}\cdot 0 = 0

\blacksquare

a

has an inverse in a field. Multiply

ab = 0

a^{-1}

, and use associativity and

a^{-1}\cdot 0 = 0

(zero times anything).

Which of the rings $\mathbb Z_n$ are fields? The picture of 0.5 (the multiplication tables mod $7$ and mod $6$ ) already shows the answer.

Theorem B standard; Judson, the fields chapter; 0.5

Z_n is a field exactly when n is prime

Let $n \ge 2$ . The ring $\mathbb Z_n$ is a field if and only if $n$ is prime.

In one lineFor n ≥ 2, the ring Zₙ of integers mod n is a field if and only if n is prime.

Why it is trueDivision mod n needs an inverse for every non-zero class, and Bézout (0.5) says a has an inverse iff gcd(a, n) = 1. That holds for all a from 1 to n − 1 exactly when n has no divisors other than 1 and n.

ProofJudson, the fields chapter

The idea: (⇐) For prime n, Bézout gives an inverse of every non-zero class. (⇒) If n = ab is composite, the classes [a] and [b] are non-zero but multiply to [0], so Zₙ has zero divisors and cannot be a field.

Let

n = p

be prime. It remains to find inverses.

(

\Leftarrow

)

\mathbb Z_n

is a commutative ring with

[1] \ne [0]

since

n \ge 2

(0.5: addition and multiplication of classes are well defined and obey the usual laws).

\gcd(a, p) = 1

Take

[a] \ne [0]

with

1 \le a \le p - 1

. Then

p \nmid a

. The only positive divisors of

p

are

1

and

p

, and

\gcd(a, p)

is one of them, not

p

[a]

has an inverse in

\mathbb Z_p

, and

\mathbb Z_p

is a field.

Inverses mod

n

exist exactly when the gcd is

1

(0.5, from Bézout's identity

ax + py = 1

Then

[a] \ne [0]

and

[b] \ne [0]

, because

0 < a, b < n

(

\Rightarrow

) Contrapositive. Suppose

n

is not prime, so

n = ab

with

1 < a, b < n

But their product is

[0]

, so

[a]

is a zero divisor.

[a][b] = [ab] = [n] = [0]

\mathbb Z_n

is not a field.

A field has no zero divisors (the lemma above).

\blacksquare

Proof workshopRebuild: Z_n is a field iff n is primeJudson, the fields chapter

Tap the lines in the order a proof would write them. Each line can only use what is already above it.

Quick checkWhich of these rings is a field?

Worked example

\mathbb Z_9

a field? Is

\mathbb Z_{11}

? Solve

7x \equiv 3 \pmod{11}

if you can.

Solution.

$\mathbb Z_9$ . $9 = 3 \cdot 3$ is composite, and $[3][3] = [9] = [0]$ with $[3] \ne [0]$ . A zero divisor, so $\mathbb Z_9$ is not a field. In particular $[3]$ has no inverse mod $9$ .
$\mathbb Z_{11}$ . $11$ is prime, so $\mathbb Z_{11}$ is a field. The theorem.
The inverse of $7$ . Euclid: $11 = 1\cdot7 + 4$ , $7 = 1\cdot4 + 3$ , $4 = 1\cdot3 + 1$ . Back-substitute: $1 = 4 - 3 = 4 - (7 - 4) = 2\cdot4 - 7 = 2(11 - 7) - 7 = 2\cdot11 - 3\cdot7$ . So $7^{-1} \equiv -3 \equiv 8 \pmod{11}$ . The extended Euclid of 0.5. Check: $7 \cdot 8 = 56 = 5 \cdot 11 + 1$ .
Solve. $x \equiv 8 \cdot 3 = 24 \equiv 2 \pmod{11}$ . In a field, $ax = b$ has the unique solution $x = a^{-1}b$ , exactly as in a group.
Check. $7 \cdot 2 = 14 = 11 + 3$ . The answer must reproduce the right side.

Answer. $\mathbb Z_9$ is not a field, $\mathbb Z_{11}$ is, and $x \equiv 2 \pmod{11}$ .

Worked example

Build a field with

4

elements, and check that it is a field.

$\mathbb Z_4$ is not a field ( $[2][2] = [0]$ ), so a field with $4$ elements cannot be the integers mod $4$ . The same idea as $\mathbb Z_p$ works with polynomials in place of integers: take polynomials over $\mathbb Z_2$ (coefficients $0$ or $1$ , with $1 + 1 = 0$ ) and replace $x^2$ by $x + 1$ , the remainder rule of dividing by the polynomial $x^2 + x + 1$ .

Solution.

The elements. $\{0, 1, x, x + 1\}$ : every polynomial reduces to one of the form $a + bx$ with $a, b \in \{0, 1\}$ . Divide by $x^2 + x + 1$ and keep the remainder, a polynomial of degree less than $2$ . The same remainder idea as $\mathbb Z_n$ in 0.5.
The rule for $x^2$ . In $\mathbb Z_2$ , $-1 = 1$ , so $x^2 + x + 1 = 0$ gives $x^2 = x + 1$ . We declare the polynomial $x^2 + x + 1$ to be $0$ , as we declared $n$ to be $0$ in $\mathbb Z_n$ .
Products. $x\cdot x = x^2 = x + 1$ . $x(x + 1) = x^2 + x = (x + 1) + x = 2x + 1 = 1$ . $(x + 1)(x + 1) = x^2 + 2x + 1 = x^2 + 1 = (x + 1) + 1 = x$ . Expand, use $x^2 = x + 1$ , and $2 = 0$ .
Inverses. $1^{-1} = 1$ , $x^{-1} = x + 1$ (since $x(x+1) = 1$ ), $(x+1)^{-1} = x$ . Every non-zero element has an inverse, so we have a field.
Why not zero divisors. $x^2 + x + 1$ has no root in $\mathbb Z_2$ ( $0 \mapsto 1$ and $1 \mapsto 1$ ), so it cannot be split into factors of degree $1$ . This is the same reason as for primes: $\mathbb Z_p$ is a field because $p$ cannot be split. Here the polynomial cannot be split.

Answer. The field $\mathbb F_4 = \{0, 1, x, x+1\}$ (the “Galois field” $\mathrm{GF}(4)$ ). Its non-zero elements form the group $\{1, x, x+1\}$ of order $3$ , with $x^2 = x+1$ and $x^3 = 1$ . In the same way $\mathrm{GF}(256)$ is $\mathbb Z_2[x]$ modulo the degree- $8$ polynomial $x^8 + x^4 + x^3 + x^2 + 1$ ; its elements are the 256 possible bytes. QR codes use it (below).

Why· Why vector spaces need a field of scalars

Everything in 2.1 to 2.7 and the dual and quotient constructions of 3.7 work with scalars from any field: replace “real number” by “element of $F$ ” and nothing in the proofs changes. They all divide by scalars. Normalising $cv = O$ to $v = O$ needs $c^{-1}$ . Elimination divides by pivots. The theorem “more vectors than a spanning set means dependent” solves for one vector by dividing by a coefficient. What goes wrong over a ring that is not a field? Let $\mathbb Z$ act as scalars on $\mathbb Z_6$ ( $k\cdot[a] = [ka]$ ). Then $2\cdot[3] = [0]$ although the scalar $2$ and the vector $[3]$ are both non-zero: the consequence ” $cv = O$ forces $c = 0$ or $v = O$ ” of 2.1 fails. Every single vector is dependent ( $6\cdot[a] = [0]$ with $6 \ne 0$ ), so there is no basis and no dimension. Over a field this cannot happen.

With a finite field the counting becomes exact. $\mathbb Z_2^3$ over $\mathbb Z_2$ has dimension $3$ and exactly $2^3 = 8$ vectors; a vector space of dimension $d$ over a field with $q$ elements has $q^d$ vectors. The invertible $2\times2$ matrices over $\mathbb Z_p$ (a group, $\mathrm{GL}_2(\mathbb Z_p)$ ) number $(p^2 - 1)(p^2 - p)$ : the first column is any non-zero vector, the second any vector not a multiple of the first (2.2). For $p = 2$ that is $6$ , and for $p = 3$ it is $48$ .

Where this came from· Kummer, Dedekind and Galois: rings and fields

In the mid-1840s Ernst Kummer found that unique factorization into primes can fail in rings of numbers built from roots of unity, and repaired it with “ideal numbers”, which he used to prove Fermat’s last theorem for every exponent that is a “regular” prime (a large class, but not all primes). The preview of 0.5, where $6 = 2\cdot3 = (1+\sqrt{-5})(1-\sqrt{-5})$ , is the same phenomenon. Richard Dedekind replaced Kummer’s ideal numbers by ideals, in a supplement to Dirichlet’s lectures on number theory (1871), and used the word Körper (body, our “field”) for a set of numbers closed under addition, subtraction, multiplication and division. In the 1890s David Hilbert introduced the word Zahlring (number ring), the origin of our word “ring”. Galois, in a note of 1830, had already built the finite fields with $p^n$ elements by adding “imaginary” roots of polynomial congruences to $\mathbb Z_p$ , which is why they are called Galois fields and written $\mathrm{GF}(p^n)$ . The problem behind all of it was the same: when can you divide, and when can you factor in only one way.

Where it is used

Used inside maths· Inside maths: where 541 goes from here

Lagrange’s theorem is the first of the counting results in group theory: Cauchy and Sylow find subgroups of prescribed prime power order. Quotient groups $G/N$ (3.7’s quotient space for one operation) and the isomorphism theorems come next, then group actions, which count orbits, and then Galois theory, which turns the 1832 idea (each polynomial has a group, and solvability by radicals is a property of that group) into a correspondence between subgroups and intermediate fields. The group $\mathrm{GL}_n(F)$ and its subgroups, such as $\mathrm{SO}(3)$ , are the matrix groups of representation theory. Fields allow linear algebra over $\mathbb Z_p$ , which is what error-correcting codes and much of cryptography use. A concrete use of this chapter inside linear algebra: the order of a matrix. In $\mathrm{GL}_2(\mathbb Z_3)$ , which has $48$ elements, every matrix $A$ satisfies $A^{48} = I$ by Lagrange, so the powers $A^k$ cycle with a period dividing $48$ .

Used in the real world· Cryptography: Diffie–Hellman key exchange lives in a group

Alice and Bob want a shared secret over a public channel. They agree on a prime $p = 23$ and the element $g = 5$ of the group $\mathbb Z_{23}^\times$ (which has $22$ elements; $5$ has order $22$ , so it generates the group). Alice picks a secret $a = 6$ and sends $A = g^a$ ; Bob picks $b = 15$ and sends $B = g^b$ . Each then raises the other’s number to their own secret power.

With $p = 23$ an eavesdropper tries all $22$ exponents; the lab below does exactly that. With $p$ of about 2048 bits there are about $2^{2048}$ exponents, trying them all is hopeless, and the best known methods for the discrete logarithm in this group are still far too slow. Lagrange explains the exponents: $g^{p-1} = 1$ , so secrets only matter mod $p - 1$ (the trap in 0.5). Other groups serve the same purpose: elliptic-curve groups of about $256$ -bit order are used instead because no known attack on them is as fast as the best attacks on $\mathbb Z_p^\times$ . RSA uses the group $\mathbb Z_n^\times$ with $\varphi(n) = (p-1)(q-1)$ elements: for $m$ coprime to $n$ , $(m^e)^d = m^{1 + k\varphi(n)} = m\,(m^{\varphi(n)})^k = m$ by Lagrange, which is the correctness proof of 0.5 in one line (0.5 handles the case where $m$ shares a factor with $n$ separately). Diffie and Hellman published the key exchange in 1976.

Python labDiffie–Hellman with small numbers, and the eavesdropper's brute force

p, g = 23, 5
order = next(k for k in range(1, p) if pow(g, k, p) == 1)
print("order of g:", order)
a, b = 6, 15                              # the secrets
A, B = pow(g, a, p), pow(g, b, p)         # the public numbers
print("A =", A, "  B =", B)
print("Alice computes", pow(B, a, p), "  Bob computes", pow(A, b, p))
for k in range(1, p):                     # an eavesdropper tries every exponent
    if pow(g, k, p) == A:
        print("eavesdropper finds a =", k)
        break
print("exponents repeat mod the order:", pow(g, a + order, p) == A)

Try this. Run it: both parties should get 2, and the eavesdropper should find a = 6. Now set g = 2: its order drops to 11, a divisor of 22 as Lagrange demands, so only half of the non-zero classes are ever reached. Try g = 22 (order 2). The key still matches for every choice of a and b, but with a small order the eavesdropper has fewer exponents to try.

Used in the real world· Symmetry in physics and chemistry: crystal groups, molecules and conservation laws

The symmetries of an object form a group under “do one, then the other”. A methane molecule $\mathrm{CH}_4$ is a regular tetrahedron with a carbon at the centre. Its symmetry group, called $T_d$ in chemistry, has $24$ elements (rotations, reflections and rotation-reflections that map the molecule onto itself) and is isomorphic to $S_4$ : every permutation of the four hydrogen atoms is achieved by exactly one symmetry. The water molecule has a group of order $4$ : do nothing, rotate by $180^\circ$ about the axis through the oxygen, and two reflections. By Lagrange, any subgroup of the methane group has order dividing $24$ , so no subgroup has order $5$ . In crystallography every crystal pattern has a symmetry group: there are exactly $32$ crystallographic point groups, $230$ space groups in three dimensions and $17$ “wallpaper” groups in the plane. Chemists use these groups to predict which vibrations of a molecule absorb infrared light. In 1918 Emmy Noether proved that each continuous symmetry of a physical law gives a conserved quantity: the rotation group $\mathrm{SO}(3)$ gives conservation of angular momentum.

Used in the real world· Error-correcting codes: Reed–Solomon codes need a field, and QR codes use GF(256)

A QR code survives a torn corner because it stores more data than the message needs, arranged so that the message can be reconstructed. The codes used, Reed–Solomon codes (Irving Reed and Gustave Solomon, 1960), treat each byte as an element of $\mathrm{GF}(256)$ and the message as the coefficients of a polynomial. The smallest QR code (version 1, with the lowest error-correction level L) has $26$ bytes: $19$ carry the message and $7$ are check bytes. Each wrong byte at an unknown position costs two check bytes to repair, and the QR standard keeps $3$ check bytes in reserve for 1-L to catch a wrong decode, so this smallest code guarantees the repair of $\lfloor (7 - 3)/2\rfloor = 2$ wrong bytes. CDs use a Reed–Solomon scheme too. Here is the mechanism at a size that fits on a page, over the field $\mathbb Z_7$ .

In a ring such as $\mathbb Z_6$ this fails: $2x \equiv 0$ has the two roots $0$ and $3$ and $x_2 - x_1$ may be a zero divisor with no inverse. The general rule: $n$ symbols sent for $k$ message symbols let you correct up to $\lfloor (n-k)/2\rfloor$ wrong symbols, here $\lfloor 3/2\rfloor = 1$ .

Used in the real world· Rubik's cube: a group of 43 quintillion elements

The moves of the $3\times3\times3$ cube form a group: the operation is “do this sequence, then that one”, every move can be undone, and doing nothing is the identity. Its order is

\frac{8!\cdot 3^7\cdot 12!\cdot 2^{11}}{2} = 43\,252\,003\,274\,489\,856\,000 \approx 4.3\times10^{19}.

There are $8!$ ways to place the corner pieces and $3^7$ ways to twist them (the last twist is forced), $12!$ ways to place the edge pieces and $2^{11}$ ways to flip them (the last flip is forced), and the factor $\frac12$ because the parity of the corner permutation must equal that of the edge permutation: a cube with only two pieces swapped cannot be reached by turning faces. The group is not abelian: turning the right face then the top face differs from top then right. Each single face turn has order $4$ . Repeating any sequence of moves must bring the cube back to its start, after a number of repetitions that divides $\lvert G\rvert$ by Lagrange. In 2010 Rokicki, Kociemba, Davidson and Dethridge showed by computer that every position can be solved in at most $20$ moves, where a half turn of a face counts as one move. (If only quarter turns are allowed, the answer is $26$ .)

Traps

Watch out· Groups need not be commutative, and inverses reverse order

The axioms never say $ab = ba$ . In $\mathrm{GL}_2$ and $S_3$ it fails. Consequently $(ab)^{-1} = b^{-1}a^{-1}$ , not $a^{-1}b^{-1}$ , and an equation $ax = b$ is solved by $x = a^{-1}b$ , not $ba^{-1}$ . Multiply on the correct side.

Watch out· Lagrange's theorem does not run backwards

If $d$ divides $\lvert G\rvert$ , a subgroup of order $d$ may not exist ( $A_4$ has no subgroup of order $6$ ). Lagrange gives necessary conditions on sizes only. Also the order of an element divides $\lvert G\rvert$ but need not equal it: $\mathbb Z_{15}^\times$ has $8$ elements and none of order $8$ .

Watch out· Check that a subset uses the same operation, and that the identity is the right one

$\{0, 1, \dots, n-1\}$ is not a subgroup of $(\mathbb Z, +)$ (not closed). $\mathbb Z_n$ under multiplication is not a group (the class $[0]$ has no inverse, and non-coprime classes fail). The identity of $(\mathbb R\setminus\{0\}, \times)$ is $1$ , so the kernel of $\det$ is the matrices of determinant $1$ , not $0$ . “Kernel is trivial” means the kernel is the identity element alone.

Watch out· Z_n is a field only for prime n; GF(4) is not Z_4

A finite field with $4$ elements exists, but it is not the integers mod $4$ (that has the zero divisor $[2]$ ). Finite fields have $p^n$ elements, and for $n > 1$ they are built from polynomials, as in the worked example. Also check conventions: some books define a ring without $1$ , and a “domain” without zero divisors is a ring, not necessarily a field.

Problems

check

Decide which are groups: (a) $(\mathbb Z_5, \times)$ (b) $(\mathbb Z_5\setminus\{0\}, \times)$ (c) $(\mathbb Z, -)$ (d) $(\{1, -1, i, -i\}, \times)$ .

Solution

(a) No: $[0]$ has no inverse. (b) Yes: $5$ is prime, products of non-zero classes are non-zero, and every non-zero class has an inverse (0.5). (c) No: $-$ is not associative, $(3 - 2) - 1 = 0$ but $3 - (2 - 1) = 2$ . (d) Yes: it is the group $\{1, i, -1, -i\}$ of the picture, with $i\cdot(-i) = 1$ , $i\cdot i = -1$ and so on.

check

Find the order of $8$ in $(\mathbb Z_{12}, +)$ and of $3$ in $\mathbb Z_7^\times$ .

Solution

$8 + 8 = 16 \equiv 4$ , $8 + 8 + 8 = 24 \equiv 0$ , so $\operatorname{ord}(8) = 3$ (also $12/\gcd(8, 12) = 3$ ). In $\mathbb Z_7^\times$ : $3, 3^2 = 2, 3^3 = 6, 3^4 = 4, 3^5 = 5, 3^6 = 1$ , so $\operatorname{ord}(3) = 6$ , and $3$ generates the group.

check

A group has $18$ elements. Which of the orders $2, 4, 6, 7, 9$ are impossible for a subgroup, and which are allowed by Lagrange?

Solution

By Lagrange the order divides $18$ , whose divisors are $1, 2, 3, 6, 9, 18$ . So $4$ and $7$ are impossible. $2$ , $6$ and $9$ are allowed by Lagrange (whether they occur depends on the group).

check

Which of these is a homomorphism? (a) $\det: \mathrm{GL}_2(\mathbb R)\to(\mathbb R\setminus\{0\},\times)$ (b) $A \mapsto \operatorname{tr}A$ from $(\mathrm{GL}_2(\mathbb R), \times)$ to $(\mathbb R, +)$ (c) $x \mapsto 3x$ from $(\mathbb R, +)$ to $(\mathbb R, +)$ .

Solution

(a) Yes: $\det(AB) = \det A\det B$ . (c) Yes: $3(x + y) = 3x + 3y$ . (b) No: $\operatorname{tr}(AB) \ne \operatorname{tr}A + \operatorname{tr}B$ in general. Take $A = B = I$ : $\operatorname{tr}(I\cdot I) = 2$ but $\operatorname{tr}I + \operatorname{tr}I = 4$ .

use

In $S_3$ compute $\sigma\circ\tau$ and $\tau\circ\sigma$ for $\sigma = (2, 3, 1)$ and $\tau = (3, 2, 1)$ (lists of $\sigma(1), \sigma(2), \sigma(3)$ ), find $\sigma^{-1}$ , and the sign of each of $\sigma, \tau, \sigma\circ\tau$ .

Solution

$\sigma\circ\tau$ : $1 \mapsto 3 \mapsto 1$ , $2 \mapsto 2 \mapsto 3$ , $3 \mapsto 1 \mapsto 2$ , so $\sigma\circ\tau = (1, 3, 2)$ . $\tau\circ\sigma$ : $1 \mapsto 2 \mapsto 2$ , $2 \mapsto 3 \mapsto 1$ , $3 \mapsto 1 \mapsto 3$ , so $\tau\circ\sigma = (2, 1, 3)$ , a different permutation. $\sigma^{-1}$ sends $\sigma(i)$ back to $i$ : $2 \mapsto 1$ , $3 \mapsto 2$ , $1 \mapsto 3$ , so $\sigma^{-1} = (3, 1, 2)$ . Inversions: $\sigma$ has $2$ (sign $+1$ ), $\tau$ has $3$ (sign $-1$ ), $\sigma\circ\tau$ has $1$ (sign $-1$ ), and $(+1)(-1) = -1$ .

use

List the group $\mathbb Z_{15}^\times$ , find the order of $2$ and of $11$ , and compute $2^{1000} \bmod 15$ .

Solution

$\mathbb Z_{15}^\times = \{1, 2, 4, 7, 8, 11, 13, 14\}$ . Powers of $2$ : $2, 4, 8, 1$ , so $\operatorname{ord}(2) = 4$ . $11^2 = 121 = 8\cdot15 + 1$ , so $\operatorname{ord}(11) = 2$ . Since $\operatorname{ord}(2) = 4$ and $1000 = 4\cdot250$ , $2^{1000} = (2^4)^{250} \equiv 1$ .

use

In $\mathrm{GF}(4) = \{0, 1, x, x + 1\}$ with $x^2 = x + 1$ over $\mathbb Z_2$ , compute $(x + 1)^2$ , $(x+1)^{-1}$ , and solve $x\cdot y = x + 1$ .

Solution

$(x + 1)^2 = x^2 + 2x + 1 = x^2 + 1 = x + 1 + 1 = x$ . Since $x(x + 1) = x^2 + x = 1$ , $(x+1)^{-1} = x$ . For $xy = x + 1$ : $y = x^{-1}(x + 1) = (x + 1)(x + 1) = x$ (using $x^{-1} = x + 1$ ). Check: $x\cdot x = x + 1$ .

use

Is $\{A \in \mathrm{GL}_2(\mathbb R) : \det A = \pm1\}$ a subgroup? Is $\{A : \det A > 0\}$ ? Is $\{A : A \text{ has integer entries}\}$ ?

Solution

Use the subgroup test. $\det A = \pm1$ : if $\det A, \det B \in \{1, -1\}$ then $\det(AB^{-1}) = \det A/\det B \in \{1, -1\}$ : yes. $\det A > 0$ : $\det(AB^{-1}) = \det A/\det B > 0$ : yes. Integer entries: no. $A = \begin{bmatrix}2&0\\0&1\end{bmatrix}$ is in the set, but $A^{-1} = \begin{bmatrix}1/2&0\\0&1\end{bmatrix}$ is not, so the set is not closed under inverses.

prove

Prove that if $g^2 = e$ for every element $g$ of a group $G$ , then $G$ is abelian.

Solution

For every $g$ , $g^2 = e$ means $g = g^{-1}$ . Take $a, b \in G$ . Then $ab$ also satisfies $(ab)^2 = e$ , so $ab = (ab)^{-1} = b^{-1}a^{-1} = ba$ , using the inverse-of-a-product rule and then $a = a^{-1}$ , $b = b^{-1}$ . So $ab = ba$ .

prove

Prove that the intersection $H \cap K$ of two subgroups of $G$ is a subgroup. Give an example showing that the union of two subgroups need not be a subgroup.

Solution

$e \in H$ and $e \in K$ , so $H \cap K$ is non-empty. If $a, b \in H \cap K$ then $ab^{-1} \in H$ and $ab^{-1} \in K$ (each is a subgroup), so $ab^{-1} \in H \cap K$ . By the subgroup test, $H\cap K \le G$ . For the union: in $\mathbb Z$ take $H = 2\mathbb Z$ and $K = 3\mathbb Z$ . Then $2 \in H\cup K$ and $3 \in H\cup K$ , but $2 + 3 = 5$ is in neither, so $H\cup K$ is not closed.

prove

Let $\varphi: G\to H$ be a homomorphism. Prove that for every $g \in G$ and $k \in \ker\varphi$ , $gkg^{-1} \in \ker\varphi$ .

Solution

$\varphi(gkg^{-1}) = \varphi(g)\varphi(k)\varphi(g^{-1}) = \varphi(g)\,e_H\,\varphi(g)^{-1} = \varphi(g)\varphi(g)^{-1} = e_H$ . The first equality is the homomorphism property twice; then $\varphi(k) = e_H$ and $\varphi(g^{-1}) = \varphi(g)^{-1}$ (identities and inverses are preserved). So $gkg^{-1} \in \ker\varphi$ . This is the property called “normal” in 541, and it is what lets one form $G/\ker\varphi$ .

prove

Prove that a group of prime order $p$ has no subgroups except $\{e\}$ and itself, and is cyclic.

Solution

By Lagrange the order of a subgroup divides $p$ , so it is $1$ or $p$ : the subgroup is $\{e\}$ or all of $G$ . Take $g \ne e$ . The cyclic subgroup $\langle g\rangle$ contains $e$ and $g$ , so it has at least $2$ elements, hence $p$ elements, so $\langle g\rangle = G$ . A group generated by one element is cyclic.

prove

Prove that $\lvert A_n\rvert = n!/2$ for $n \ge 2$ , where $A_n$ is the set of even permutations in $S_n$ .

Solution

Let $O$ be the set of odd permutations, so $S_n$ is the disjoint union of $A_n$ and $O$ . Let $\tau$ be the transposition swapping $1$ and $2$ ; it has sign $-1$ . Define $f: A_n \to O$ by $f(\sigma) = \tau\circ\sigma$ . Its sign is $\operatorname{sgn}(\tau)\operatorname{sgn}(\sigma) = -1$ , so $f(\sigma) \in O$ (sign is a homomorphism). It is one-to-one by cancellation, and onto: if $\rho \in O$ then $\tau^{-1}\circ\rho = \tau\circ\rho$ has sign $(-1)(-1) = 1$ so lies in $A_n$ and $f(\tau\circ\rho) = \tau\circ\tau\circ\rho = \rho$ . So $\lvert A_n\rvert = \lvert O\rvert$ , and $\lvert A_n\rvert + \lvert O\rvert = n!$ gives $\lvert A_n\rvert = n!/2$ . (This is the statement that $A_n$ has index $2$ in $S_n$ .)

stretch

A finite commutative ring $R$ with $1 \ne 0$ and no zero divisors is a field. Prove it. Where does this explain the theorem on $\mathbb Z_n$ ?

Solution

Let $a \ne 0$ in $R$ and define $f: R\to R$ , $f(x) = ax$ . If $f(x) = f(y)$ then $a(x - y) = 0$ , and since $a \ne 0$ and there are no zero divisors, $x - y = 0$ . So $f$ is one-to-one. A one-to-one map from a finite set to itself is onto (pigeonhole, 0.3), so some $x$ has $ax = 1$ . Hence $a$ has an inverse, and $R$ is a field. For $\mathbb Z_p$ with $p$ prime: if $ab \equiv 0$ then $p \mid ab$ , so $p \mid a$ or $p \mid b$ by Euclid’s lemma (0.5), so $\mathbb Z_p$ has no zero divisors, and the result makes it a field without computing any Bézout coefficients.

stretch

Show that every group of order $4$ is isomorphic to $\mathbb Z_4$ or to the group $\{1, 3, 5, 7\}$ of the picture.

Solution

Let $\lvert G\rvert = 4$ . By Lagrange every element has order $1$ , $2$ or $4$ . If some $g$ has order $4$ , then $\langle g\rangle$ has $4$ elements, so $G = \langle g\rangle = \{e, g, g^2, g^3\}$ , and $g^k \mapsto k$ is an isomorphism with $\mathbb Z_4$ . Otherwise every element has order $1$ or $2$ , so $g^2 = e$ for all $g$ , and $G$ is abelian (earlier problem). Take non-identity $a \ne b$ . Then $ab \notin \{e, a, b\}$ : $ab = e$ would give $b = a^{-1} = a$ ; $ab = a$ gives $b = e$ ; $ab = b$ gives $a = e$ . So $G = \{e, a, b, ab\}$ , with $a^2 = b^2 = (ab)^2 = e$ and $ab = ba$ . These rules fix the whole table, and the map $e \mapsto 1$ , $a \mapsto 3$ , $b \mapsto 5$ , $ab \mapsto 7$ matches it with the mod- $8$ table ( $3\cdot5 = 15 \equiv 7$ ).

Summary

A group is a set with an associative operation, an identity and inverses: a family of reversible moves. Commutativity is not required ( $\mathrm{GL}_n$ , $S_n$ ). Consequences: unique identity and inverses, $(ab)^{-1} = b^{-1}a^{-1}$ , cancellation, and a unique solution of $ax = b$ .
A subgroup is a subset that is itself a group (test: $ab^{-1}$ stays inside). The order of an element is the size of the subgroup it generates.
Lagrange’s theorem: $\lvert H\rvert$ divides $\lvert G\rvert$ , because the cosets of $H$ partition $G$ into equal-sized pieces (0.4 and 3.7). Consequences: element orders divide $\lvert G\rvert$ , Fermat and Euler for $\mathbb Z_n^\times$ . The converse is false ( $A_4$ ).
A homomorphism respects the operation. Its kernel (the null space of 2.3, in group language) is a subgroup, and it is one-to-one iff the kernel is trivial. Examples: $\det$ with kernel $\mathrm{SL}_n$ , $\operatorname{sgn}$ with kernel $A_n$ , reduction mod $n$ .
A ring has $+$ (an abelian group) and $\times$ (associative, with $1$ ) linked by the distributive law; $\mathbb Z$ , $\mathbb Z_n$ , polynomials and matrices are rings.
A field is a commutative ring where every non-zero element has an inverse. $\mathbb Z_n$ is a field iff $n$ is prime (Bézout one way, zero divisors the other); finite fields with $p^n$ elements exist.
Vector spaces need a field of scalars because linear algebra divides by scalars; over a ring like $\mathbb Z_6$ the notions of basis and dimension collapse.
Uses: Diffie–Hellman and RSA live in $\mathbb Z_n^\times$ ; crystals and molecules have symmetry groups; QR codes use Reed–Solomon codes over $\mathrm{GF}(256)$ ; the Rubik’s cube group has about $4.3\times10^{19}$ elements.

Watch and read

The same ideas explained by someone else. Use these when an explanation here does not land.

3.9 Groups, rings and fields: a preview built from what you know

The picture

The idea, in words

Groups

Group

Abelian group

What the rules force

Consequences of the group axioms

Subgroups and orders of elements

Subgroup

Subgroup test

Order of an element

A repeated move has as many positions as its order

Lagrange’s theorem

Lagrange's theorem

Consequences of Lagrange's theorem

Homomorphisms

Homomorphism

Homomorphisms preserve identity and inverses

The sign of a permutation

The sign is a homomorphism

Rings

Ring

Zero times anything in a ring

Fields

Field

A field has no zero divisors

Z_n is a field exactly when n is prime

Where it is used

Traps

Problems

Summary

Watch and read

Where this sits

Comes from

Leads to

Same idea elsewhere