Chapter 1

Groups

The group axioms and what they force: uniqueness of the identity and inverses, cancellation, the reversal rule for inverses, and the Cayley table as a Latin square; orders of elements with ord(a^k) = n/gcd(n,k); cyclic groups classified as Z or Z/nZ, with the Klein four-group showing abelian does not imply cyclic; worked throughout in Z/nZ, the unit groups, S_3, the dihedral groups and GL_2.

Introduction

A group is what remains of arithmetic when you delete everything except the ability to combine and to undo. There is one operation instead of two, no order relation, no distributive law, no requirement that the operation commute — and yet the four axioms below are already enough to force a long list of theorems, every one of which then holds simultaneously for the integers under addition, for the invertible $2 \times 2$ matrices, for the permutations of a deck of cards, for the rotations of a crystal and for the symmetries of a differential equation. That is the entire bargain of abstract algebra: assume less, prove once, apply everywhere.

The bargain is worth stating precisely because it is easy to mistake for vagueness. When we prove that the inverse of an element is unique, we are not proving a fact about numbers that happens also to be true of matrices; we are proving a fact about any set with an associative operation, an identity and inverses, and matrices merely happen to be such a set. Nothing in the proof may appeal to commutativity, to cancellation of zero divisors, to the existence of a size or a sign. Every step must be traceable to one of the four axioms or to something already deduced from them. The discipline is the point, and it is what makes the resulting theorems so widely applicable.

This chapter is organised in five movements. The first states the axioms and pins down what they do and do not say — in particular that associativity is a hypothesis about three elements which silently controls expressions of any length, and that the identity and inverse axioms can be weakened to one-sided versions without loss. The second extracts the consequences that follow from the axioms alone: the identity is unique, inverses are unique, cancellation holds on both sides, the equations $a x = b$ and $x a = b$ have exactly one solution each, and the multiplication table of a finite group is a Latin square. None of these is deep; all of them are used constantly, and the habit of deriving them from nothing but the axioms is the habit the subject runs on.

The third movement is a catalogue: $Z / n Z$ , the unit groups $(Z / n Z)^{\times}$ , the symmetric group $S_{3}$ with its table written out in full, the dihedral group $D_{4}$ of symmetries of a square, and the matrix group $G L_{2} (R)$ . These five carry almost every example in the rest of the subject, and it is worth knowing them the way one knows a friend's face rather than as entries on a list. The fourth movement isolates commutativity and shows exactly where it can fail. The fifth develops the order of an element — the single most useful numerical invariant attached to a group element — and closes with cyclic groups, which are the groups generated by one element and which we shall classify completely: up to renaming there is one infinite cyclic group and one of each finite size.

Two conventions hold throughout. We write the operation multiplicatively, as $ab$ rather than $a \cdot b$ , unless the group at hand is visibly additive. And we compose functions right-to-left, so that $σ τ$ means "do $τ$ , then $σ$ " — a choice that costs nothing but must be made once and kept, since half the permutation computations in print use the other one.

1.1The definition of a group

Before the axioms, the object they constrain. An operation on a set is a rule for turning two elements into one, and the requirement that the result land back in the set — closure — is built into the word operation rather than listed separately, though it is worth spelling out because it is the axiom most often violated in practice.

Definition 1.1 (Binary operation). A binary operation on a set $G$ is a function

* : G \times G \to G .

We write $a * b$ for $* (a, b)$ . That the codomain is $G$ itself is the closure requirement: for all $a, b \in G$ , the element $a * b$ again lies in $G$ .

Definition 1.2 (Group). A group is a pair $(G, \cdot)$ consisting of a non-empty set $G$ and a binary operation $\cdot$ on $G$ satisfying:

Closure. For all $a, b \in G$ , $ab \in G$ .
Associativity. For all $a, b, c \in G$ , $(ab) c = a (b c)$ .
Identity. There exists $e \in G$ with $e a = a e = a$ for every $a \in G$ .
Inverses. For every $a \in G$ there exists $a^{- 1} \in G$ with $a a^{- 1} = a^{- 1} a = e$ .

The group is finite if $G$ is a finite set, and then $∣ G ∣$ , the number of elements, is called the order of the group.

Notation. In an additive group the operation is written $a + b$ , the identity is $0$ , the inverse of $a$ is $- a$ , and the $n$ -fold combination $a + a + \dots + a$ is written $na$ rather than $a^{n}$ . Nothing mathematical changes; only the ink does. Mixing the two notations inside one computation is the single commonest source of confusion in a first course, so decide which one a given group is wearing and stay with it.

Three remarks about what the axioms say. First, commutativity is not among them. The most important groups in mathematics — permutation groups, matrix groups, symmetry groups of geometric figures — fail it, and every proof in this chapter is written so as never to use it silently. Second, the identity axiom demands a two-sided identity and the inverse axiom a two-sided inverse; this turns out to be more than necessary, as the proposition One-sided axioms suffice below shows, but it is the convenient form to check against. Third, the inverse axiom is stated after the identity axiom and depends on it: the symbol $e$ in clause 4 refers to an element whose existence clause 3 has just asserted. This is why one cannot verify inverses before producing an identity.

Associativity deserves separate comment because its statement looks weaker than its effect. The axiom constrains only products of three elements, yet what we use daily is that a product of any number of elements is independent of bracketing — that $((ab) c) d$ , $(ab) (c d)$ and $a (b (c d))$ all agree, so that $ab c d$ is unambiguous notation. The passage from three to $n$ is a genuine induction, known as the generalised associative law, and we record it because every later manipulation of a long product silently invokes it.

Proposition 1.3 (Generalised associative law). Let $G$ be a set with an associative binary operation and let $a_{1}, \dots, a_{n} \in G$ . Then every way of inserting parentheses into the expression $a_{1} a_{2} \dots a_{n}$ yields the same element of $G$ .

Proof. Induct on $n$ . The cases $n = 1, 2$ are vacuous and $n = 3$ is the axiom. Suppose the claim holds for all products of fewer than $n$ factors, and let $P$ be any bracketing of $a_{1} \dots a_{n}$ . The outermost operation of $P$ splits the list somewhere, so $P = QR$ where $Q$ is a bracketing of $a_{1} \dots a_{k}$ and $R$ one of $a_{k + 1} \dots a_{n}$ for some $1 \leq k < n$ . By the induction hypothesis $Q$ and $R$ each equal the left-nested products $L_{k} = (\dots ((a_{1} a_{2}) a_{3}) \dots) a_{k}$ and $L^{'} = (\dots (a_{k + 1} a_{k + 2}) \dots) a_{n}$ respectively, so it suffices to show $L_{k} L^{'} = L_{n}$ .

Induct on $n - k$ . If $n - k = 1$ then $L^{'} = a_{n}$ and $L_{k} a_{n} = L_{n}$ by definition of the left-nested product. If $n - k > 1$ , write $L^{'} = L^{''} a_{n}$ where $L^{''}$ is the left-nested product of $a_{k + 1}, \dots, a_{n - 1}$ . Then

L_{k} L^{'} = L_{k} (L^{''} a_{n}) = (L_{k} L^{''}) a_{n} = L_{n - 1} a_{n} = L_{n},

where the second equality is the axiom applied to the three elements $L_{k}$ , $L^{''}$ , $a_{n}$ , and the third is the inner induction hypothesis.∎

From here on we write $ab c d$ and $a_{1} \dots a_{n}$ without parentheses. Note carefully what the proposition does not say: the order of the factors is untouched. Associativity permits rebracketing, never rearrangement, and conflating the two is the first serious error available in this subject.

Intuition. Think of the elements of a group as reversible actions performed on something — shuffles of a deck, rotations of a die, translations of a line — with $ab$ meaning "do $b$ , then do $a$ ". Closure says the result of two allowed actions is again an allowed action. Associativity is automatic for actions, because composing functions is associative: all three of $(ab) c$ and $a (b c)$ describe the same physical sequence "do $c$ , then $b$ , then $a$ ", and the brackets only record the order in which you chose to think about it. The identity is "do nothing". Inverses say every action can be undone from within the repertoire — there is no shuffle you can perform but not reverse.

That picture is not merely an analogy. Cayley's theorem, proved in Group homomorphisms, says every group is a group of reversible actions on a set, namely on itself. So anything you can prove about abstract groups is a statement about symmetry, and anything true of all symmetry is a theorem about groups.

Example 1.4 (Verifying the axioms for $(Z, +)$ ). Show that the integers under ordinary addition form a group, and identify which axiom would fail if $Z$ were replaced by $N = {0, 1, 2, \dots}$ .

Solution.

Closure. The sum of two integers is an integer, so $+$ maps $Z \times Z$ into $Z$ .
Associativity. $(a + b) + c = a + (b + c)$ is a defining property of integer addition.
Identity. Take $e = 0$ : for every $n$ , $n + 0 = 0 + n = n$ .
Inverses. Given $n \in Z$ , the integer $- n$ satisfies $n + (- n) = (- n) + n = 0$ .
So $(Z, +)$ is a group, of infinite order. It is also commutative, but that is a bonus none of the four axioms asked for.
For $N$ , closure, associativity and identity all survive; inverses fail, and fail for every element except $0$ , since $- n \in / N$ when $n > 0$ . A single failure of a single element is enough: $(N, +)$ is not a group.

□

Example 1.5 (Why $(Z, \cdot)$ is not a group). The integers under multiplication satisfy closure, associativity and have the identity $1$ . Determine precisely which elements have inverses, and conclude.

Solution.

An inverse of $n$ would be an integer $x$ with $n x = 1$ . Then $∣ n ∣ ∣ x ∣ = 1$ with both factors positive integers, forcing $∣ n ∣ = ∣ x ∣ = 1$ .
So the only invertible elements are $1$ (inverse $1$ ) and $- 1$ (inverse $- 1$ ). Every other integer, $2$ included, has none: $2 x = 1$ has only the non-integer solution $x = 1/2$ .
The inverse axiom must hold for every element, so $(Z, \cdot)$ is not a group.
Note the general lesson in the shape of this argument. To disprove a group you exhibit one element breaking one axiom; to prove a group you must verify all four for all elements. The two tasks are not symmetric in effort.
The salvage is instructive: the invertible elements ${1, - 1}$ do form a group under multiplication. That construction — keep only what is invertible — is exactly how the unit groups $(Z / n Z)^{\times}$ of the section A catalogue of groups arise.

□

Example 1.6 (An operation that is not associative). Show that subtraction on $Z$ is a binary operation that is closed and has a right identity, but is not associative, and that $(Z, -)$ is therefore not a group.

Solution.

Closure is clear: $a - b \in Z$ .
$0$ is a right identity, since $a - 0 = a$ for all $a$ . It is not a left identity: $0 - a = - a \neq = a$ unless $a = 0$ .
Associativity fails at once: $(5 - 3) - 2 = 0$ while $5 - (3 - 2) = 4$ .
So $(Z, -)$ is not a group. This example is worth carrying because it shows associativity is a real hypothesis with real content, not a formality one may assume of any reasonable operation. Without it the symbol $a - b - c$ is meaningless, and the proposition Generalised associative law is exactly what rescues $ab c$ in the associative case.

□

The axioms as stated are redundant. It is enough to demand a left identity and, relative to it, left inverses; the right-hand versions then follow. This matters in practice: verifying that some construction is a group is half as much work if you only have to check one side, and the proof below is the standard model of an argument that uses nothing but the axioms.

Proposition 1.7 (One-sided axioms suffice). Let $G$ be a set with an associative binary operation. Suppose there is $e \in G$ with $e a = a$ for all $a \in G$ , and that for each $a \in G$ there is $b \in G$ with $ba = e$ . Then $(G, \cdot)$ is a group: $e$ is a two-sided identity and each such $b$ is a two-sided inverse of $a$ .

Proof. Fix $a \in G$ and choose $b$ with $ba = e$ ; choose also $c$ with $c b = e$ . Then

ab = e (ab) = (c b) (ab) = c ((ba) b) = c (e b) = c b = e,

using associativity freely and $ba = e$ in the middle. So $b$ is a right inverse as well as a left one. Consequently

a e = a (ba) = (ab) a = e a = a,

so $e$ is a right identity as well as a left one. Both remaining axioms hold.∎

Pitfall. The mixed hypotheses "left identity plus right inverses" do not give a group. On any set $G$ with at least two elements, define $ab = b$ for all $a, b$ . This operation is associative, every element is a left identity, and $e$ is a right inverse of every element for any fixed choice of $e$ — yet there is no two-sided identity as soon as $∣ G ∣ \geq 2$ . The proposition One-sided axioms suffice is therefore not a free lunch: the two one-sided conditions must be on the same side.

Exercises for §1.1 →

1.2What the axioms already force

Everything in this section is proved from the four axioms and nothing else. The results are short, and they are the tools with which every later computation is carried out.

Theorem 1.8 (Uniqueness of the identity). A group has exactly one identity element. That is, if $e$ and $f$ both satisfy $e x = x e = x$ and $f x = x f = x$ for all $x \in G$ , then $e = f$ .

Proof. Consider the product $e f$ . Since $e$ is an identity, $e f = f$ . Since $f$ is an identity, $e f = e$ . Hence $e = e f = f$ .∎

The proof is two lines and its shape recurs: evaluate one expression in two ways. Note that it needs only that $e$ is a left identity and $f$ a right identity, so it proves rather more than stated — a group cannot contain a stray one-sided identity distinct from $e$ either.

Theorem 1.9 (Uniqueness of inverses). Let $G$ be a group and $a \in G$ . If $b$ and $c$ both satisfy $ab = ba = e$ and $a c = c a = e$ , then $b = c$ . We may therefore speak of the inverse of $a$ and write it $a^{- 1}$ .

Proof. Using the identity axiom, the hypothesis on $c$ , associativity, and the hypothesis on $b$ in turn,

b = b e = b (a c) = (ba) c = ec = c .

∎

Again the proof uses one side of each hypothesis only — $a c = e$ and $ba = e$ — so in fact a left inverse of $a$ equals any right inverse of $a$ . Without uniqueness the notation $a^{- 1}$ would not even be well defined, so this theorem is a licence to write the rest of the subject.

Proposition 1.10 (Inverse of an inverse, inverse of the identity). For every $a$ in a group $G$ : $(a^{- 1})^{- 1} = a$ , and $e^{- 1} = e$ .

Proof. The element $a^{- 1}$ satisfies $a^{- 1} a = a a^{- 1} = e$ . Read that pair of equations as saying that $a$ is a two-sided inverse of $a^{- 1}$ . By the theorem Uniqueness of inverses applied to the element $a^{- 1}$ , its inverse is unique, so $(a^{- 1})^{- 1} = a$ . For the second claim, $ee = e$ exhibits $e$ as an inverse of itself, and uniqueness again finishes.∎

Theorem 1.11 (Cancellation laws). Let $G$ be a group and $a, b, c \in G$ . Then

ab = a c ⟹ b = c (left cancellation),

ba = c a ⟹ b = c (right cancellation) .

Proof. Assume $ab = a c$ . Multiply both sides on the left by $a^{- 1}$ , which exists by the inverse axiom:

a^{- 1} (ab) = a^{- 1} (a c) .

By associativity the left side is $(a^{- 1} a) b = e b = b$ and the right side is $(a^{- 1} a) c = ec = c$ . Hence $b = c$ . The right-hand law is the same computation with $a^{- 1}$ multiplied on the right instead.∎

Pitfall. Cancellation must be performed on the same side of both products. From $ab = c a$ one may conclude nothing in a non-abelian group; the two $a$ 's are not in comparable positions. In $S_{3}$ , with the notation of the section A catalogue of groups, $rs = s r^{2}$ but $s \neq = r^{2}$ . Writing "cancel the $a$ " without checking sides is the most frequent error in first attempts at group-theoretic algebra.

Cancellation is the axiom-level replacement for dividing, and it is worth noticing which familiar fact it does not license. In a group, $ab = e$ does not permit the conclusion " $a = e$ or $b = e$ "; that is a statement about integral domains, proved in Integral domains and fields, and it has no analogue here — in $Z /6 Z$ we have $2 + 4 = 0$ with neither summand zero.

Corollary 1.12 (Unique solutions of linear equations). Let $G$ be a group and $a, b \in G$ . Each of the equations

a x = b and y a = b

has exactly one solution in $G$ , namely $x = a^{- 1} b$ and $y = b a^{- 1}$ .

Proof. Existence. Substituting $x = a^{- 1} b$ gives $a (a^{- 1} b) = (a a^{- 1}) b = e b = b$ , so it is a solution; similarly $(b a^{- 1}) a = b (a^{- 1} a) = b$ .

Uniqueness. If $a x_{1} = b = a x_{2}$ then $x_{1} = x_{2}$ by the theorem Cancellation laws; the same for $y$ using right cancellation.∎

Observe that $a^{- 1} b$ and $b a^{- 1}$ are in general different elements, so the two equations have different answers. In a non-abelian group there is no such thing as " $b / a$ ", and the honest notation is to write the inverse explicitly on the correct side. This corollary is also the reason a group can be defined by a "division" condition: a non-empty set with an associative operation in which $a x = b$ and $y a = b$ are always solvable is automatically a group.

Theorem 1.13 (Socks and shoes: the inverse of a product). Let $G$ be a group and $a, b \in G$ . Then

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

Proof. By the theorem Uniqueness of inverses it suffices to check that $b^{- 1} a^{- 1}$ is a two-sided inverse of $ab$ . Using the generalised associative law,

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

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

Both products are $e$ , so $b^{- 1} a^{- 1}$ is the inverse of $ab$ .∎

Intuition. The name is the mnemonic. You put on socks and then shoes; to undo it you take off shoes and then socks. The undoing reverses the order as well as each individual step, and the reversal is not an artefact of the algebra but a fact about sequences of actions: the last thing done must be the first thing undone. The expression $a^{- 1} b^{- 1}$ tries to remove the socks through the shoes.

Corollary 1.14 (Reversal for a product of $n$ factors). For $a_{1}, \dots, a_{n}$ in a group,

(a_{1} a_{2} \dots a_{n})^{- 1} = a_{n}^{- 1} \dots a_{2}^{- 1} a_{1}^{- 1} .

In particular $(a^{n})^{- 1} = (a^{- 1})^{n}$ for every $n \geq 1$ .

Proof. Induct on $n$ . The case $n = 1$ is trivial and $n = 2$ is the theorem Socks and shoes: the inverse of a product. Assume the formula for $n - 1$ factors and write $P = a_{1} \dots a_{n - 1}$ , so that $a_{1} \dots a_{n} = P a_{n}$ . By the two-factor case and then the induction hypothesis,

(P a_{n})^{- 1} = a_{n}^{- 1} P^{- 1} = a_{n}^{- 1} (a_{n - 1}^{- 1} \dots a_{1}^{- 1}),

which is the claim. Taking all $a_{i} = a$ gives $(a^{n})^{- 1} = (a^{- 1})^{n}$ .∎

Example 1.15 (Solving in a non-abelian group). In a group $G$ , solve $a x b = c$ for $x$ , and simplify $(a b^{- 1})^{- 1}$ and $(ab a^{- 1})^{- 1}$ .

Solution.

Multiply $a x b = c$ on the left by $a^{- 1}$ : $x b = a^{- 1} c$ . Now multiply on the right by $b^{- 1}$ : $x = a^{- 1} c b^{- 1}$ .
By the corollary Unique solutions of linear equations applied twice, this $x$ is the only solution. Note that both multiplications had to be performed on the side where the offending factor sits; multiplying $a x b = c$ on the left by $b^{- 1}$ accomplishes nothing.
By the theorem Socks and shoes: the inverse of a product and the proposition Inverse of an inverse, inverse of the identity, $(a b^{- 1})^{- 1} = (b^{- 1})^{- 1} a^{- 1} = b a^{- 1}$ .
Likewise $(ab a^{- 1})^{- 1} = (a^{- 1})^{- 1} b^{- 1} a^{- 1} = a b^{- 1} a^{- 1}$ . The conjugating element stays put and only the middle factor is inverted — a pattern used constantly once conjugation appears in Subgroups and quotient groups.

□

The last structural consequence of the axioms concerns finite groups, whose operation can be displayed in a table — the Cayley table — with rows and columns indexed by $G$ and the entry in row $a$ , column $b$ equal to $ab$ . The corollary on unique solutions puts a severe combinatorial constraint on which tables can occur.

Definition 1.16 (Latin square). A Latin square of side $n$ is an $n \times n$ array filled from a set of $n$ symbols so that each symbol occurs exactly once in every row and exactly once in every column.

Theorem 1.17 (The Cayley table of a group is a Latin square). Let $G$ be a finite group of order $n$ . In the Cayley table of $G$ , every element of $G$ appears exactly once in each row and exactly once in each column.

Proof. Fix $a \in G$ and consider the row indexed by $a$ , whose entries are $ab$ as $b$ ranges over $G$ . The map $λ_{a} : G \to G$ , $λ_{a} (b) = ab$ , is injective by left cancellation, and since $G$ is finite an injective map from $G$ to itself is surjective. Hence the row consists of all $n$ elements of $G$ , each exactly once. The same argument with $ρ_{a} (b) = ba$ and right cancellation handles the column indexed by $a$ .∎

The converse is false and worth knowing: not every Latin square is the table of a group, because the Latin property encodes cancellation but says nothing about associativity. Latin squares of side $n$ are plentiful, while groups of order $n$ are scarce — there are $576$ Latin squares of side $4$ and only two groups of order $4$ .

Example 1.18 (Completing the table of a group of order $3$ ). Let $G = {e, a, b}$ be a group of order $3$ with identity $e$ . Determine the entire Cayley table, and deduce that $G$ must be cyclic.

Solution.

The row and column of $e$ are forced: $e x = x e = x$ .
Consider $ab$ . By the theorem The Cayley table of a group is a Latin square, the entry $ab$ cannot repeat $a$ (already in row $a$ , at $a e$ ) nor $b$ (already in column $b$ , at $e b$ ). So $ab = e$ .
Symmetrically $ba = e$ , so $b = a^{- 1}$ .
Now $aa$ cannot be $a$ (else $a = e$ by cancellation) and cannot be $e$ (that entry is taken in row $a$ by $ab$ ). So $aa = b$ .
Likewise $bb = a$ , and the table is complete and uniquely determined.
Since $a^{2} = b$ and $a^{3} = ab = e$ , the powers $e, a, a^{2}$ exhaust $G$ , so $G = ⟨ a ⟩$ is cyclic. Every group of order $3$ therefore looks exactly like $Z /3 Z$ — the first instance of a classification, and a preview of the corollary Groups of prime order are cyclic.

□

Exercises for §1.2 →

1.3A catalogue of groups

Five families of examples carry the weight of the whole subject. Learn them concretely — know the elements, know the operation, know the identity, know how to invert — and every abstract theorem afterwards has somewhere to land.

Modular addition

Definition 1.19 (The group $Z / n Z$ ). Fix an integer $n \geq 1$ . For $a \in Z$ write $\overset{a}{ˉ} = {a + kn : k \in Z}$ for its residue class modulo $n$ . The set of residue classes is

Z / n Z = {\overset{ˉ}{0}, \overset{ˉ}{1}, \dots, \overline{n - 1}},

with operation $\overset{a}{ˉ} + \overset{ˉ}{b} = \overline{a + b}$ .

Proposition 1.20 ( $Z / n Z$ is a group of order $n$ ). The operation above is well defined, and $(Z / n Z, +)$ is an abelian group of order $n$ with identity $\overset{ˉ}{0}$ and $- \overset{a}{ˉ} = \overline{n - a}$ for $a \neq = 0$ .

Proof. Well defined. Suppose $\overset{a}{ˉ} = \overset{ˉ}{a^{'}}$ and $\overset{ˉ}{b} = \overset{ˉ}{b^{'}}$ , so $a^{'} = a + kn$ and $b^{'} = b + ln$ . Then $a^{'} + b^{'} = (a + b) + (k + l) n$ , so $\overline{a^{'} + b^{'}} = \overline{a + b}$ . The rule does not depend on the representatives chosen — the one thing that genuinely needs checking whenever an operation is defined on classes.

Axioms. Closure holds by construction. Associativity and commutativity are inherited from $Z$ : $(\overset{a}{ˉ} + \overset{ˉ}{b}) + \overset{c}{ˉ} = \overline{(a + b) + c} = \overline{a + (b + c)} = \overset{a}{ˉ} + (\overset{ˉ}{b} + \overset{c}{ˉ})$ . The class $\overset{ˉ}{0}$ is an identity since $\overset{a}{ˉ} + \overset{ˉ}{0} = \overset{a}{ˉ}$ , and $\overset{a}{ˉ} + \overline{- a} = \overset{ˉ}{0}$ gives inverses, with $\overline{- a} = \overline{n - a}$ .

Order. Every integer is congruent mod $n$ to exactly one of $0, 1, \dots, n - 1$ by division with remainder, so the $n$ listed classes are distinct and exhaust the set.∎

Example 1.21 (Arithmetic in $Z /6 Z$ ). List the inverses of every element of $Z /6 Z$ and verify the Latin square property on the row of $\overset{ˉ}{2}$ .

Solution.

Inverses: $- \overset{ˉ}{0} = \overset{ˉ}{0}$ , $- \overset{ˉ}{1} = \overset{ˉ}{5}$ , $- \overset{ˉ}{2} = \overset{ˉ}{4}$ , $- \overset{ˉ}{3} = \overset{ˉ}{3}$ , $- \overset{ˉ}{4} = \overset{ˉ}{2}$ , $- \overset{ˉ}{5} = \overset{ˉ}{1}$ . Two elements are their own inverses, $\overset{ˉ}{0}$ and $\overset{ˉ}{3}$ , and the rest pair up.
The row of $\overset{ˉ}{2}$ is $\overset{ˉ}{2} + \overset{ˉ}{b}$ for $b = 0, \dots, 5$ , that is $2, 3, 4, 5, 0, 1$ — all six classes, each once, as the theorem The Cayley table of a group is a Latin square requires.
A remark for later: $\overset{ˉ}{3} + \overset{ˉ}{3} = \overset{ˉ}{0}$ with $\overset{ˉ}{3} \neq = \overset{ˉ}{0}$ . In a group there is no prohibition on a non-identity element squaring to the identity, and no analogue of "no zero divisors".

□

Unit groups

Not every element of $Z / n Z$ is invertible for multiplication mod $n$ — indeed $\overset{ˉ}{0}$ never is. Discarding the non-invertible elements leaves a group, and it is the standard example of a finite abelian group that is not obviously cyclic.

Definition 1.22 (Unit group modulo $n$ ). For $n \geq 2$ , the unit group modulo $n$ is

(Z / n Z)^{\times} = {\overset{a}{ˉ} : g cd (a, n) = 1},

under multiplication $\overset{a}{ˉ} \cdot \overset{ˉ}{b} = \overline{ab}$ .

Proposition 1.23 ( $(Z / n Z)^{\times}$ is an abelian group of order $φ (n)$ ). $(Z / n Z)^{\times}$ is an abelian group under multiplication modulo $n$ , of order $φ (n)$ , where $φ$ is Euler's totient function.

Proof. Well defined and closed. Multiplication of classes is well defined by the same representative check as in the proposition $Z / n Z$ is a group of order $n$ . If $g cd (a, n) = g cd (b, n) = 1$ then no prime dividing $n$ divides $a$ or $b$ , hence none divides $ab$ , so $g cd (ab, n) = 1$ and the product stays in the set.

Associativity and commutativity are inherited from $Z$ , and $\overset{ˉ}{1}$ is the identity.

Inverses. If $g cd (a, n) = 1$ then by Bézout's identity, proved in The Euclidean algorithm, there are integers $u, v$ with $a u + n v = 1$ . Reducing mod $n$ gives $\overset{a}{ˉ} \overset{u}{ˉ} = \overset{ˉ}{1}$ . Moreover $g cd (u, n) = 1$ , since any common divisor of $u$ and $n$ divides $a u + n v = 1$ ; hence $\overset{u}{ˉ}$ lies in the set and is a two-sided inverse of $\overset{a}{ˉ}$ (the operation being commutative).

Order. By definition $φ (n)$ counts the integers in ${1, \dots, n}$ coprime to $n$ , which is exactly the number of classes listed.∎

Example 1.24 (The unit group modulo $12$ ). Determine $(Z /12 Z)^{\times}$ , its order, and the order of each of its elements.

Solution.

The residues coprime to $12 = 2^{2} \cdot 3$ are those divisible by neither $2$ nor $3$ : $1, 5, 7, 11$ . So $(Z /12 Z)^{\times} = {1, 5, 7, 11}$ and $φ (12) = 4$ .
Squares: $5^{2} = 25 \equiv 1$ , $7^{2} = 49 \equiv 1$ , $1 1^{2} = 121 \equiv 1$ .
So every non-identity element has order $2$ . There is no element of order $4$ , hence no generator.
Therefore $(Z /12 Z)^{\times}$ is abelian of order $4$ but not cyclic — it is a copy of the Klein four-group of the definition The Klein four-group. Contrast $(Z /7 Z)^{\times}$ , which is cyclic of order $6$ with generator $3$ .
Sanity check on closure: $5 \cdot 7 = 35 \equiv 11$ , $5 \cdot 11 = 55 \equiv 7$ , $7 \cdot 11 = 77 \equiv 5$ — every product lands back in the set, and the pattern "product of two distinct non-identity elements is the third" is precisely the Klein multiplication rule.

□

Symmetric groups

Definition 1.25 (The symmetric group). Let $X = {1, 2, \dots, n}$ . A permutation of $X$ is a bijection $σ : X \to X$ . The symmetric group $S_{n}$ is the set of all permutations of $X$ under composition, $(σ τ) (x) = σ (τ (x))$ .

Proposition 1.26 ( $S_{n}$ is a group of order $n!$ , non-abelian for $n \geq 3$ ). $S_{n}$ is a group under composition, $∣ S_{n} ∣ = n!$ , and $S_{n}$ is abelian exactly when $n \leq 2$ .

Proof. Group axioms. A composite of bijections is a bijection, so composition is a binary operation on $S_{n}$ . Composition of functions is associative. The identity map $id$ satisfies $id σ = σ id = σ$ . Every bijection has a two-sided inverse function, which is again a bijection of $X$ .

Order. A permutation is determined by choosing $σ (1)$ in $n$ ways, then $σ (2)$ in $n - 1$ remaining ways, and so on, giving $n (n - 1) \dots 1 = n!$ permutations.

Commutativity. For $n \leq 2$ we have $∣ S_{n} ∣ \leq 2$ , and any group of order at most $2$ is abelian since one of any two elements must be the identity. For $n \geq 3$ , let $σ = (12)$ and $τ = (13)$ , extended by the identity on the remaining points. Then $(σ τ) (1) = σ (3) = 3$ while $(τ σ) (1) = τ (2) = 2$ , so $σ τ \neq = τ σ$ .∎

We record the smallest non-abelian group in full. Write $r = (123)$ for the $3$ -cycle sending $1 \mapsto 2 \mapsto 3 \mapsto 1$ and $s = (12)$ for the transposition. Then $r^{3} = e$ , $s^{2} = e$ , and a direct check gives the crucial relation

sr = r^{2} s,

which says that moving $s$ past $r$ inverts $r$ . From it every product can be reduced to the form $r^{i} s^{k}$ with $0 \leq i \leq 2$ , $0 \leq k \leq 1$ , so the six elements $e, r, r^{2}, s, rs, r^{2} s$ are all of $S_{3}$ .

Figure 1.27. The Cayley table of

S_{3}

, with

r = (123)

and

s = (12)

. Row

a

, column

b

holds

ab

; every symbol occurs once per row and once per column.

Read two things off the table. It is not symmetric about its main diagonal — the entry in row $s$ , column $r$ is $r^{2} s$ while the entry in row $r$ , column $s$ is $rs$ — which is precisely the failure of commutativity. And each of the six symbols appears once in every row and every column, as the theorem The Cayley table of a group is a Latin square guarantees; that is a useful arithmetic check on any table you compute by hand.

Example 1.28 (Composing permutations in $S_{3}$ ). With $σ = (12)$ and $τ = (13)$ in $S_{3}$ , compute $σ τ$ and $τ σ$ in cycle notation, and find $(σ τ)^{- 1}$ .

Solution.

Recall the convention: $σ τ$ means apply $τ$ first.
For $σ τ$ : $1 τ 3 σ 3$ , so $1 \mapsto 3$ ; $3 τ 1 σ 2$ , so $3 \mapsto 2$ ; $2 τ 2 σ 1$ , so $2 \mapsto 1$ . Hence $σ τ = (132)$ .
For $τ σ$ : $1 \mapsto 2$ , $2 \mapsto 3$ , $3 \mapsto 1$ , so $τ σ = (123)$ .
These differ, confirming $S_{3}$ is non-abelian.
By the theorem Socks and shoes: the inverse of a product, $(σ τ)^{- 1} = τ^{- 1} σ^{- 1} = τ σ$ , since a transposition is its own inverse. And indeed $(132)^{- 1} = (123)$ : inverting a cycle reverses it.

□

Dihedral groups

Definition 1.29 (The dihedral group $D_{n}$ ). For $n \geq 3$ , the dihedral group $D_{n}$ is the group of all symmetries of a regular $n$ -gon — the rigid motions of the plane, rotations and reflections alike, that carry the polygon onto itself — under composition.

Proposition 1.30 (Structure of $D_{n}$ ). Let $r$ be rotation by $2 π / n$ about the centre and $s$ any one of the reflections. Then

D_{n} = {e, r, r^{2}, \dots, r^{n - 1}, s, rs, r^{2} s, \dots, r^{n - 1} s},

so $∣ D_{n} ∣ = 2 n$ ; and the relations

r^{n} = e, s^{2} = e, sr = r^{- 1} s

hold and determine all products. $D_{n}$ is non-abelian for every $n \geq 3$ .

Proof. A symmetry $g$ is determined by where it sends one vertex $v$ and whether it preserves or reverses orientation: the image of $v$ has $n$ possible positions, and the polygon can then be laid down in exactly two ways, so $∣ D_{n} ∣ \leq 2 n$ . Conversely the $n$ rotations $r^{k}$ and the $n$ reflections listed are pairwise distinct — rotations preserve orientation and reflections reverse it, so the two families are disjoint, and within each family the images of a fixed vertex differ. Hence $∣ D_{n} ∣ = 2 n$ and the list is complete.

For the relations: $r^{n}$ is rotation by $2 π$ , the identity; $s^{2} = e$ since a reflection repeated returns every point. For the third, $sr s^{- 1}$ is a rotation (a conjugate of a rotation by an orientation-reversing map reverses the sense of rotation) through $- 2 π / n$ , so $sr s^{- 1} = r^{- 1}$ , that is $sr = r^{- 1} s$ . Using this relation repeatedly, $s r^{k} = r^{- k} s$ , so any word in $r, s$ can be pushed into the form $r^{i} s^{k}$ — which is why the listed $2 n$ elements are closed under multiplication.

Finally $rs \neq = sr$ : if they were equal then $r^{- 1} s = sr = rs$ , and right-cancelling $s$ by the theorem Cancellation laws gives $r^{- 1} = r$ , i.e. $r^{2} = e$ , contradicting that $r$ has order $n \geq 3$ .∎

Figure 1.31. The four axes of symmetry of a square. With

r

the quarter-turn and

s

a reflection,

D_{4}

has the eight elements

e, r, r^{2}, r^{3}, s, rs, r^{2} s, r^{3} s

Example 1.32 (Computing inside $D_{4}$ ). In $D_{4}$ , simplify $s r^{3} s$ and find the order of the element $rs$ .

Solution.

By the relation $sr = r^{- 1} s$ applied three times, $s r^{3} = r^{- 3} s = rs$ (since $r^{4} = e$ ).
Hence $s r^{3} s = (rs) s = r s^{2} = r$ .
For the order of $rs$ : $(rs)^{2} = rsrs = r (sr) s = r (r^{- 1} s) s = r r^{- 1} s^{2} = e$ .
So $rs$ has order $2$ — as does every reflection $r^{k} s$ by the same computation. $D_{4}$ therefore has five elements of order $2$ (the four reflections and $r^{2}$ ), two of order $4$ ( $r$ and $r^{3}$ ), and the identity: $5 + 2 + 1 = 8 = ∣ D_{4} ∣$ , a complete account.

□

Matrix groups

Definition 1.33 (The general linear group). For a field $F$ , the general linear group $G L_{2} (F)$ is the set of $2 \times 2$ matrices with entries in $F$ and non-zero determinant, under matrix multiplication.

Proposition 1.34 ( $G L_{2} (F)$ is a non-abelian group). $G L_{2} (F)$ is a group under matrix multiplication, non-abelian whenever $F$ has more than one non-zero element pattern available — in particular for $F = R$ .

Proof. Closure. $det (A B) = det A det B$ , so a product of matrices with non-zero determinant again has non-zero determinant.

Associativity holds for matrix multiplication generally, being composition of linear maps.

Identity. $I = (1001)$ has $det I = 1 \neq = 0$ and $A I = I A = A$ .

Inverses. For $A = (a c b d)$ with $Δ = a d - b c \neq = 0$ , the matrix

A^{- 1} = \frac{1}{Δ} (d - c - b a)

has entries in $F$ (as $Δ$ is invertible in $F$ ) and satisfies $A A^{- 1} = A^{- 1} A = I$ by direct multiplication; its determinant is $1/Δ \neq = 0$ , so it lies in $G L_{2} (F)$ .

Non-abelian. Over $R$ ,

(1011) (1101) = (2111), (1101) (1011) = (1112),

and these differ.∎

Example 1.35 (Why the determinant condition is exactly right). Show that the set of all $2 \times 2$ real matrices is not a group under multiplication, and that $det : G L_{2} (R) \to R^{\times}$ respects the operation.

Solution.

The zero matrix has no inverse: $0 \cdot A = 0 \neq = I$ for every $A$ . More generally $(1000)$ is non-zero and still singular, since any product with it has a zero second row.
So the inverse axiom fails, and removing exactly the singular matrices — those with $det = 0$ — is what repairs it, by the formula in the proof of the proposition $G L_{2} (F)$ is a non-abelian group.
That $det (A B) = det A det B$ says $det$ carries multiplication in $G L_{2} (R)$ to multiplication in $R^{\times} = R ∖ {0}$ . A map between groups with that property is a homomorphism, the central notion of Group homomorphisms; this one is the first important example.
A finite matrix group worth noting: over $F = Z /2 Z$ there are $16$ matrices, of which $6$ are invertible, and $G L_{2} (Z /2 Z)$ is a non-abelian group of order $6$ — in fact the same group as $S_{3}$ , since it permutes the three non-zero vectors of $F^{2}$ .

□

Summary. The catalogue in one line each. $Z / n Z$ : additive, abelian, order $n$ , cyclic. $(Z / n Z)^{\times}$ : multiplicative, abelian, order $φ (n)$ , cyclic only for special $n$ . $S_{n}$ : permutations, order $n!$ , non-abelian for $n \geq 3$ . $D_{n}$ : symmetries of an $n$ -gon, order $2 n$ , non-abelian, presented by $r^{n} = s^{2} = e$ , $sr = r^{- 1} s$ . $G L_{2} (F)$ : invertible matrices, non-abelian, infinite over $R$ .

Exercises for §1.3 →

1.4Commutativity: abelian groups

Definition 1.36 (Abelian group). A group $G$ is abelian, or commutative, if

ab = ba for all a, b \in G .

An element $a$ with $a x = x a$ for all $x$ is said to be central; the set of central elements is the centre $Z (G)$ , and $G$ is abelian exactly when $Z (G) = G$ .

The name honours Niels Henrik Abel, and the convention that it is written in lower case is a small monument to how thoroughly the notion has been absorbed. Abelian groups are enormously better behaved than groups in general: they are classified completely in the finite case, every subgroup of an abelian group is normal, and quotients by any subgroup exist — all facts developed in Subgroups and quotient groups. The price of that good behaviour is that abelian groups cannot express asymmetry, and asymmetry is exactly what symmetry groups of interesting objects have.

Proposition 1.37 (Commutativity through squares). Let $G$ be a group and $a, b \in G$ . Then $ab = ba$ if and only if $(ab)^{2} = a^{2} b^{2}$ . Consequently $G$ is abelian if and only if $(x y)^{2} = x^{2} y^{2}$ for all $x, y \in G$ .

Proof. ( $\Rightarrow$ ) If $ab = ba$ then $(ab)^{2} = abab = a (ba) b = a (ab) b = a^{2} b^{2}$ .

( $\Leftarrow$ ) Suppose $abab = aabb$ . Left-cancel $a$ by the theorem Cancellation laws to get $bab = abb$ , then right-cancel $b$ to get $ba = ab$ .∎

This is the model for a family of "identity forces commutativity" results, and the next is the most used of them.

Proposition 1.38 (Exponent two implies abelian). If $x^{2} = e$ for every $x$ in a group $G$ , then $G$ is abelian.

Proof. The hypothesis says every element is its own inverse: $x^{2} = e$ gives $x^{- 1} = x$ by the theorem Uniqueness of inverses. Now take any $a, b \in G$ . Applying the hypothesis to the element $ab$ and then the theorem Socks and shoes: the inverse of a product,

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

∎

Pitfall. The converse is wildly false, and the analogous statement for cubes fails outright. $Z /3 Z$ is abelian with no element of order $2$ , so "abelian" does not imply "exponent two"; and there exist non-abelian groups of exponent $3$ — the smallest has order $27$ — so the proposition Exponent two implies abelian does not generalise by replacing $2$ with $3$ . The proof used $x^{- 1} = x$ , which is special to the exponent $2$ .

Example 1.39 (The smallest non-abelian group). Show that every group of order at most $5$ is abelian, so that $S_{3}$ , of order $6$ , is the smallest non-abelian group.

Solution.

Orders $1$ and $2$ : with at most two elements, one is $e$ and commutes with everything, and the other commutes with itself.
Orders $3$ and $5$ are prime, so by the corollary Groups of prime order are cyclic such a group is cyclic, and by the theorem Cyclic groups are abelian it is abelian.
Order $4$ : by the theorem Order of an element divides the order of the group, every element has order $1$ , $2$ or $4$ . If some element has order $4$ the group is cyclic, hence abelian. Otherwise every non-identity element has order $2$ , so $x^{2} = e$ for all $x$ and the proposition Exponent two implies abelian applies.
Hence no non-abelian group has order below $6$ , and $S_{3}$ realises order $6$ non-abelian by the proposition $S_{n}$ is a group of order $n!$ , non-abelian for $n \geq 3$ .

□

Definition 1.40 (The Klein four-group). The Klein four-group is $V_{4} = {e, a, b, c}$ with multiplication determined by

a^{2} = b^{2} = c^{2} = e, ab = ba = c, b c = c b = a, a c = c a = b .

Theorem 1.41 ( $V_{4}$ is abelian but not cyclic). $V_{4}$ is an abelian group of order $4$ containing no element of order $4$ ; in particular it is not cyclic, so an abelian group need not be cyclic.

Proof. Every element satisfies $x^{2} = e$ by the defining relations, so $V_{4}$ is abelian by the proposition Exponent two implies abelian, and the stated products are consistent with the Latin square condition of the theorem The Cayley table of a group is a Latin square. (That the operation is associative is checked by the realisation below, which is quicker than verifying $64$ triples.)

Realise $V_{4}$ concretely as $(Z /12 Z)^{\times} = {1, 5, 7, 11}$ from the example The unit group modulo $12$ , where $5^{2} = 7^{2} = 1 1^{2} = 1$ and $5 \cdot 7 = 11$ , $7 \cdot 11 = 5$ , $5 \cdot 11 = 7$ . Associativity is inherited from multiplication of integers, so $V_{4}$ is a genuine group.

No element has order $4$ : the identity has order $1$ and each of $a, b, c$ has order $2$ . A cyclic group of order $4$ would be generated by a single element $g$ , and then $g$ would have order $4$ by the proposition The cyclic subgroup generated by an element. Hence $V_{4}$ is not cyclic.∎

So among groups of order $4$ there are exactly two possibilities, $Z /4 Z$ and $V_{4}$ , distinguished by whether an element of order $4$ exists. $V_{4}$ is the standard counterexample to the converse of the theorem Cyclic groups are abelian, and it is worth memorising for that purpose alone; it also appears as the group of symmetries of a non-square rectangle and as the subgroup ${e, (12) (34), (13) (24), (14) (23)}$ of $S_{4}$ .

Intuition. Non-commutativity is not an exotic defect; it is what happens whenever the objects being combined move things around in space. Rotating a book about a vertical axis and then about a horizontal one leaves it in a different position from the reverse order — try it. Abelian groups describe quantities that merely accumulate, like displacements along a line or counts of money, where nothing depends on order. The moment your operations have a geometry, expect $ab \neq = ba$ .

Exercises for §1.4 →

1.5Powers and the order of an element

Repeating one element is the simplest thing one can do inside a group, and the arithmetic of doing so is the most useful invariant attached to an element. We start by fixing the notation for powers, including negative ones, and proving that they obey the laws one expects.

Definition 1.42 (Integer powers). Let $G$ be a group and $a \in G$ . Define $a^{0} = e$ , $a^{n + 1} = a^{n} a$ for $n \geq 0$ , and $a^{- n} = (a^{- 1})^{n} = (a^{n})^{- 1}$ for $n \geq 1$ , the last two expressions agreeing by the corollary Reversal for a product of $n$ factors.

Proposition 1.43 (Laws of exponents). For every $a$ in a group and all $m, n \in Z$ ,

a^{m} a^{n} = a^{m + n}, (a^{m})^{n} = a^{mn} .

If moreover $ab = ba$ , then $(ab)^{n} = a^{n} b^{n}$ for all $n \in Z$ .

Proof. For $m, n \geq 0$ the first law is an induction on $n$ : the case $n = 0$ reads $a^{m} e = a^{m}$ , and $a^{m} a^{n + 1} = a^{m} (a^{n} a) = (a^{m} a^{n}) a = a^{m + n} a = a^{m + n + 1}$ using the generalised associative law. For mixed signs, write $m + n = k$ and reduce to the non-negative case by multiplying by suitable powers of $a^{- 1}$ ; concretely, if $m \geq 0 > n$ put $n = - p$ with $p > 0$ , and $a^{m} a^{- p} = a^{m} (a^{p})^{- 1}$ , which after cancelling $min (m, p)$ factors of $a$ against $a^{- 1}$ leaves $a^{m - p}$ in either case. The second law follows from the first by induction on $n \geq 0$ and then by inverting for $n < 0$ .

Note that the third claim genuinely needs $ab = ba$ : by the proposition Commutativity through squares already the case $n = 2$ characterises commuting elements. Given $ab = ba$ , an induction shows $a^{i} b = b a^{i}$ for all $i$ , whence $(ab)^{n + 1} = (ab)^{n} (ab) = a^{n} b^{n} ab = a^{n} a b^{n} b = a^{n + 1} b^{n + 1}$ .∎

Pitfall. In a non-abelian group $(ab)^{n} \neq = a^{n} b^{n}$ in general, and no amount of rebracketing repairs it: the proposition Generalised associative law lets you move parentheses, never factors. In $S_{3}$ , $(rs)^{2} = e$ while $r^{2} s^{2} = r^{2} \neq = e$ .

Definition 1.44 (Order of an element). Let $G$ be a group and $a \in G$ . If some positive integer $k$ satisfies $a^{k} = e$ , the order of $a$ , written $ord (a)$ or $∣ a ∣$ , is the least such $k$ . If no positive power of $a$ equals $e$ , then $a$ has infinite order.

Proposition 1.45 (Every element of a finite group has finite order). If $G$ is a finite group and $a \in G$ , then $ord (a)$ is finite, and $ord (a) \leq ∣ G ∣$ .

Proof. The elements $a^{0}, a^{1}, a^{2}, \dots, a^{∣ G ∣}$ are $∣ G ∣ + 1$ entries of a set with $∣ G ∣$ members, so by the pigeonhole principle two coincide: $a^{i} = a^{j}$ with $0 \leq i < j \leq ∣ G ∣$ . Multiplying by $(a^{i})^{- 1}$ and using the proposition Laws of exponents gives $a^{j - i} = e$ with $1 \leq j - i \leq ∣ G ∣$ . Hence some positive power is the identity, so a least one exists and is at most $∣ G ∣$ .∎

The next theorem is the workhorse. It converts every question of the form "is $a^{k}$ the identity?" into a divisibility question about integers, and it is the reason orders interact so cleanly with number theory.

Theorem 1.46 ( $a^{k} = e$ if and only if $ord (a) ∣ k$ ). Let $a$ be an element of finite order $n = ord (a)$ , and let $k \in Z$ . Then

a^{k} = e ⟺ n ∣ k .

Moreover $a^{i} = a^{j}$ if and only if $i \equiv j (mod n)$ , so $e, a, a^{2}, \dots, a^{n - 1}$ are distinct.

Proof. ( $\Leftarrow$ ) If $k = n q$ then $a^{k} = (a^{n})^{q} = e^{q} = e$ by the proposition Laws of exponents.

( $\Rightarrow$ ) Suppose $a^{k} = e$ . Divide with remainder: $k = n q + r$ with $0 \leq r < n$ . Then

e = a^{k} = a^{n q} a^{r} = (a^{n})^{q} a^{r} = a^{r} .

So $a^{r} = e$ with $0 \leq r < n$ . Since $n$ is the least positive integer with $a^{n} = e$ , we cannot have $0 < r < n$ ; hence $r = 0$ and $n ∣ k$ .

For the last claim, $a^{i} = a^{j}$ iff $a^{i - j} = e$ iff $n ∣ i - j$ iff $i \equiv j (mod n)$ . In particular the exponents $0, 1, \dots, n - 1$ are pairwise incongruent mod $n$ , so the corresponding powers are distinct.∎

Pitfall. Finding some $k$ with $a^{k} = e$ does not compute the order — it only bounds it, and by the theorem above the true order divides $k$ . In $(Z /7 Z)^{\times}$ one has $2^{6} = 64 \equiv 1$ , but $ord (2) = 3$ , since $2^{3} = 8 \equiv 1$ . The efficient method is to compute $a^{d}$ for the divisors $d$ of a known exponent, smallest first.

Proposition 1.47 (The order of a power). Let $a$ have finite order $n$ and let $k \geq 1$ . Then

ord (a^{k}) = \frac{n}{g cd ( n , k )} .

In particular $ord (a^{k}) = n$ exactly when $g cd (n, k) = 1$ .

Proof. Write $d = g cd (n, k)$ , $n = d n^{'}$ , $k = d k^{'}$ with $g cd (n^{'}, k^{'}) = 1$ . Then

(a^{k})^{n^{'}} = a^{k n^{'}} = a^{d k^{'} n^{'}} = a^{n k^{'}} = (a^{n})^{k^{'}} = e,

so by the theorem $a^{k} = e$ if and only if $ord (a) ∣ k$ the order of $a^{k}$ divides $n^{'}$ . Conversely, if $(a^{k})^{m} = e$ then $n ∣ km$ , i.e. $d n^{'} ∣ d k^{'} m$ , so $n^{'} ∣ k^{'} m$ ; since $g cd (n^{'}, k^{'}) = 1$ , Euclid's lemma (proved in Divisibility and primes) gives $n^{'} ∣ m$ . Hence $n^{'}$ is the least positive such $m$ , and $ord (a^{k}) = n^{'} = n / d$ .∎

Proposition 1.48 (Order is invariant under inversion and conjugation). For any $a, g$ in a group $G$ : $ord (a^{- 1}) = ord (a)$ and $ord (g a g^{- 1}) = ord (a)$ .

Proof. For the first, $(a^{- 1})^{k} = (a^{k})^{- 1}$ by the corollary Reversal for a product of $n$ factors, and an element equals $e$ exactly when its inverse does; so the two elements satisfy the same set of relations $x^{k} = e$ , and hence have the same least one.

For the second, induct on $k$ to see $(g a g^{- 1})^{k} = g a^{k} g^{- 1}$ : the case $k = 1$ is trivial, and $(g a g^{- 1})^{k + 1} = (g a^{k} g^{- 1}) (g a g^{- 1}) = g a^{k} (g^{- 1} g) a g^{- 1} = g a^{k + 1} g^{- 1}$ . Therefore $(g a g^{- 1})^{k} = e$ iff $g a^{k} g^{- 1} = e$ iff $a^{k} = g^{- 1} e g = e$ , and again the two elements have the same least such $k$ .∎

Definition 1.49 (The cyclic subgroup generated by an element). For $a \in G$ , put

⟨ a ⟩ = {a^{k} : k \in Z} \subseteq G .

Proposition 1.50 (The cyclic subgroup generated by an element). For every $a \in G$ , the set $⟨ a ⟩$ is a subgroup of $G$ , it is abelian, and

∣ ⟨ a ⟩ ∣ = ord (a)

when $a$ has finite order, with $⟨ a ⟩ = {e, a, \dots, a^{n - 1}}$ for $n = ord (a)$ ; if $a$ has infinite order then $⟨ a ⟩$ is infinite and its elements $a^{k}$ , $k \in Z$ , are pairwise distinct. Moreover $⟨ a ⟩$ is contained in every subgroup of $G$ containing $a$ .

Proof. Subgroup. $e = a^{0} \in ⟨ a ⟩$ ; the product $a^{i} a^{j} = a^{i + j}$ lies in the set; and $(a^{i})^{- 1} = a^{- i}$ does too. So $⟨ a ⟩$ is closed under the operation and inverses and contains the identity, which is exactly what is required of a subgroup in Subgroups and quotient groups. Associativity is inherited.

Abelian. $a^{i} a^{j} = a^{i + j} = a^{j + i} = a^{j} a^{i}$ by the proposition Laws of exponents.

Size. Suppose $ord (a) = n < \infty$ . Every $k \in Z$ is congruent mod $n$ to some $r \in {0, \dots, n - 1}$ , and then $a^{k} = a^{r}$ by the theorem $a^{k} = e$ if and only if $ord (a) ∣ k$ ; so the listed $n$ elements exhaust $⟨ a ⟩$ , and the same theorem says they are distinct. If $a$ has infinite order and $a^{i} = a^{j}$ with $i > j$ , then $a^{i - j} = e$ with $i - j > 0$ , a contradiction; so the powers are distinct and $⟨ a ⟩$ is infinite.

Minimality. A subgroup $H ∋ a$ is closed under products and inverses, so it contains $a^{k}$ for every $k \in Z$ by induction, i.e. $H \supseteq ⟨ a ⟩$ .∎

With $⟨ a ⟩$ in hand, the most quoted fact about orders in a finite group follows immediately from Lagrange's theorem, which is proved in the next chapter, Subgroups and quotient groups. We state and use it here, flagging the forward reference honestly.

Theorem 1.51 (Order of an element divides the order of the group). Let $G$ be a finite group and $a \in G$ . Then $ord (a)$ divides $∣ G ∣$ .

Proof. By the proposition The cyclic subgroup generated by an element, $⟨ a ⟩$ is a subgroup of $G$ with $∣ ⟨ a ⟩ ∣ = ord (a)$ , the order being finite by the proposition Every element of a finite group has finite order. By Lagrange's theorem, established in Subgroups and quotient groups, the order of a subgroup of a finite group divides the order of the group. Hence $ord (a) = ∣ ⟨ a ⟩ ∣$ divides $∣ G ∣$ .∎

Corollary 1.52 ( $a^{∣ G ∣} = e$ , and groups of prime order are cyclic). Let $G$ be a finite group of order $n$ . Then $a^{n} = e$ for every $a \in G$ . If moreover $n = p$ is prime, then $G$ is cyclic and is generated by any of its $p - 1$ non-identity elements.

Proof. By the theorem Order of an element divides the order of the group, $ord (a) ∣ n$ , so $a^{n} = e$ by the theorem $a^{k} = e$ if and only if $ord (a) ∣ k$ .

Now let $n = p$ be prime and $a \neq = e$ . Then $ord (a)$ divides $p$ and is not $1$ (since $a \neq = e$ ), so $ord (a) = p$ . By the proposition The cyclic subgroup generated by an element, $⟨ a ⟩$ has $p$ elements, hence equals $G$ .∎

Applied to $G = (Z / n Z)^{\times}$ , whose order is $φ (n)$ by the proposition $(Z / n Z)^{\times}$ is an abelian group of order $φ (n)$ , the corollary reads $a^{φ (n)} \equiv 1 (mod n)$ for every $a$ coprime to $n$ — Euler's theorem, and with $n$ prime, Fermat's little theorem. That a purely structural statement about finite groups reproduces two of the pillars of elementary number theory is the clearest possible advertisement for the axiomatic method.

Example 1.53 (Orders in $Z /12 Z$ ). Compute the order of every element of the additive group $Z /12 Z$ and verify each divides $12$ .

Solution.

In additive notation, $ord (a)$ is the least $k > 0$ with $ka \equiv 0 (mod 12)$ . Taking $a = k \cdot 1$ and applying the proposition The order of a power to the generator $1$ , which has order $12$ , gives

ord (a) = \frac{12}{g cd ( 12 , a )} .

Hence: $ord (0) = 1$ ; $ord (1) = ord (5) = ord (7) = ord (11) = 12$ ; $ord (2) = ord (10) = 6$ ; $ord (3) = ord (9) = 4$ ; $ord (4) = ord (8) = 3$ ; $ord (6) = 2$ .
The orders occurring are $1, 2, 3, 4, 6, 12$ — exactly the divisors of $12$ , each achieved. Every one divides $12$ , as the theorem Order of an element divides the order of the group requires.
The count of elements of order $12$ is four, matching $φ (12) = 4$ ; this is the general rule proved in the theorem Generators of a finite cyclic group.

□

Example 1.54 (Order of a permutation). Find the order of $σ = (1234) (567) \in S_{7}$ and of $τ = (12) (345) \in S_{5}$ .

Solution.

Disjoint cycles commute, since they move disjoint sets of points, so by the proposition Laws of exponents $σ^{k}$ is the product of the $k$ -th powers of the two cycles.
A $c$ -cycle has order $c$ : applying it $c$ times returns every moved point to its start, and no fewer will do so for the first point.
So $σ^{k} = e$ requires $4 ∣ k$ and $3 ∣ k$ , and by the theorem $a^{k} = e$ if and only if $ord (a) ∣ k$ the order is the least such $k$ , namely $lcm (4, 3) = 12$ .
Similarly $ord (τ) = lcm (2, 3) = 6$ .
General rule: the order of a permutation is the least common multiple of its disjoint cycle lengths. Check against Lagrange: $12 ∣ 5040 = 7!$ and $6 ∣ 120 = 5!$ .

□

Example 1.55 (An element of infinite order). Exhibit elements of infinite order in $(Z, +)$ and in $G L_{2} (R)$ , and explain why this does not contradict the proposition Every element of a finite group has finite order.

Solution.

In $(Z, +)$ the element $1$ has infinite order: $k \cdot 1 = k \neq = 0$ for every $k > 0$ .
In $G L_{2} (R)$ take $A = (1011)$ . Induction gives $A^{k} = (10 k 1)$ , which is never $I$ for $k \geq 1$ .
There is no contradiction: that proposition assumes $G$ finite, and its proof used the pigeonhole principle on the finitely many elements of $G$ . Both groups here are infinite.
Note that an infinite group may still have elements of finite order — $(01 - 1 0) \in G L_{2} (R)$ is rotation by a quarter turn and has order $4$ — so "infinite group" and "all elements of infinite order" are different conditions.

□

Exercises for §1.5 →

1.6Cyclic groups

A cyclic group is one that a single element already fills. They are the simplest groups there are, and the classification below says there are essentially no surprises among them: one infinite example and one of each finite order.

Definition 1.56 (Cyclic group and generator). A group $G$ is cyclic if $G = ⟨ g ⟩$ for some $g \in G$ ; such a $g$ is called a generator of $G$ . A cyclic group may have many generators.

Theorem 1.57 (Cyclic groups are abelian). Every cyclic group is abelian.

Proof. Let $G = ⟨ g ⟩$ and take $x, y \in G$ . By definition $x = g^{m}$ and $y = g^{n}$ for some integers $m, n$ . By the proposition Laws of exponents,

x y = g^{m} g^{n} = g^{m + n} = g^{n + m} = g^{n} g^{m} = y x,

the middle step being commutativity of addition in $Z$ .∎

Pitfall. The converse fails. By the theorem $V_{4}$ is abelian but not cyclic, the Klein four-group is abelian of order $4$ with no element of order $4$ . Equivalently $(Z /12 Z)^{\times}$ is abelian but not cyclic. "Abelian" is a condition on pairs of elements; "cyclic" asserts the existence of a single element that generates everything, which is far stronger.

Note where the proof of Cyclic groups are abelian got its leverage: commutativity in the group was imported wholesale from commutativity of addition in the exponents. The same observation, pushed one step further, classifies cyclic groups completely.

Theorem 1.58 (Classification of cyclic groups). Let $G = ⟨ g ⟩$ be cyclic.

If $g$ has infinite order, the map $k \mapsto g^{k}$ is a bijection $Z \to G$ carrying addition to the group operation; so $G$ is a relabelling of $(Z, +)$ .
If $g$ has finite order $n$ , the map $\overset{ˉ}{k} \mapsto g^{k}$ is a well-defined bijection $Z / n Z \to G$ carrying addition to the group operation; so $G$ is a relabelling of $(Z / n Z, +)$ .

Hence up to isomorphism there is exactly one cyclic group of each finite order $n$ and exactly one of infinite order.

Proof. Define $Φ (k) = g^{k}$ in both cases. By the proposition Laws of exponents, $Φ (k + l) = g^{k + l} = g^{k} g^{l} = Φ (k) Φ (l)$ , so $Φ$ turns addition into the group operation. It is surjective onto $⟨ g ⟩ = G$ by definition of $⟨ g ⟩$ .

(1) If $g$ has infinite order then $Φ$ is injective: $g^{k} = g^{l}$ with $k > l$ would give $g^{k - l} = e$ with $k - l > 0$ , contradicting infinite order. So $Φ : Z \to G$ is a bijection.

(2) If $ord (g) = n$ , then by the theorem $a^{k} = e$ if and only if $ord (a) ∣ k$ we have $g^{k} = g^{l}$ exactly when $k \equiv l (mod n)$ . That says precisely that $Φ$ descends to a well-defined map on residue classes and that the descended map is injective; it is surjective as before. Since both sides have $n$ elements, the correspondence is a bijection.

Two cyclic groups of the same order are therefore each relabellings of the same $Z / n Z$ (or of $Z$ ), hence relabellings of each other.∎

This is a complete classification, and it is worth pausing on how rare that is. Groups of order $n$ in general are not classified for most $n$ ; cyclic groups of order $n$ are, and the answer is "there is one". The theorem is also the reason one may stop saying "a cyclic group of order $12$ " and start saying " $Z /12 Z$ " without loss.

Theorem 1.59 (Generators of a finite cyclic group). Let $G = ⟨ g ⟩$ be cyclic of order $n$ . Then $g^{k}$ generates $G$ if and only if $g cd (k, n) = 1$ , and consequently $G$ has exactly $φ (n)$ generators.

Proof. By the proposition The cyclic subgroup generated by an element, $g^{k}$ generates $G$ iff $∣ ⟨ g^{k} ⟩ ∣ = n$ iff $ord (g^{k}) = n$ . By the proposition The order of a power, $ord (g^{k}) = n / g cd (n, k)$ , which equals $n$ exactly when $g cd (n, k) = 1$ . Counting the $k \in {0, 1, \dots, n - 1}$ with $g cd (k, n) = 1$ gives $φ (n)$ generators.∎

Theorem 1.60 (Subgroups of a finite cyclic group). Let $G = ⟨ g ⟩$ be cyclic of order $n$ . Then every subgroup of $G$ is cyclic, and for each positive divisor $d$ of $n$ there is exactly one subgroup of order $d$ , namely $⟨ g^{n / d} ⟩$ . In particular $G$ has exactly $τ (n)$ subgroups, where $τ (n)$ is the number of positive divisors of $n$ .

Proof. Every subgroup is cyclic. Let $H \leq G$ with $H \neq = {e}$ . Let $m$ be the least positive integer with $g^{m} \in H$ ; such an $m$ exists because $H$ contains some $g^{k}$ with $k \neq \equiv 0$ , and then also $g^{- k}$ . Given any $g^{t} \in H$ , divide $t = m q + r$ with $0 \leq r < m$ ; then $g^{r} = g^{t} (g^{m})^{- q} \in H$ , so minimality of $m$ forces $r = 0$ . Hence $H = ⟨ g^{m} ⟩$ .

Existence. For $d ∣ n$ , the element $g^{n / d}$ has order $n / g cd (n, n / d) = n / (n / d) = d$ by the proposition The order of a power, so $⟨ g^{n / d} ⟩$ has order $d$ by the proposition The cyclic subgroup generated by an element.

Uniqueness. Let $H$ be any subgroup of order $d$ . By the first part $H = ⟨ g^{m} ⟩$ for some $m$ , and its order is $n / g cd (n, m) = d$ , so $g cd (n, m) = n / d$ . Writing $g cd (n, m) = n / d$ , the powers of $g^{m}$ are exactly the powers of $g^{g c d (n, m)} = g^{n / d}$ — because $g cd (n, m)$ is an integer combination $u n + v m$ , giving $g^{g c d (n, m)} = (g^{n})^{u} (g^{m})^{v} = (g^{m})^{v} \in H$ , and conversely $m$ is a multiple of $g cd (n, m)$ . Hence $H = ⟨ g^{n / d} ⟩$ .

The subgroups therefore correspond bijectively to the positive divisors of $n$ , of which there are $τ (n)$ .∎

Figure 1.61. The subgroup lattice of

Z /12 Z

: one subgroup per divisor of

12

, drawn with a line upward from each subgroup to those containing it.

The lattice is a picture of the theorem. Six nodes for the six divisors $1, 2, 3, 4, 6, 12$ of $12$ ; a line from $H$ up to $K$ exactly when $H \subseteq K$ , which by the correspondence happens exactly when $∣ H ∣$ divides $∣ K ∣$ . So the subgroup lattice of $Z / n Z$ is the divisor lattice of $n$ redrawn, and questions about subgroups become questions about factorisation. Compare $V_{4}$ , whose three subgroups of order $2$ are incomparable and which has four subgroups in total though $τ (4) = 3$ — another way to see it is not cyclic.

Example 1.62 (Generators and subgroups of $Z /18 Z$ ). How many generators does $Z /18 Z$ have, how many subgroups, and what is the order of the subgroup generated by $12$ ?

Solution.

Generators: by the theorem Generators of a finite cyclic group there are $φ (18) = φ (2) φ (9) = 1 \cdot 6 = 6$ of them, namely $1, 5, 7, 11, 13, 17$ .
Subgroups: by the theorem Subgroups of a finite cyclic group there is one per divisor of $18$ . The divisors are $1, 2, 3, 6, 9, 18$ , so there are $6$ subgroups.
$ord (12) = 18/ g cd (18, 12) = 18/6 = 3$ , so $⟨ 12 ⟩ = {0, 12, 6}$ has order $3$ .
Sanity check: $3$ divides $18$ , as the theorem Order of an element divides the order of the group demands, and ${0, 6, 12}$ is the unique subgroup of order $3$ , matching $⟨ 18/3 ⟩ = ⟨ 6 ⟩$ .

□

Example 1.63 (Which unit groups are cyclic?). Decide whether $(Z /9 Z)^{\times}$ and $(Z /8 Z)^{\times}$ are cyclic.

Solution.

$(Z /9 Z)^{\times} = {1, 2, 4, 5, 7, 8}$ has order $φ (9) = 6$ . Compute powers of $2$ : $2, 4, 8, 16 \equiv 7, 14 \equiv 5, 10 \equiv 1$ . Six distinct powers, so $ord (2) = 6$ and the group is cyclic with generator $2$ .
$(Z /8 Z)^{\times} = {1, 3, 5, 7}$ has order $φ (8) = 4$ . Squares: $3^{2} = 9 \equiv 1$ , $5^{2} = 25 \equiv 1$ , $7^{2} = 49 \equiv 1$ .
Every non-identity element has order $2$ , so there is no element of order $4$ and the group is not cyclic; by the theorem $V_{4}$ is abelian but not cyclic it is another copy of the Klein four-group.
The pattern is a theorem of number theory: $(Z / n Z)^{\times}$ is cyclic exactly for $n = 1, 2, 4, p^{k}, 2 p^{k}$ with $p$ an odd prime. A generator, when one exists, is called a primitive root mod $n$ .

□

Example 1.64 (An abelian group that is not cyclic, from the catalogue). Show directly that $Z /2 Z \times Z /2 Z$ , with componentwise addition, is abelian of order $4$ and not cyclic.

Solution.

The elements are $(0, 0), (1, 0), (0, 1), (1, 1)$ , so the order is $4$ . Addition is componentwise and $Z /2 Z$ is abelian, so the product is abelian.
Each non-identity element doubles to the identity: $(1, 0) + (1, 0) = (0, 0)$ , and likewise for the other two.
Hence every element has order $1$ or $2$ , so no element has order $4$ , so no element generates — the group is not cyclic. By the proposition Exponent two implies abelian it is abelian, and it is another realisation of $V_{4}$ .
Contrast $Z /2 Z \times Z /3 Z$ , where $(1, 1)$ has order $lcm (2, 3) = 6$ and so generates a group of order $6$ : that product is cyclic. The general criterion, proved in Subgroups and quotient groups, is that $Z / m Z \times Z / n Z$ is cyclic exactly when $g cd (m, n) = 1$ .

□

Summary. The order of an element is the size of the cyclic subgroup it generates, and everything else follows from that identification. $a^{k} = e$ iff $ord (a) ∣ k$ ; $ord (a^{k}) = ord (a) / g cd (ord (a), k)$ ; $ord (a)$ divides $∣ G ∣$ when $G$ is finite, so $a^{∣ G ∣} = e$ . A cyclic group of order $n$ is $Z / n Z$ up to relabelling, has $φ (n)$ generators and exactly $τ (n)$ subgroups, one for each divisor of $n$ .

Exercises for §1.6 →

Common Mistakes

Cancelling on the wrong side. The theorem Cancellation laws gives $ab = a c \Rightarrow b = c$ and $ba = c a \Rightarrow b = c$ ; it says nothing about $ab = c a$ . In $S_{3}$ , $rs = s r^{2}$ with $s \neq = r^{2}$ .
Writing $(ab)^{- 1} = a^{- 1} b^{- 1}$ . The correct reversal is $b^{- 1} a^{- 1}$ , by the theorem Socks and shoes: the inverse of a product. The two agree only when $a$ and $b$ commute.
Assuming $(ab)^{n} = a^{n} b^{n}$ . By the proposition Commutativity through squares, even the case $n = 2$ holds exactly when $ab = ba$ . In $D_{4}$ , $(rs)^{2} = e$ while $r^{2} s^{2} = r^{2}$ .
Confusing rebracketing with rearranging. The proposition Generalised associative law licenses $a (b c) = (ab) c$ ; it never licenses $ab c = ba c$ .
Confusing the order of an element with the order of the group. Both are written with $∣ \cdot ∣$ and they are different numbers; $ord (a)$ divides $∣ G ∣$ and is usually much smaller.
Reading " $a^{k} = e$ " as " $k$ is the order of $a$ ". By the theorem $a^{k} = e$ if and only if $ord (a) ∣ k$ , such a $k$ is only a multiple of the order. $2^{6} \equiv 1 (mod 7)$ but $ord (2) = 3$ .
Using $ord (a) = n / g cd (n, a)$ in a multiplicative group. That formula comes from the proposition The order of a power applied to the additive generator $1$ of $Z / n Z$ ; in $(Z / n Z)^{\times}$ orders must be computed from powers, and the relevant group order is $φ (n)$ , not $n$ .
Assuming abelian implies cyclic. The theorem $V_{4}$ is abelian but not cyclic is the standing counterexample; $(Z /8 Z)^{\times}$ and $Z /2 Z \times Z /2 Z$ are the same obstruction in different clothes. The implication runs only one way, by the theorem Cyclic groups are abelian.
Forgetting closure. The even integers are a group under addition; the odd integers are not, and fail on closure and identity together. Checking three axioms and assuming the fourth is how non-groups get certified.
Expecting a converse to Lagrange from the theorem Order of an element divides the order of the group. That $d$ divides $∣ G ∣$ does not produce an element of order $d$ : the alternating group $A_{4}$ has order $12$ and no element of order $6$ . Only for cyclic groups does every divisor occur, by the theorem Subgroups of a finite cyclic group.
Treating $ab = e$ as forcing $a = e$ or $b = e$ . There are no "zero divisors" to appeal to; $ab = e$ says only $b = a^{- 1}$ , by the theorem Uniqueness of inverses.
Checking a Latin square and declaring a group. The theorem The Cayley table of a group is a Latin square is one-directional; associativity is invisible in the table and must be verified separately, usually by realising the group concretely.

About the practice questions. They check that you can carry out this chapter's computations correctly, and each one is graded on a single answer. They are not proof exercises: working through them confirms the mechanics, not that you could prove the results yourself. For that, re-read the statements above and try to reconstruct their proofs with the page closed.

Practice this chapter