---
title: "Algebraic Structures"
book: "University Mathematics — Year 1"
subject: math
language: en
chapter: 7
exercises: 12
source: https://one-course.com/books/math/3/en/chapter/7-algebraic-structures
---

# Chapter 7 — Algebraic Structures

The same computation rules keep reappearing: integers, real numbers, complex numbers, [congruence](https://one-course.com/books/math/3/en/chapter/6-integer-arithmetic#def-b1-arith-congruence) classes, and soon polynomials ([Chapter 8](https://one-course.com/books/math/3/en/chapter/8-polynomials#ch-b1-poly)), vectors and matrices (Chapters [18](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#ch-b1-vspaces) and [21](https://one-course.com/books/math/3/en/chapter/21-matrices#ch-b1-matrices)). Algebra extracts the common patterns and names them: *[group](#def-b1-structures-group)*, *[ring](#def-b1-structures-ring)*, *[field](#def-b1-structures-field)*. Proving a fact once, at the level of the structure, proves it for every example at once.

## 7.1 Laws of composition

**Definition 7.1.**

A *law of composition* on a [set](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-sets) $E$ is a [map](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-map) $E \times E \to E$, written $(x, y) \mapsto x * y$. It is *associative* when $(x*y)*z = x*(y*z)$ always, *commutative* when $x * y = y * x$ always. An element $e$ is an *identity* when $e * x = x * e = x$ for all $x$; then $x'$ is an *inverse* of $x$ when $x * x' = x' * x = e$.

**Proposition 7.2 (Uniqueness).**

A law has at most one identity; for an associative law with identity, each element has at most one inverse.

**Proof.** If $e$ and $e'$ are identities: $e = e * e' = e'$. If $x'$ and $x''$ invert $x$: $x' = x' * e = x' * (x * x'') = (x' * x) * x'' = e * x''
= x''$. ∎

## 7.2 Groups

**Definition 7.3 (Group).**

A *group* $(G, *)$ is a [set](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-sets) with an associative law admitting an identity and in which every element has an inverse. The group is *abelian* when the law is commutative.

**Example 7.4.**

$(\Z, +)$, $(\Q, +)$, $(\R, +)$, $(\C, +)$; $(\Q^*, \times)$, $(\R^*, \times)$, $(\C^*, \times)$, $(\mathbb{U}_n, \times)$ ([roots of unity](https://one-course.com/books/math/3/en/chapter/3-complex-numbers#def-b1-complex-unity), [Definition 3.17](https://one-course.com/books/math/3/en/chapter/3-complex-numbers#def-b1-complex-unity)); the [set](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-sets) $\mathfrak{S}(E)$ of bijections of a [set](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-sets) $E$ onto itself, under composition — the *symmetric group* of $E$, [non-abelian](#def-b1-structures-group) as soon as $\abs E \geq 3$. Not [groups](#def-b1-structures-group): $(\N, +)$ (no inverses), $(\Z, \times)$ (only $\pm 1$ invertible).

**Proposition 7.5 (Computation rules).**

In a [group](#def-b1-structures-group) $G$ (written multiplicatively, identity $e$):

1. cancellation: $ax = ay \implies x = y$ and $xa = ya \implies  x = y$ ;
2. $(ab)^{-1} = b^{-1} a^{-1}$ and $(a^{-1})^{-1} = a$ ;
3. for $a, b \in G$ , each equation $ax = b$ and $xa = b$ has a unique solution ( $x = a^{-1}b$ , resp. $x = b a^{-1}$ ).

**Proof.** (1) Multiply by $a^{-1}$ on the appropriate side, using associativity. (2) $(b^{-1}a^{-1})(ab) = b^{-1}(a^{-1}a)b = b^{-1}b =
e$ and symmetrically; uniqueness of the inverse concludes; the second point is [Proposition 7.2](#prop-b1-structures-unique) applied to $a^{-1}$. (3) Substitute and use (1) for uniqueness. ∎

**Example 7.6 (The symmetries of a rectangle).**

A (non-square) rectangle admits exactly four isometries onto itself: the identity $e$, the horizontal-axis reflection $h$, the vertical-axis reflection $v$, and the half-turn $r$ about the center. Composition makes this four-element [set](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-sets) a [group](#def-b1-structures-group): each element is its own inverse ($h^2 = v^2 = r^2 = e$), and the product of any two distinct non-identity elements is the third ($hv = vh = r$: reflecting in both axes is the half-turn). The full table is symmetric, so the [group](#def-b1-structures-group) is [abelian](#def-b1-structures-group) — yet it is *not* the same [group](#def-b1-structures-group) as the rotations $\mathbb U_4$ of [Example 7.15](#ex-b1-structures-order): there, $\iu$ has [order](#def-b1-structures-order) $4$, while here every element has [order](#def-b1-structures-order) $\leq 2$. Two [groups](#def-b1-structures-group) of the same size can thus have genuinely different multiplication structures — the figure below displays both tables side by side. This four-element [group](#def-b1-structures-group) returns as $\{\pm1\} \times \{\pm1\}$, and [Exercise 7.7](#exo-b1-structures-7) explains why any [group](#def-b1-structures-group) with all squares trivial must, like this one, be [abelian](#def-b1-structures-group).

![Two groups with four elements: U_4 = \e, , -1, - \ (left) and the rectangle group (right), with the identity’s positions shaded. On the left the identity meanders (one element of order 4 generates everything); on the right it fills the diagonal (every element squares to e). No relabeling can turn one table into the other: the groups are not isomorphic.](https://one-course.com/images/onecourse/chapters/math-3/b1-structures/fig-b3780f21ef36.svg)

*Two [groups](#def-b1-structures-group) with four elements: $\mathbb U_4 = \{e, \iu,
-1, -\iu\}$ (left) and the rectangle [group](#def-b1-structures-group) (right), with the identity’s positions shaded. On the left the identity meanders (one element of [order](#def-b1-structures-order) $4$ generates everything); on the right it fills the diagonal (every element squares to $e$). No relabeling can turn one table into the other: the [groups](#def-b1-structures-group) are not isomorphic.*

**Definition 7.7 (Subgroup).**

A subset $H$ of a [group](#def-b1-structures-group) $G$ is a *subgroup* (written $H \leq G$) when it contains $e$, is stable under the law and under inversion. Then $H$ is itself a [group](#def-b1-structures-group).

*Criterion:* a nonempty $H \subseteq G$ is a subgroup if and only if

$$
\forall x, y \in H, \quad x y^{-1} \in H .
$$

**Proof of the criterion.** A [subgroup](#def-b1-structures-subgroup) obviously satisfies it. Conversely, let $H \neq \emptyset$ satisfy it, and pick $x_0 \in H$. Then $e = x_0 x_0^{-1} \in H$; for $y \in H$, $y^{-1} = e\,y^{-1} \in H$; and for $x, y \in H$, $xy =
x (y^{-1})^{-1} \in H$. ∎

**Example 7.8.**

$\mathbb{U}_n \leq (\C^*, \times)$: nonempty, and for $z, w \in
\mathbb{U}_n$, $(zw^{-1})^n = z^n (w^n)^{-1} = 1$. The [subgroups](#def-b1-structures-subgroup) of $(\Z, +)$ are exactly the $n\Z$ (proved in [Theorem 6.4](https://one-course.com/books/math/3/en/chapter/6-integer-arithmetic#thm-b1-arith-gcd)). An intersection of [subgroups](#def-b1-structures-subgroup) is always a [subgroup](#def-b1-structures-subgroup), but a union almost never is ([Exercise 7.6](#exo-b1-structures-6)).

**Remark 7.9 (Common pitfalls with structures).**

1. *Stability under the law is not enough.* $\N$ is stable under addition inside $\Z$ , contains $0$ , yet is no [subgroup](#def-b1-structures-subgroup) : inverses are missing. The criterion $xy^{-1} \in H$ tests everything at once — but only after checking $H \neq \emptyset$ .
2. *Nonabelian reflexes.* In a general [group](#def-b1-structures-group) , $(ab)^2 =  abab$ , which is $a^2b^2$ only when $a$ and $b$ commute; likewise $(ab)^{-1} = b^{-1}a^{-1}$ , [order](#def-b1-structures-order) reversed. Every identity imported from school algebra must be re-derived from the axioms or flagged as commutative.
3. *[Kernel](#def-b1-structures-morphism) versus image.* $\ker f$ lives in the *source* , $\operatorname{im} f$ in the target; “ $f$ [injective](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-inj) iff $\ker f$ trivial” ( [Proposition 7.11](#prop-b1-structures-kernel) ) has no analogue with the image ( $\operatorname{im} f = G'$ is surjectivity).
4. *[Rings](#def-b1-structures-ring) are not [groups](#def-b1-structures-group) for $\times$.* In a [ring](#def-b1-structures-ring) , most elements need not be invertible, and cancellation by $a$ requires $a$ to be a unit or the [ring](#def-b1-structures-ring) to be an [integral domain](#def-b1-structures-field) : in $\Z/12\Z$ , $\overline3\,\overline2 =  \overline3\,\overline6$ yet $\overline2 \neq \overline6$ ( [Example 7.27](#ex-b1-structures-zncomputation) ).

**Definition 7.10 (Group morphism).**

Let $(G, *)$ and $(G', \star)$ be [groups](#def-b1-structures-group). A [map](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-map) $f \colon G \to G'$ is a *morphism* when

$$
\forall x, y \in G, \qquad f(x * y) = f(x) \star f(y).
$$

Then $f(e_G) = e_{G'}$ and $f(x^{-1}) = f(x)^{-1}$. The *kernel* and *image* of $f$ are

$$
\ker f = f^{-1}(\{e_{G'}\}) \leq G,
\qquad
\operatorname{im} f = f(G) \leq G' .
$$

A [bijective](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-inj) morphism is an *isomorphism*; its inverse [map](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-map) is then automatically a morphism.

**Proof of the assertions.** $f(e) = f(e * e) = f(e)\star f(e)$, and cancelling $f(e)$ gives $e_{G'} = f(e)$. Then $f(x)\star f(x^{-1}) = f(x x^{-1}) = e_{G'}$ identifies $f(x^{-1})$ as the inverse. [Kernel](#def-b1-structures-morphism): $e \in \ker f$; if $x, y \in \ker f$, $f(xy^{-1}) = f(x)f(y)^{-1} = e$; the criterion applies. Image: same criterion with $f(x)f(y)^{-1} = f(xy^{-1})$. Inverse of an isomorphism: for $u, v \in G'$, write $u = f(x)$, $v =
f(y)$; then $f^{-1}(u \star v) = f^{-1}(f(xy)) = xy =
f^{-1}(u) f^{-1}(v)$. ∎

**Proposition 7.11 (Injectivity via the kernel).**

A [group](#def-b1-structures-group) [morphism](#def-b1-structures-morphism) $f$ is [injective](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-inj) if and only if $\ker f =
\{e\}$.

**Proof.** If $f$ is [injective](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-inj), $\ker f$ can only contain the one [preimage](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-map) of $e_{G'}$, which is $e$. Conversely, if $\ker f = \{e\}$ and $f(x) =
f(y)$, then $f(xy^{-1}) = f(x) f(y)^{-1} = e_{G'}$, so $xy^{-1} = e$, i.e. $x = y$. ∎

**Example 7.12.**

$\exp \colon (\R, +) \to (\R_+^*, \times)$ is a [morphism](#def-b1-structures-morphism) ($\eu^{x+y} = \eu^x \eu^y$), [bijective](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-inj) ([Proposition 4.1](https://one-course.com/books/math/3/en/chapter/4-standard-functions#prop-b1-functions-expln)): the additive and multiplicative structures are isomorphic — the historical raison d’être of logarithms. Another [morphism](#def-b1-structures-morphism): $\theta \mapsto \eu^{\iu\theta}$ from $(\R, +)$ onto the unit circle $(\mathbb{U}, \times)$, with [kernel](#def-b1-structures-morphism) $2\pi\Z$.

**Example 7.13 (The sign morphism).**

The [map](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-map) $s \colon (\R^*, \times) \to (\{\pm1\}, \times)$ sending $x$ to its sign is a [morphism](#def-b1-structures-morphism): the sign of a product is the product of the signs. Its [kernel](#def-b1-structures-morphism) is $\intoo0{+\infty}$ (a [subgroup](#def-b1-structures-subgroup), as [Definition 7.10](#def-b1-structures-morphism) promises), its image all of $\{\pm1\}$: [surjective](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-inj), massively [non-injective](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-inj). Two general lessons in miniature. First, a [morphism](#def-b1-structures-morphism) may crush information: $s$ remembers nothing of $x$ but one bit, and that is its virtue — sign arguments are exactly the computations that factor through $s$. Second, [morphisms](#def-b1-structures-morphism) to $\{\pm1\}$ are the simplest “invariants”: the signature of [permutations](https://one-course.com/books/math/3/en/chapter/2-counting#def-b1-counting-objects), built in this chapter’s weekend problem, is the same phenomenon on the [group](#def-b1-structures-group) $\mathfrak S_n$, and the parity arguments it powers all descend through such a two-valued [morphism](#def-b1-structures-morphism).

**Definition 7.14 (Powers, order of an element).**

In a [group](#def-b1-structures-group) $G$ (multiplicative notation), set $x^0 = e$, $x^{k+1} =
x^k x$ and $x^{-k} = (x^k)^{-1}$ for $k \in \N$; then $x^{k+l} = x^k
x^l$ for all $k, l \in \Z$, so $k \mapsto x^k$ is a [morphism](#def-b1-structures-morphism) $(\Z,
+) \to G$ whose image $\langle x \rangle = \{x^k : k \in \Z\}$ is a [subgroup](#def-b1-structures-subgroup), the [subgroup](#def-b1-structures-subgroup) *generated* by $x$. The *order* of $x$ is the least $m \geq
1$ with $x^m = e$ if one exists (then $\langle x\rangle = \{e, x,
\dots, x^{m-1}\}$ has exactly $m$ elements, and $x^k = e \iff m
\mid k$), and $\infty$ otherwise.

**Example 7.15.**

In $(\C^*, \times)$: $\iu$ has [order](#def-b1-structures-order) $4$, with $\langle \iu \rangle
= \{1, \iu, -1, -\iu\} = \mathbb{U}_4$; more generally $\omega =
\eu^{2\iu\pi/n}$ has [order](#def-b1-structures-order) $n$ and $\langle\omega\rangle =
\mathbb{U}_n$. In $(\Z, +)$, every $x \neq 0$ has infinite [order](#def-b1-structures-order). Why the claims in the definition hold: if $x$ has [order](#def-b1-structures-order) $m$, divide any $k$ by $m$ ($k = mq + r$, $0 \leq r < m$, [Theorem 6.2](https://one-course.com/books/math/3/en/chapter/6-integer-arithmetic#thm-b1-arith-division)): $x^k = (x^m)^q x^r = x^r$, so the powers cycle with period $m$, the listed elements are pairwise distinct by minimality of $m$, and $x^k = e$ forces $r = 0$. [Orders](#def-b1-structures-order) of [permutations](https://one-course.com/books/math/3/en/chapter/2-counting#def-b1-counting-objects) are computed in the weekend problem below.

**Example 7.16 (Orders inside U12\mathbb U_{12}U12​).**

What is the [order](#def-b1-structures-order) of $\omega^k$ in $\mathbb U_n$, for $\omega =
\eu^{2\iu\pi/n}$? One has $(\omega^k)^m = 1$ iff $n \mid km$, and writing $d = \gcd(n, k)$, $n = dn'$, $k = dk'$ with $\gcd(n', k')
= 1$: $n \mid km \iff n' \mid k'm \iff n' \mid m$ (Gauss’s lemma, [Theorem 6.8](https://one-course.com/books/math/3/en/chapter/6-integer-arithmetic#thm-b1-arith-gauss)). The least such $m \geq 1$ is $n' = \frac{n}{\gcd(n,k)}$. In $\mathbb U_{12}$ for instance, $\omega^8$ has [order](#def-b1-structures-order) $\frac{12}{\gcd(12,8)} = 3$ (indeed $\omega^8 = \eu^{4\iu\pi/3} \in \mathbb U_3$), while $\omega^5$ has [order](#def-b1-structures-order) $12$: it generates the whole [group](#def-b1-structures-group), though it is not the “standard” generator. Counting the generators — the $k$ with $\gcd(k, n) = 1$ — recovers the [coprime](https://one-course.com/books/math/3/en/chapter/6-integer-arithmetic#cor-b1-arith-bezout) counts of [Example 2.25](https://one-course.com/books/math/3/en/chapter/2-counting#ex-b1-counting-coprime): [group](#def-b1-structures-group) theory and counting meet.

## 7.3 Rings and fields

**Definition 7.17 (Ring).**

A *ring* $(A, +, \times)$ is a [set](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-sets) with two laws such that: $(A, +)$ is an [abelian group](#def-b1-structures-group) (identity $0$); $\times$ is associative with an identity $1$; and $\times$ distributes over $+$ on both sides. The ring is *commutative* when $\times$ is. An element $a$ is *invertible* (a *unit*) when $ab = ba = 1$ for some $b$; the units form a [group](#def-b1-structures-group) $(A^\times, \times)$.

**Proof that the units form a group.** Stability: if $a, a'$ are units with inverses $b, b'$, then

$$
(aa')(b'b) = a(a'b')b = a\,1\,b = ab = 1,
\qquad (b'b)(aa') = 1
$$

symmetrically, so $aa'$ is a unit. The element $1$ is a unit (its own inverse), associativity is inherited from $A$, and the inverse $b$ of a unit $a$ is itself a unit (with inverse $a$). So $(A^\times, \times)$ satisfies all [group](#def-b1-structures-group) axioms. Every [group](#def-b1-structures-group) in this book that is not built from [permutations](https://one-course.com/books/math/3/en/chapter/2-counting#def-b1-counting-objects) arises this way: $\Q^* = \Q^\times$, $\R^*$, $\C^*$, the units of $\Z/n\Z$ below, and later the invertible matrices ([Chapter 21](https://one-course.com/books/math/3/en/chapter/21-matrices#ch-b1-matrices)). ∎

**Example 7.18.**

$\Z, \Q, \R, \C$ are commutative [rings](#def-b1-structures-ring); $\Z^\times = \{1, -1\}$, $\Q^\times = \Q^*$. Later: polynomial [rings](#def-b1-structures-ring) $K[X]$ ([Chapter 8](https://one-course.com/books/math/3/en/chapter/8-polynomials#ch-b1-poly)), matrix [rings](#def-b1-structures-ring) (non-commutative, [Chapter 21](https://one-course.com/books/math/3/en/chapter/21-matrices#ch-b1-matrices)), and $\Z/n\Z$ below. In every [ring](#def-b1-structures-ring), $0 \times
a = 0$ (from distributivity: $0a = (0+0)a = 0a + 0a$), and $(-1)a = -a$.

**Example 7.19 (Idempotents: new phenomena in new rings).**

In $\Z$, the equation $x^2 = x$, i.e. $x(x - 1) = 0$, has only the solutions $0$ and $1$. In $\Z/6\Z$, testing all classes: $\overline0^2 = \overline0$, $\overline1^2 = \overline1$, $\overline3^2 = \overline9 = \overline3$ and $\overline4^2 =
\overline{16} = \overline4$ — *four* idempotents. The two exotic ones come from zero divisors: $\overline3\,(\overline3 -
\overline1) = \overline3 \times \overline2 = \overline6 =
\overline0$ with neither factor zero. Such computations calibrate one’s instincts: familiar facts about equations survive in [integral domains](#def-b1-structures-field) and [fields](#def-b1-structures-field), but a general [ring](#def-b1-structures-ring) can and does behave differently — see also the Boolean [rings](#def-b1-structures-ring) of [Exercise 7.10](#exo-b1-structures-10), where *every* element is idempotent.

**Proposition 7.20 (Binomial theorem in a commutative ring).**

If $a, b$ are elements of a commutative [ring](#def-b1-structures-ring) (more generally, if $ab = ba$), then for $n \in \N$:

$$
(a+b)^n = \sum_{k=0}^n \binom nk a^k b^{n-k},
\qquad
a^n - b^n = (a - b) \sum_{k=0}^{n-1} a^k b^{\,n-1-k} .
$$

**Proof.** The proofs of [Theorem 2.16](https://one-course.com/books/math/3/en/chapter/2-counting#thm-b1-counting-binomial) and of the geometric identity use only associativity, commutativity of the two elements, and distributivity — they apply verbatim. ∎

**Example 7.21 (The binomial theorem in an unfamiliar ring).**

Two quick payoffs of the generality. In $\Z/p\Z$ ($p$ [prime](https://one-course.com/books/math/3/en/chapter/6-integer-arithmetic#def-b1-arith-prime)), the middle [binomial coefficients](https://one-course.com/books/math/3/en/chapter/2-counting#def-b1-counting-objects) vanish ([Theorem 6.23](https://one-course.com/books/math/3/en/chapter/6-integer-arithmetic#thm-b1-arith-fermat)’s first step), so the theorem collapses to the *freshman’s dream*

$$
(a + b)^p = a^p + b^p \qquad \text{in } \Z/p\Z ,
$$

a genuine identity there, however criminal it looks over $\R$. And in any commutative [ring](#def-b1-structures-ring) containing an element $\varepsilon$ with $\varepsilon^2 = 0$, the theorem truncates: $(a + \varepsilon)^n = a^n + n\,a^{n-1}\varepsilon$, all higher terms carrying a factor $\varepsilon^2 = 0$. The coefficient $n\,a^{n-1}$ of $\varepsilon$ is the derivative of $x^n$ — no accident, and a first hint that derivatives are algebra as much as analysis (compare the formal derivative of [Chapter 8](https://one-course.com/books/math/3/en/chapter/8-polynomials#ch-b1-poly)).

**Definition 7.22 (Integral domain, field).**

A commutative [ring](#def-b1-structures-ring) $A \neq \{0\}$ is an *integral domain* when it has no zero divisors: $ab = 0
\implies a = 0$ or $b = 0$. It is a *field* when every nonzero element is invertible. Every field is an integral domain ($ab = 0$ and $a \neq 0$ give $b = a^{-1}ab = 0$).

**Example 7.23.**

$\Q$, $\R$, $\C$ are [fields](#def-b1-structures-field); $\Z$ is an [integral domain](#def-b1-structures-field) but not a [field](#def-b1-structures-field). In an [integral domain](#def-b1-structures-field), cancellation holds for $\times$: $ab =
ac$ and $a \neq 0$ imply $b = c$.

## 7.4 The ring $\Z/n\Z$

**Definition 7.24.**

Fix $n \in \N^*$. The [congruence](https://one-course.com/books/math/3/en/chapter/6-integer-arithmetic#def-b1-arith-congruence) classes mod $n$ ([Example 1.32](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#ex-b1-logic-congruence)) form a [set](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-sets) $\Z/n\Z$ of $n$ elements, written $\overline 0,
\overline 1, \dots, \overline{n-1}$. The operations

$$
\overline a + \overline b = \overline{a + b},
\qquad
\overline a \times \overline b = \overline{ab}
$$

are well defined — the classes of the results do not depend on the representatives, precisely because [congruence](https://one-course.com/books/math/3/en/chapter/6-integer-arithmetic#def-b1-arith-congruence) is compatible with $+$ and $\times$ ([Definition 6.18](https://one-course.com/books/math/3/en/chapter/6-integer-arithmetic#def-b1-arith-congruence)) — and make $\Z/n\Z$ a commutative [ring](#def-b1-structures-ring).

**Theorem 7.25 (Units of Z/nZ\Z/n\ZZ/nZ; the fields Z/pZ\Z/p\ZZ/pZ).**

1. $\overline a$ is invertible in $\Z/n\Z$ if and only if $\gcd(a, n) = 1$ .
2. $\Z/n\Z$ is a [field](#def-b1-structures-field) if and only if $n$ is [prime](https://one-course.com/books/math/3/en/chapter/6-integer-arithmetic#def-b1-arith-prime) .

**Proof.** (1) is [Proposition 6.20](https://one-course.com/books/math/3/en/chapter/6-integer-arithmetic#prop-b1-arith-invmod) rewritten with classes.

(2) If $n = p$ is [prime](https://one-course.com/books/math/3/en/chapter/6-integer-arithmetic#def-b1-arith-prime), every $\overline a \neq \overline 0$ has $p
\nmid a$, so $\gcd(a, p) = 1$: invertible by (1) — a [field](#def-b1-structures-field). If $n =
ab$ with $1 < a, b < n$, then $\overline a\, \overline b = \overline
n = \overline 0$ with $\overline a, \overline b \neq \overline 0$: zero divisors, so not even an [integral domain](#def-b1-structures-field); and $n = 1$ gives the zero [ring](#def-b1-structures-ring), excluded. ∎

**Example 7.26 (How many square roots of 111?).**

Solve $x^2 = \overline 1$ in $\Z/8\Z$ and in $\Z/7\Z$. Testing the eight classes mod $8$: $1^2 = 1$, $3^2 = 9 \equiv 1$, $5^2 = 25
\equiv 1$, $7^2 = 49 \equiv 1$ — *four* solutions $\{\overline1, \overline3, \overline5, \overline7\}$, even though the polynomial $X^2 - 1$ has degree $2$. In the [field](#def-b1-structures-field) $\Z/7\Z$, by contrast, $x^2 = \overline1$ means $(x - \overline1)(x +
\overline1) = \overline0$, and a [field](#def-b1-structures-field) has no zero divisors: $x =
\pm\overline1$, two solutions only. The failure mod $8$ is traceable: $(3-1)(3+1) = 2 \times 4 = 8 \equiv 0$ without either factor vanishing. Moral: the familiar rule “a degree-$d$ equation has at most $d$ roots” is a theorem about *[integral domains](#def-b1-structures-field)* ([Corollary 8.8](https://one-course.com/books/math/3/en/chapter/8-polynomials#cor-b1-poly-nroots) proves it over [fields](#def-b1-structures-field)); in [rings](#def-b1-structures-ring) with zero divisors it silently fails — which is exactly why the pairing proof of Wilson’s theorem ([Exercise 6.11](https://one-course.com/books/math/3/en/chapter/6-integer-arithmetic#exo-b1-arith-11)) needed $p$ [prime](https://one-course.com/books/math/3/en/chapter/6-integer-arithmetic#def-b1-arith-prime).

**Example 7.27 (Computing in Z/nZ\Z/n\ZZ/nZ).**

In $\Z/12\Z$: the units are $\overline 1, \overline 5, \overline 7,
\overline{11}$ (the classes [coprime](https://one-course.com/books/math/3/en/chapter/6-integer-arithmetic#cor-b1-arith-bezout) to $12$), and each is its own inverse ($5^2 = 25 \equiv 1$, $7^2 = 49 \equiv 1$, $11^2 = 121 \equiv
1$). The equation $\overline 3\, x = \overline 6$ has *three* solutions ($x \in \{\overline 2, \overline 6, \overline{10}\}$): without invertibility, no cancellation. In $\Z/11\Z$ by contrast, every equation $\overline a x = \overline b$ with $\overline a \neq
\overline 0$ has exactly one solution.

**Example 7.28 (Group axioms as a solving license).**

In the [group](#def-b1-structures-group) $\bigl((\Z/7\Z)^*, \times\bigr)$, solve $\overline
3\,x = \overline 5$. By [Proposition 7.5](#prop-b1-structures-rules) (3) the solution exists, is unique, and equals $\overline3^{-1}\,
\overline5$; since $\overline3 \times \overline5 = \overline{15}
= \overline1$, the inverse of $\overline 3$ is $\overline 5$, so

$$
x = \overline5 \times \overline5 = \overline{25} = \overline4,
\qquad\text{check: } \overline3 \times \overline4 =
\overline{12} = \overline5 .
$$

The point is less the answer than the guarantee: in a [group](#def-b1-structures-group), every such equation is solvable uniquely *before* any computation, so a solving procedure can never run into “no solution” or “several”. Compare $\overline3\,x = \overline6$ in $\Z/12\Z$ above, where the guarantee fails — knowing which structure one is in is knowing what one may take for granted.

**Example 7.29 (Direct products).**

If $G$ and $H$ are [groups](#def-b1-structures-group), the product [set](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-sets) $G \times H$ with the componentwise law $(g, h)(g', h') = (gg', hh')$ is a [group](#def-b1-structures-group): axioms are checked coordinate by coordinate, with identity $(e_G, e_H)$ and inverses $(g^{-1}, h^{-1})$. [Orders](#def-b1-structures-order) combine by the lcm: $(g, h)^m = (g^m, h^m)$ is the identity iff the [order](#def-b1-structures-order) of $g$ and the [order](#def-b1-structures-order) of $h$ both divide $m$. Thus in $\Z/2\Z
\times \Z/2\Z$ (additive) every nonzero element has [order](#def-b1-structures-order) $2$ — this is exactly the rectangle [group](#def-b1-structures-group) of [Example 7.6](#ex-b1-structures-klein) in coordinates — while $\Z/4\Z$ has an element of [order](#def-b1-structures-order) $4$: a second, computation-free proof that the two [groups](#def-b1-structures-group) of size $4$ are not isomorphic (an isomorphism preserves [orders](#def-b1-structures-order)). Products are the easiest way to manufacture new [groups](#def-b1-structures-group) from old, and the plane $\R^2 = \R \times
\R$ of [Chapter 18](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#ch-b1-vspaces) is the construction’s most important instance.

**Remark 7.30 (Fermat, structurally).**

In the [field](#def-b1-structures-field) $\Z/p\Z$, the nonzero classes form a multiplicative [group](#def-b1-structures-group) with $p - 1$ elements, and Fermat’s little theorem ([Theorem 6.23](https://one-course.com/books/math/3/en/chapter/6-integer-arithmetic#thm-b1-arith-fermat)) says: every element $x$ of this [group](#def-b1-structures-group) satisfies $x^{p-1} = \overline 1$. This is an instance of a general fact about finite [groups](#def-b1-structures-group) (Lagrange’s theorem), proved in the second year; the pairing proof of Wilson’s theorem ([Exercise 6.11](https://one-course.com/books/math/3/en/chapter/6-integer-arithmetic#exo-b1-arith-11)) already had this group-theoretic flavor.

**Remark 7.31 (Interlude: what abstraction buys).**

It is fair to ask what was gained by proving, say, [Proposition 7.2](#prop-b1-structures-unique) for an abstract law rather than for numbers. The answer is leverage. That two-line argument now covers, at once: inverses of functions under composition ([Theorem 1.24](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#thm-b1-logic-inverse), whose uniqueness proof it repeats word for word), inverses mod $n$ ([Proposition 6.20](https://one-course.com/books/math/3/en/chapter/6-integer-arithmetic#prop-b1-arith-invmod)), inverses of nonzero reals, of units in any [ring](#def-b1-structures-ring), and — sight unseen — of the invertible matrices of [Chapter 21](https://one-course.com/books/math/3/en/chapter/21-matrices#ch-b1-matrices), where uniqueness of $A^{-1}$ will not need a single line of proof. The same economy holds for [Proposition 7.11](#prop-b1-structures-kernel) (one injectivity criterion, reused for linear [maps](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-map) in [Chapter 20](https://one-course.com/books/math/3/en/chapter/20-linear-maps#ch-b1-linmaps)) and for the [subgroup](#def-b1-structures-subgroup) criterion. Abstraction here is not generality for its own sake: it is the refusal to prove the same lemma five times under five names. The price — keeping track of which axioms each [statement](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-statement) really used — is exactly what the exercises of this chapter train.

**Remark 7.32 (Where this chapter is used).**

The vocabulary of this chapter is the grammar of the rest of the volume. [Rings](#def-b1-structures-ring) and [fields](#def-b1-structures-field) organize [Chapter 8](https://one-course.com/books/math/3/en/chapter/8-polynomials#ch-b1-poly) ($K[X]$ is a [ring](#def-b1-structures-ring) imitating $\Z$) and [Chapter 9](https://one-course.com/books/math/3/en/chapter/9-rational-fractions#ch-b1-fractions) ($K(X)$ is its [field](#def-b1-structures-field) of fractions); vector spaces ([Chapter 18](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#ch-b1-vspaces)) are [abelian groups](#def-b1-structures-group) with a [field](#def-b1-structures-field) acting on them; matrices ([Chapter 21](https://one-course.com/books/math/3/en/chapter/21-matrices#ch-b1-matrices)) form the volume’s first seriously non-commutative [ring](#def-b1-structures-ring), and their invertible elements a [group](#def-b1-structures-group) whose study is linear algebra itself. [Morphisms](#def-b1-structures-morphism) and [kernels](#def-b1-structures-morphism) return as linear [maps](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-map) and null spaces in [Chapter 20](https://one-course.com/books/math/3/en/chapter/20-linear-maps#ch-b1-linmaps) — [Proposition 7.11](#prop-b1-structures-kernel) *is* the injectivity criterion of that chapter, proved once and for all here. The [symmetric group](#ex-b1-structures-groups), star of the weekend problem below, supplies the signature on which determinants are built in [Chapter 22](https://one-course.com/books/math/3/en/chapter/22-determinants-and-linear-systems#ch-b1-det).

## 7.5 Exercises

**Exercise 7.1 ★.**

On $E = \R \setminus \{1\}$, define $x * y = x + y - xy$. Prove that $(E, *)$ is an [abelian group](#def-b1-structures-group). *(Identify the identity and the inverse of $x$; check stability: why is $x * y \neq 1$?)*

**Solution of Exercise 7.1.**

*Stability:* $x * y = 1 \iff x + y - xy = 1 \iff (1-x)(1-y) = 0$, impossible for $x, y \neq 1$. Indeed the key identity is

$$
1 - x * y = (1 - x)(1 - y):
$$

the [map](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-map) $\varphi(x) = 1 - x$ sends $(E, *)$ to $(\R^*, \times)$ with $\varphi(x * y) = \varphi(x)\varphi(y)$ — a [bijective](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-inj) [morphism](#def-b1-structures-morphism). All axioms now transport: associativity and commutativity follow from those of $\times$; the identity is $\varphi^{-1}(1) = 0$ (check: $x *
0 = x$); the inverse of $x$ is $\varphi^{-1}\bigl((1-x)^{-1}\bigr) =
1 - \frac{1}{1-x} = \frac{x}{x - 1}$ (which is $\neq 1$). So $(E, *)$ is an [abelian group](#def-b1-structures-group).

**Exercise 7.2 ★.**

Which of the following are [groups](#def-b1-structures-group)?

1. $(\intoo{0}{+\infty}, \times)$ ;
2. $(\{-1, 0, 1\}, +)$ ;
3. $(\Q^*, \times)$ ;
4. the [set](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-sets) of odd integers under addition.

**Solution of Exercise 7.2.**

1. Yes: product of positives is positive, identity $1$ , inverse $\frac 1x$ , associativity inherited from $\R^*$ .
2. No: not stable ( $1 + 1 = 2 \notin \{-1,0,1\}$ ).
3. Yes: the standard example.
4. No: not stable (odd $+$ odd $=$ even), and no identity ( $0$ is even).

**Exercise 7.3 ★.**

Write the composition table of the [symmetric group](#ex-b1-structures-groups) $\mathfrak{S}_3$ of $\{1,2,3\}$ (six bijections: identity, three transpositions, two $3$-cycles), and exhibit two elements that do not commute.

**Solution of Exercise 7.3.**

Write $\mathrm{id}$, the transpositions $\tau_{12}, \tau_{13},
\tau_{23}$ (swapping the two named points), and the cycles $c =
(1\,2\,3)$ (i.e. $1 \mapsto 2 \mapsto 3 \mapsto 1$) and $c^2 =
(1\,3\,2)$. The table of $\sigma\rho$ (row $\sigma$, column $\rho$, apply $\rho$ first):

| $\sigma\backslash\rho$ | $\mathrm{id}$ | $c$ | $c^2$ | $\tau_{12}$ | $\tau_{13}$ | $\tau_{23}$ |
| --- | --- | --- | --- | --- | --- | --- |
| $\mathrm{id}$ | $\mathrm{id}$ | $c$ | $c^2$ | $\tau_{12}$ | $\tau_{13}$ | $\tau_{23}$ |
| $c$ | $c$ | $c^2$ | $\mathrm{id}$ | $\tau_{13}$ | $\tau_{23}$ | $\tau_{12}$ |
| $c^2$ | $c^2$ | $\mathrm{id}$ | $c$ | $\tau_{23}$ | $\tau_{12}$ | $\tau_{13}$ |
| $\tau_{12}$ | $\tau_{12}$ | $\tau_{23}$ | $\tau_{13}$ | $\mathrm{id}$ | $c^2$ | $c$ |
| $\tau_{13}$ | $\tau_{13}$ | $\tau_{12}$ | $\tau_{23}$ | $c$ | $\mathrm{id}$ | $c^2$ |
| $\tau_{23}$ | $\tau_{23}$ | $\tau_{13}$ | $\tau_{12}$ | $c^2$ | $c$ | $\mathrm{id}$ |

Non-commuting pair: $\tau_{12}\tau_{13} = c^2$ while $\tau_{13}\tau_{12} = c$. (To check one entry: $\tau_{12}\tau_{13}$ sends $1 \xmapsto{\tau_{13}} 3
\xmapsto{\tau_{12}} 3$, $3 \mapsto 1 \mapsto 2$, $2 \mapsto 2 \mapsto
1$: that is $1 \mapsto 3 \mapsto 2 \mapsto 1$, the cycle $c^2 =
(1\,3\,2)$.)

**Exercise 7.4 ★.**

Prove that $H = \{z \in \C^* : \abs z = 1\}$ is a [subgroup](#def-b1-structures-subgroup) of $(\C^*,
\times)$, and that $\R_+^*$ is another; is $H \cup \R_+^*$ a [subgroup](#def-b1-structures-subgroup)?

**Solution of Exercise 7.4.**

$H$: $1 \in H$; for $z, w \in H$, $\abs{zw^{-1}} = \abs z / \abs w =
1$: the criterion applies. $\R_+^*$: same, $\abs{xy^{-1}}$ replaced by positivity. Union: $\iu \in H$ and $2 \in \R_+^*$, but $2\iu$ has [modulus](https://one-course.com/books/math/3/en/chapter/3-complex-numbers#def-b1-complex-field) $2 \neq 1$ and is not a positive real: $2\iu \notin H \cup
\R_+^*$, so the union is not stable — not a [subgroup](#def-b1-structures-subgroup) (as predicted by [Exercise 7.6](#exo-b1-structures-6), neither [subgroup](#def-b1-structures-subgroup) contains the other).

**Exercise 7.5 ★★.**

Let $f \colon (\R, +) \to (\C^*, \times)$, $\theta \mapsto
\eu^{\iu\theta}$. Prove that $f$ is a [morphism](#def-b1-structures-morphism), compute $\ker f$ and $\operatorname{im} f$, and deduce from [Proposition 7.11](#prop-b1-structures-kernel) that $f$ is not [injective](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-inj). Restrict the domain to make it [injective](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-inj) on an interval as large as possible.

**Solution of Exercise 7.5.**

[Morphism](#def-b1-structures-morphism): $\eu^{\iu(\theta + \varphi)} =
\eu^{\iu\theta}\eu^{\iu\varphi}$ ([Theorem 3.7](https://one-course.com/books/math/3/en/chapter/3-complex-numbers#thm-b1-complex-funceq)). [Kernel](#def-b1-structures-morphism): $\eu^{\iu\theta} = 1 \iff \theta \in 2\pi\Z$, so $\ker f =
2\pi\Z \neq \{0\}$: not [injective](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-inj). Image: every unit complex number is $\eu^{\iu\theta}$ for some $\theta$ (polar form), so $\operatorname{im} f = \mathbb{U}$, the unit circle. The restriction of $f$ to a half-open interval of length $2\pi$, such as $\intco{0}{2\pi}$ or $\intoc{-\pi}{\pi}$, is [injective](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-inj) (two angles with the same image differ by a multiple of $2\pi$, and only one representative of each class fits in the interval); no interval of greater length works, since it contains two points at distance $2\pi$.

**Exercise 7.6 ★★.**

Let $H, K$ be [subgroups](#def-b1-structures-subgroup) of $G$. Prove that $H \cap K$ is a [subgroup](#def-b1-structures-subgroup), and that $H \cup K$ is a [subgroup](#def-b1-structures-subgroup) *only* when $H \subseteq K$ or $K \subseteq H$. *(If $h \in H \setminus K$ and $k \in K
\setminus H$, where can $hk$ live?)*

**Solution of Exercise 7.6.**

Intersection: $e \in H \cap K$, and $x, y \in H \cap K$ gives $xy^{-1}$ in both $H$ and $K$. Union: if $H \subseteq K$ the union is $K$, a [subgroup](#def-b1-structures-subgroup) (and symmetrically). Conversely, suppose neither inclusion holds: pick $h \in H \setminus K$ and $k \in K \setminus
H$, and suppose $H \cup K$ were a [subgroup](#def-b1-structures-subgroup); then $hk \in H \cup K$. If $hk \in H$, then $k = h^{-1}(hk) \in H$: contradiction. If $hk \in
K$, then $h = (hk)k^{-1} \in K$: contradiction. So $H \cup K$ is not a [subgroup](#def-b1-structures-subgroup).

**Exercise 7.7 ★★.**

A [group](#def-b1-structures-group) $G$ satisfies $x^2 = e$ for all $x \in G$. Prove that $G$ is [abelian](#def-b1-structures-group). *(Expand $(xy)^2$.)*

**Solution of Exercise 7.7.**

Note first that $x^2 = e$ means $x^{-1} = x$ for every $x$. Then for $x, y \in G$:

$$
xy = (xy)^{-1} = y^{-1} x^{-1} = yx ,
$$

using [Proposition 7.5](#prop-b1-structures-rules) (2). So $G$ is [abelian](#def-b1-structures-group).

**Exercise 7.8 ★★.**

In $\Z/18\Z$: list the units and find the inverse of $\overline 5$; solve $\overline 5\, x = \overline 7$; solve $\overline 6\, x =
\overline 3$ and $\overline 6\, x = \overline{12}$.

**Solution of Exercise 7.8.**

Units of $\Z/18\Z$: classes [coprime](https://one-course.com/books/math/3/en/chapter/6-integer-arithmetic#cor-b1-arith-bezout) to $18 = 2 \times 3^2$: $\overline 1, \overline 5, \overline 7, \overline{11}, \overline{13},
\overline{17}$. Inverse of $\overline 5$: $5 \times 11 = 55 = 3\times
18 + 1$, so $\overline 5^{-1} = \overline{11}$.

$\overline 5 x = \overline 7$: multiply by $\overline{11}$: $x =
\overline{77} = \overline 5$ (since $77 = 4\times 18 + 5$). Unique solution.

$\overline 6 x = \overline 3$: the equation $6x \equiv 3 \pmod{18}$ means $18 \mid 6x - 3$. But $6x - 3 = 3(2x - 1)$ is odd, while $18$ is even: an even number cannot divide an odd one. No solution.

$\overline 6 x = \overline{12}$: $6x \equiv 12 \pmod{18} \iff x
\equiv 2 \pmod 3$: solutions $x \in \{\overline 2, \overline 5,
\overline 8, \overline{11}, \overline{14}, \overline{17}\}$ — six of them.

**Exercise 7.9 ★★.**

Prove that the [set](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-sets) $\Z[\sqrt 2] = \{a + b\sqrt 2 : a, b \in \Z\}$ is a [ring](#def-b1-structures-ring) (a subring of $\R$), and that $1 + \sqrt 2$ is a unit of it with infinitely many distinct powers — so $\Z[\sqrt 2]^\times$ is infinite, unlike $\Z^\times$.

**Solution of Exercise 7.9.**

$\Z[\sqrt 2]$ contains $0$ and $1$, and is stable under subtraction and product:

$$
(a + b\sqrt 2)(c + d\sqrt 2) = (ac + 2bd) + (ad + bc)\sqrt 2 ,
$$

so it is a subring of $\R$ (commutativity, associativity, distributivity are inherited). Unit: $(1 + \sqrt 2)(-1 + \sqrt 2) =
2 - 1 = 1$, so $1 + \sqrt 2$ is invertible with inverse $\sqrt 2 - 1
\in \Z[\sqrt 2]$. Its powers $(1 + \sqrt 2)^n$ are strictly increasing (the base is $> 1$), hence pairwise distinct, and each is a unit ($\bigl((1+\sqrt2)^n\bigr)^{-1} = (\sqrt 2 - 1)^n$): the [group](#def-b1-structures-group) of units is infinite.

**Exercise 7.10 ★★★.**

(Boolean [rings](#def-b1-structures-ring)) Let $A$ be a [ring](#def-b1-structures-ring) in which $x^2 = x$ for every $x$. Prove that $x + x = 0$ for all $x$, and that $A$ is commutative. *(Expand $(x+x)^2$ and $(x+y)^2$.)* Give an example of such a [ring](#def-b1-structures-ring) with $\mathcal{P}(E)$, taking the symmetric difference as addition and intersection as multiplication.

**Solution of Exercise 7.10.**

$x + x = (x + x)^2 = x^2 + x^2 + x^2 + x^2 = 4x^2 = 4x$ — so $2x =
4x$, giving $2x = 0$, i.e. $x + x = 0$ (each element is its own additive inverse). Then

$$
x + y = (x+y)^2 = x^2 + xy + yx + y^2 = x + xy + yx + y ,
$$

so $xy + yx = 0$, i.e. $xy = -yx = yx$ (using $-z = z$). Hence $A$ is commutative.

Example: on $\mathcal{P}(E)$, define $A + B = (A \cup B) \setminus (A
\cap B)$ (symmetric difference) and $A \times B = A \cap B$. One checks: $(\mathcal{P}(E), +)$ is an [abelian group](#def-b1-structures-group) with identity $\emptyset$ and each [set](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-sets) its own inverse; $\cap$ is associative, commutative, with identity $E$; distributivity $A \cap (B + C) = (A
\cap B) + (A \cap C)$ holds (an element lies in the left side iff it is in $A$ and in exactly one of $B, C$). And $A \cap A = A$: every element is idempotent, as required.

**Exercise 7.11 ★★★.**

Let $G$ be a [group](#def-b1-structures-group) in which, for some fixed $n \geq 1$, $(xy)^n =
x^n y^n$, $(xy)^{n+1} = x^{n+1}y^{n+1}$ and $(xy)^{n+2} =
x^{n+2}y^{n+2}$ for all $x, y$. Prove that $G$ is [abelian](#def-b1-structures-group). *(From the three identities, derive first $y^n x = x y^n$, then $y^{n+1} x = x y^{n+1}$, and conclude.)*

**Solution of Exercise 7.11.**

Write the hypothesis for $n$ and $n+1$:

$$
(xy)^{n+1} = x^{n+1} y^{n+1}
\quad\text{and}\quad
(xy)^{n+1} = (xy)(xy)^n = xy\,x^n y^n .
$$

Equating: $x^{n+1} y^{n+1} = x\,y\,x^n\,y^n$; cancel $x$ on the left and $y^n$ on the right: $x^n y = y x^n$. The same computation one degree higher ($n+1$ and $n+2$) gives $x^{n+1} y = y x^{n+1}$. Then

$$
y\,x^{n+1} = x^{n+1} y = x\,(x^n y) = x\,y\,x^n ,
$$

and cancelling $x^n$ on the right of $y x \cdot x^n = x y \cdot x^n$: $yx = xy$. So $G$ is [abelian](#def-b1-structures-group).

**Exercise 7.12 ★★.**

1. Determine all [group](#def-b1-structures-group) [morphisms](#def-b1-structures-morphism) from $(\Z, +)$ to $(\Z, +)$ .
2. Prove that the only [group](#def-b1-structures-group) [morphism](#def-b1-structures-morphism) from $(\Q, +)$ to $(\Z, +)$ is the zero [morphism](#def-b1-structures-morphism) . *(For $x \in \Q$ and $n \in \N^*$, compare $f(x)$ and $n\,f(x/n)$.)*

**Solution of Exercise 7.12.**

1. Let $f \colon \Z \to \Z$ be additive and $a = f(1)$ . By induction $f(k) = ka$ for $k \in \N$ , and $f(-k) = -f(k) =  -ka$ : so $f$ is the multiplication by $a$ . Conversely every [map](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-map) $k \mapsto ak$ is a [morphism](#def-b1-structures-morphism) : the [morphisms](#def-b1-structures-morphism) $(\Z,+) \to (\Z,+)$ are exactly the multiplications by a fixed integer.
2. Let $f \colon \Q \to \Z$ be a [morphism](#def-b1-structures-morphism), $x \in \Q$ and $n \in \N^*$. Then $$f(x) = f\Bigl(\underbrace{\tfrac xn + \dots +  \tfrac xn}_{n}\Bigr) = n\,f\Bigl(\frac xn\Bigr) ,$$ so the integer $f(x)$ is divisible by every $n \geq 1$. The only such integer is $0$: $f \equiv 0$.

## 7.6 Problem: The symmetric group and the 8-puzzle

**Problem 7.1.**

The [group](#def-b1-structures-group) $\mathfrak S_n$ of [permutations](https://one-course.com/books/math/3/en/chapter/2-counting#def-b1-counting-objects) of $\intint1n$ is the oldest [group](#def-b1-structures-group) in mathematics and still the most instructive. This problem builds its structure theory from scratch — cycles, generation by transpositions, the *signature* [morphism](#def-b1-structures-morphism) $\varepsilon \colon \mathfrak S_n \to \{\pm1\}$ (whose existence is genuinely nontrivial), and the [alternating group](#pb-b1-structures-1) $\mathfrak A_n$ generated by $3$-cycles — then cashes it in on a classical puzzle: in the $3 \times 3$ sliding-tile game, no sequence of moves can swap two tiles and leave everything else in place. [Permutations](https://one-course.com/books/math/3/en/chapter/2-counting#def-b1-counting-objects) act on $\intint1n$; products $\sigma\tau$ mean “apply $\tau$ first”; $[\,v_1, \dots, v_n]$ denotes the [permutation](https://one-course.com/books/math/3/en/chapter/2-counting#def-b1-counting-objects) sending $i$ to $v_i$.

**Part I — Cycles and transpositions.**

1. Justify $\abs{\mathfrak S_n} = n!$ ( [Theorem 2.12](https://one-course.com/books/math/3/en/chapter/2-counting#thm-b1-counting-counts) ). In $\mathfrak S_3$ , compute both products of $\sigma = [2, 3, 1]$ and $\tau =  [1, 3, 2]$ , and conclude that $\mathfrak S_3$ is not [abelian](#def-b1-structures-group) .
2. A *$k$-cycle* $(a_1\ a_2\ \dots\ a_k)$ ( $k \geq 2$ , the $a_i$ pairwise distinct) sends $a_1 \mapsto a_2  \mapsto \dots \mapsto a_k \mapsto a_1$ and fixes everything else; its *support* is $\{a_1, \dots,  a_k\}$ . Prove that two cycles with disjoint supports commute.
3. Prove that every $\sigma \in \mathfrak S_n$ is a product of cycles with pairwise disjoint supports, and that this decomposition is unique up to the [order](#def-b1-structures-order) of the factors. *(Consider, for each $i$, the sequence $i, \sigma(i),  \sigma^2(i), \dots$: it must return to $i$; the resulting *orbits* [partition](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#thm-b1-logic-partition) $\intint1n$, and $\sigma$ acts on each as a cycle.)*
4. Decompose $\sigma = [4, 1, 5, 2, 3, 7, 8, 6] \in  \mathfrak S_8$ into disjoint cycles. Defining the *[order](#def-b1-structures-order)* of $\sigma$ as in [Definition 7.14](#def-b1-structures-order) , prove that the [order](#def-b1-structures-order) of a product of disjoint cycles is the lcm of their lengths, and compute the [order](#def-b1-structures-order) of this $\sigma$ .
5. Prove the telescoping identity $$(a_1\ a_2\ \dots\ a_k)  = (a_1\ a_k)(a_1\ a_{k-1})\cdots(a_1\ a_2) ,$$ and conclude that every [permutation](https://one-course.com/books/math/3/en/chapter/2-counting#def-b1-counting-objects) is a product of transpositions. Write the $\sigma$ of question 4 as such a product.
6. Show further that the *adjacent* transpositions $(i\ \ i{+}1)$ suffice: for $a < b$, $$(a\ b) = (a\ \ a{+}1)(a{+}1\ \ a{+}2)\cdots(b{-}1\ \ b)  \cdots(a{+}1\ \ a{+}2)(a\ \ a{+}1),$$ a product of $2(b - a) - 1$ adjacent transpositions — an *odd* number (this parity will matter twice below).

**Part II — The signature exists.** For $\sigma
\in \mathfrak S_n$, let

$$
N(\sigma) = \#\bigl\{(i, j) : i < j,\ \sigma(i) >
\sigma(j)\bigr\}
$$

be its number of *inversions*, and set $\varepsilon(\sigma) =
(-1)^{N(\sigma)}$.

7. Compute $N$ and $\varepsilon$ for the identity, for a transposition $(i\ \ i{+}1)$ , and for $[2, 3, 1]$ .
8. Prove that for every $\sigma$ and every adjacent transposition $\tau = (i\ \ i{+}1)$ : $N(\sigma\tau) = N(\sigma) \pm 1$ . *(Composing with $\tau$ on the right swaps the values in positions $i$ and $i + 1$; exactly one pair changes its inversion status.)*
9. Deduce, using question 6, that for *any* transposition $\tau$ , $\varepsilon(\sigma\tau) =  -\varepsilon(\sigma)$ ; conclude that if $\sigma$ is a product of $p$ transpositions, then $\varepsilon(\sigma)  = (-1)^p$ — in particular the parity of $p$ depends only on $\sigma$ , not on the chosen factorization — and that $\varepsilon \colon \mathfrak S_n \to \{\pm 1\}$ is a [group](#def-b1-structures-group) [morphism](#def-b1-structures-morphism) .
10. Show that a $k$ -cycle has signature $(-1)^{k-1}$ , and that in general $\varepsilon(\sigma) = (-1)^{n -  c(\sigma)}$ , where $c(\sigma)$ is the number of orbits of $\sigma$ (fixed points included).
11. The *[alternating group](#pb-b1-structures-1)* is $\mathfrak A_n =  \ker\varepsilon$ . Justify that it is a [subgroup](#def-b1-structures-subgroup) , and prove $\abs{\mathfrak A_n} = \frac{n!}2$ for $n \geq 2$ . *(Fix a transposition $\tau_0$ and consider $\sigma  \mapsto \sigma\tau_0$.)*
12. Consistency check on $\sigma = [4, 1, 5, 2, 3, 7, 8, 6]$ : compute $\varepsilon(\sigma)$ three ways — by counting inversions, from the cycle type via question 10, and from your transposition count in question 5.

**Part III — $\mathfrak A_n$ is generated by $3$-cycles.**

13. Let $a, b, c, d$ be pairwise distinct. Verify the two identities $$(a\ b)(a\ c) = (a\ c\ b),  \qquad  (a\ b)(c\ d) = (a\ c\ b)(a\ c\ d) .$$
14. Prove that for $n \geq 3$ , every element of $\mathfrak  A_n$ is a product of $3$ -cycles. *(An even [permutation](https://one-course.com/books/math/3/en/chapter/2-counting#def-b1-counting-objects) is a product of an even number of transpositions; absorb them two at a time.)*
15. Write $(1\ 2)(3\ 4)$ and the $5$ -cycle $(1\ 2\ 3\ 4\ 5)$ explicitly as products of $3$ -cycles.
16. Prove the conjugation formula: for every $\sigma \in  \mathfrak S_n$, $$\sigma\,(a_1\ \dots\ a_k)\,\sigma^{-1}  = \bigl(\sigma(a_1)\ \dots\ \sigma(a_k)\bigr) .$$

**Part IV — The 8-puzzle.** Tiles $1, \dots, 8$ slide in a $3 \times 3$ frame with one empty cell; a *move* slides a tile adjacent to the empty cell into it. Number the cells $1, \dots, 9$ (row by row; the solved position has tile $i$ in cell $i$ and the empty cell at cell $9$). Treat the empty cell as a ninth tile, so a position is a [permutation](https://one-course.com/books/math/3/en/chapter/2-counting#def-b1-counting-objects) $\sigma \in \mathfrak
S_9$ (tile $\sigma(i)$ sits in cell $i$).

17. Show that a move replaces $\sigma$ by $\sigma \circ \tau$ where $\tau$ is the transposition of the two cells involved; deduce that each move flips $\varepsilon(\sigma)$ .
18. Let $d(\sigma)$ be the taxicab distance (rows plus columns) between the empty cell’s current cell and its home cell $9$. Show that each move changes $d$ by $\pm1$, so each move also flips $(-1)^{d(\sigma)}$. Conclude that $$I(\sigma) = \varepsilon(\sigma)\cdot(-1)^{d(\sigma)}$$ is *invariant* under every move.
19. Prove the puzzle’s classical impossibility: the position that swaps tiles $7$ and $8$ and leaves everything else (including the empty cell) in place cannot be reached from the solved position.
20. We admit the converse (its proof is an instructive but lengthy induction): every position with $I = +1$ is reachable. Deduce that exactly half of the $8!$ positions with the empty cell at home are solvable, i.e. $\frac{8!}2 = 20\,160$ .
21. Deduce from question 20 that the reachable tile arrangements with the empty cell at home form exactly the [subgroup](#def-b1-structures-subgroup) $\mathfrak A_8 \leq \mathfrak S_8$ .
22. Applications of the invariant: can one reach (a) the position where tiles $1, 2, 3$ are cyclically permuted and everything else, empty cell included, is at home? (b) the position where tile $5$ and the empty cell have exchanged places and all other tiles are at home? Justify both answers with $I$ .

**Part V — Synthesis.**

23. Prove that for $n \geq 3$ the only [group](#def-b1-structures-group) [morphisms](#def-b1-structures-morphism) $f  \colon \mathfrak S_n \to \{\pm 1\}$ are the constant [morphism](#def-b1-structures-morphism) and $\varepsilon$ . *(Using question 16 and commutativity of $\{\pm1\}$, show $f$ takes the same value on all transpositions.)*
24. Where exactly did the problem use: (i) the [morphism](#def-b1-structures-morphism) concept and [Proposition 7.11](#prop-b1-structures-kernel) ; (ii) the counting principles of [Chapter 2](https://one-course.com/books/math/3/en/chapter/2-counting#ch-b1-counting) ; (iii) the well-definedness issue that questions 8–9 resolve? One sentence each.
25. Synthesis, in a short paragraph: one parity function, proved well defined once, simultaneously organizes the internal structure of $\mathfrak S_n$ (the [subgroup](#def-b1-structures-subgroup) $\mathfrak A_n$ ), decides a physical puzzle, and — through the formula $\det = \sum_\sigma  \varepsilon(\sigma)\cdots$ — will define determinants in [Chapter 22](https://one-course.com/books/math/3/en/chapter/22-determinants-and-linear-systems#ch-b1-det) . Comment on the recurring pattern: invariants turn “try all sequences of moves” into one computation.

**Solution of Problem 7.1.**

**1.** A [permutation](https://one-course.com/books/math/3/en/chapter/2-counting#def-b1-counting-objects) is a bijection of $\intint1n$, i.e. an $n$-arrangement of $n$ objects: there are $n!$ of them ([Theorem 2.12](https://one-course.com/books/math/3/en/chapter/2-counting#thm-b1-counting-counts)). With $\sigma = [2,3,1]$, $\tau =
[1,3,2]$: $\sigma\tau$ sends $1 \mapsto 1 \mapsto 2$, $2 \mapsto 3
\mapsto 1$, $3 \mapsto 2 \mapsto 3$: $\sigma\tau = [2,1,3]$; and $\tau\sigma$ sends $1 \mapsto 2 \mapsto 3$, $2 \mapsto 3 \mapsto
2$, $3 \mapsto 1 \mapsto 1$: $\tau\sigma = [3,2,1] \neq
\sigma\tau$.

**2.** Let $\gamma, \gamma'$ have disjoint supports $S, S'$. For $x \in S$: $\gamma'(x) = x$ and $\gamma(x) \in S$, so $\gamma\gamma'(x) = \gamma(x) = \gamma'\gamma(x)$. Symmetrically for $x \in S'$; and both sides fix every $x \notin S \cup S'$. So $\gamma\gamma' = \gamma'\gamma$.

**3.** For $i \in \intint1n$, the values $i, \sigma(i),
\sigma^2(i), \dots$ live in a [finite set](https://one-course.com/books/math/3/en/chapter/2-counting#def-b1-counting-card), so $\sigma^a(i) =
\sigma^b(i)$ for some $a < b$; injectivity gives $\sigma^{b-a}(i)
= i$: the sequence returns to $i$. Call *orbit* of $i$ the set $\{i, \sigma(i), \dots, \sigma^{k-1}(i)\}$ with $k \geq 1$ minimal such that $\sigma^k(i) = i$. Two orbits meeting in one point coincide (both are the forward $\sigma$-images of that point), so the orbits [partition](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#thm-b1-logic-partition) $\intint1n$; $\sigma$ acts on each orbit of size $k \geq 2$ as the $k$-cycle $(i\ \sigma(i)\ \cdots\
\sigma^{k-1}(i))$ and fixes the singletons. The product of these disjoint cycles agrees with $\sigma$ everywhere. Uniqueness: in any decomposition into disjoint cycles, the cycle through $i$ must be $(i\ \sigma(i)\ \cdots)$ — the cycles are forced to be the orbits with their induced action.

**4.** Following the orbits: $1 \to 4 \to 2 \to 1$, $3 \to 5
\to 3$, $6 \to 7 \to 8 \to 6$:

$$
\sigma = (1\ 4\ 2)(3\ 5)(6\ 7\ 8) .
$$

If $\sigma = \gamma_1\cdots\gamma_r$ with disjoint cycles of lengths $k_1, \dots, k_r$, commutation (question 2) gives $\sigma^m = \gamma_1^m\cdots\gamma_r^m$, and since the supports are disjoint, $\sigma^m = \mathrm{id}$ iff each $\gamma_i^m =
\mathrm{id}$ iff $k_i \mid m$ for all $i$ (a $k$-cycle has [order](#def-b1-structures-order) $k$: $\gamma^m$ sends $a_1$ to $a_{1 + (m \bmod k)}$). The least such $m$ is $\operatorname{lcm}(k_1, \dots, k_r)$. Here: $\operatorname{lcm}(3, 2, 3) = 6$.

**5.** Apply the right-hand side to each point, rightmost factor first. $a_1 \mapsto a_2$ by $(a_1\ a_2)$, then every later factor fixes $a_2$: net $a_1 \mapsto a_2$. For $2 \leq i < k$: $a_i$ is untouched until $(a_1\ a_i)$ sends it to $a_1$, and the very next factor $(a_1\ a_{i+1})$ sends $a_1$ to $a_{i+1}$, after which nothing moves it: net $a_i \mapsto a_{i+1}$. Finally $a_k$ is fixed by all factors but the leftmost, which sends it to $a_1$. This is exactly the cycle. Since every [permutation](https://one-course.com/books/math/3/en/chapter/2-counting#def-b1-counting-objects) is a product of cycles (question 3), it is a product of transpositions. For question 4’s $\sigma$:

$$
\sigma = (1\ 2)(1\ 4)\;(3\ 5)\;(6\ 8)(6\ 7),
$$

five transpositions.

**6.** Induction on $b - a$. For $b = a + 1$ the identity is trivial ($1 = 2\cdot1 - 1$ factor). For $b > a + 1$, verify directly that $(a\ b) = (a\ \ a{+}1)\,(a{+}1\ \ b)\,(a\ \ a{+}1)$: the right side sends $a \mapsto a{+}1 \mapsto b \mapsto b$, $b
\mapsto b \mapsto a{+}1 \mapsto a$, $a{+}1 \mapsto a \mapsto a
\mapsto a{+}1$, and fixes the rest. By induction $(a{+}1\ \ b)$ is a palindromic product of $2(b - a - 1) - 1$ adjacent transpositions, so $(a\ b)$ is one of $2(b - a) - 1$: an odd number.

**7.** $N(\mathrm{id}) = 0$, $\varepsilon = +1$. For $(i\ \
i{+}1)$, the only inverted pair is $(i, i+1)$: $N = 1$, $\varepsilon = -1$. For $[2, 3, 1]$: the inverted pairs are $(1,
3)$ (values $2 > 1$) and $(2, 3)$ (values $3 > 1$): $N = 2$, $\varepsilon = +1$.

**8.** The value lists of $\sigma$ and $\sigma\tau$ differ only by the swap of positions $i$ and $i + 1$. For a pair of positions not involving $i, i+1$, nothing changes. For $k < i$, the two pairs $(k, i)$ and $(k, i+1)$ exchange their inversion statuses (the same two values are compared with $\sigma(k)$, in the other [order](#def-b1-structures-order) of positions): their total contribution is unchanged; likewise for $k > i + 1$. The one remaining pair $(i,
i+1)$ flips its status. Hence $N(\sigma\tau) = N(\sigma) \pm 1$.

**9.** Let $\tau = (a\ b)$ be any transposition: by question 6 it is a product of an odd number of adjacent transpositions, so right-multiplying by $\tau$ changes $N$ by an odd total (question 8, applied repeatedly): $\varepsilon(\sigma
\tau) = -\varepsilon(\sigma)$. Now if $\sigma = \tau_1\cdots
\tau_p$ (transpositions), build it up from the identity by $p$ right-multiplications: $\varepsilon(\sigma) =
(-1)^p\varepsilon(\mathrm{id}) = (-1)^p$. Since $\varepsilon(\sigma)$ is defined by inversions — independently of any factorization — the parity of $p$ is an invariant of $\sigma$. [Morphism](#def-b1-structures-morphism): writing $\sigma$ with $p$ and $\sigma'$ with $q$ transpositions, $\sigma\sigma'$ uses $p + q$ of them: $\varepsilon(\sigma\sigma') = (-1)^{p+q} =
\varepsilon(\sigma)\varepsilon(\sigma')$.

**10.** A $k$-cycle is a product of $k - 1$ transpositions (question 5): $\varepsilon = (-1)^{k-1}$. For general $\sigma$ with orbits of sizes $k_1, \dots, k_r$ ($k_i \geq 2$) plus $f$ fixed points, $c(\sigma) = r + f$ and $n = k_1 + \dots + k_r + f$, so

$$
\varepsilon(\sigma) = \prod_{i=1}^r (-1)^{k_i - 1}
= (-1)^{\sum_i k_i - r} = (-1)^{n - f - r} = (-1)^{n -
c(\sigma)} .
$$

**11.** $\mathfrak A_n = \ker\varepsilon$ is a [subgroup](#def-b1-structures-subgroup) as the [kernel](#def-b1-structures-morphism) of a [morphism](#def-b1-structures-morphism) ([Definition 7.10](#def-b1-structures-morphism)). Fix a transposition $\tau_0$ (exists for $n \geq 2$). The [map](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-map) $\sigma
\mapsto \sigma\tau_0$ is a bijection of $\mathfrak S_n$ (its own inverse) exchanging $\mathfrak A_n$ with the [set](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-sets) of odd [permutations](https://one-course.com/books/math/3/en/chapter/2-counting#def-b1-counting-objects) (question 9). The two [sets](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-sets) [partition](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#thm-b1-logic-partition) $\mathfrak S_n$ and have equal size: $\abs{\mathfrak A_n} = \frac{n!}2$.

**12.** *Inversions* of $[4, 1, 5, 2, 3, 7, 8, 6]$: from value $4$: over $1, 2, 3$: three; from $5$: over $2, 3$: two; from $7$: over $6$: one; from $8$: over $6$: one. $N = 7$, $\varepsilon = -1$. *Cycle type*: $c = 3$ orbits, $n = 8$: $\varepsilon = (-1)^{8-3} = -1$. *Transposition count*: five transpositions in question 5: $(-1)^5 = -1$. All three agree.

**13.** $(a\ b)(a\ c)$ (rightmost first): $a \mapsto c
\mapsto c$; $c \mapsto a \mapsto b$; $b \mapsto b \mapsto a$: the $3$-cycle $(a\ c\ b)$. And $(a\ c\ b)(a\ c\ d)$: $a \mapsto c
\mapsto b$; $b \mapsto b \mapsto a$; $c \mapsto d \mapsto d$; $d
\mapsto a \mapsto c$: that is $(a\ b)(c\ d)$, as claimed.

**14.** Let $\sigma \in \mathfrak A_n$: by question 9, $\sigma = \tau_1\cdots\tau_{2m}$ with an even number of transpositions. Group them in consecutive pairs $\tau_{2i-1}\tau_{2i}$: if the two are equal, the pair is the identity and disappears; if they share exactly one point, the first identity of question 13 writes the pair as one $3$-cycle; if they are disjoint, the second identity writes it as two $3$-cycles. Hence $\sigma$ is a product of $3$-cycles (or the identity, an empty product — and for $n \geq 3$ also $(1\ 2\
3)^3$).

**15.** $(1\ 2)(3\ 4) = (1\ 3\ 2)(1\ 3\ 4)$ (question 13 with $a{=}1, b{=}2, c{=}3, d{=}4$). For the $5$-cycle: by question 5, $(1\ 2\ 3\ 4\ 5) = (1\ 5)(1\ 4)(1\ 3)(1\ 2)$, and pairing: $(1\ 5)(1\ 4) = (1\ 4\ 5)$, $(1\ 3)(1\ 2) = (1\ 2\ 3)$:

$$
(1\ 2\ 3\ 4\ 5) = (1\ 4\ 5)(1\ 2\ 3) .
$$

(Check on $3$: $(1\ 2\ 3)$ sends $3 \to 1$, then $(1\ 4\ 5)$ sends $1 \to 4$: net $3 \to 4$, correct.)

**16.** Apply both sides to an arbitrary point. For $i =
\sigma(a_j)$: the left side gives $\sigma\bigl((a_1\ \dots\
a_k)(a_j)\bigr) = \sigma(a_{j+1})$ (indices mod $k$), which is what the right side does to $\sigma(a_j)$. For $i$ not of this form: $\sigma^{-1}(i)$ is outside the support, so the left side fixes $i$, and so does the right side. Equal everywhere.

**17.** Sliding the tile of cell $c'$ into the empty cell $c$ swaps the contents of cells $c$ and $c'$ (tile $9$, the blank, moves to $c'$). If tile $\sigma(i)$ sat in cell $i$, the new position is $\sigma' = \sigma \circ (c\ c')$: same contents except that cells $c, c'$ read each other’s former contents. By question 9, $\varepsilon(\sigma') = -\varepsilon(\sigma)$.

**18.** A move sends the empty cell to an adjacent cell: its row or its column changes by exactly $1$, so the taxicab distance $d$ to cell $9$ changes by $\pm1$, and $(-1)^d$ flips. Since each move flips both $\varepsilon(\sigma)$ and $(-1)^{d(\sigma)}$, their product $I(\sigma)$ is unchanged by every move: an invariant.

**19.** The solved position has $\varepsilon = +1$, $d = 0$: $I = +1$. The target (tiles $7, 8$ swapped, blank home) is the transposition of the contents of cells $7$ and $8$: $\varepsilon
= -1$, $d = 0$: $I = -1$. Since $I$ is invariant and the two values differ, no sequence of moves joins them.

**20.** A position with the blank at home is a [permutation](https://one-course.com/books/math/3/en/chapter/2-counting#def-b1-counting-objects) of the $8$ tiles among cells $1, \dots, 8$, i.e. an element of $\mathfrak S_8$; it has $d = 0$, so $I = \varepsilon(\sigma)$. Reachable forces $I = +1$, i.e. $\sigma \in \mathfrak A_8$; the admitted converse says all of $\mathfrak A_8$ is reached. Count: $\abs{\mathfrak A_8} = \frac{8!}2 = 20\,160$ (question 11).

**21.** By question 20 the reachable blank-at-home arrangements form exactly $\mathfrak A_8$ — in particular a *[subgroup](#def-b1-structures-subgroup)* of $\mathfrak S_8$: composing two solvable scrambles, or inverting one, stays solvable, which is far from obvious by pure puzzle reasoning.

**22.** (a) A $3$-cycle of tiles with blank home: $\varepsilon = +1$ (question 10), $d = 0$, so $I = +1$: reachable (by the admitted converse) — one can cycle three tiles. (b) Tile $5$ and the blank exchanged: the position is the transposition of the contents of cells $5$ and $9$, so $\varepsilon = -1$; the blank sits at the center, at taxicab distance $d = 2$ from home, so $(-1)^d = +1$ and $I = -1$: unreachable. One cannot simply “park the blank in the middle” leaving the tiles otherwise sorted.

**23.** Let $f \colon \mathfrak S_n \to \{\pm1\}$ be a [morphism](#def-b1-structures-morphism). For any two transpositions $\tau, \tau'$, question 16 provides $\sigma$ with $\sigma\tau\sigma^{-1} = \tau'$ ([map](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-map) the two moved points onto the two others; $n \geq 3$ guarantees room to do so, though even $n = 2$ is trivial here). Then $f(\tau') =
f(\sigma)f(\tau)f(\sigma)^{-1} = f(\tau)$ since $\{\pm1\}$ is [abelian](#def-b1-structures-group): $f$ is constant on transpositions. If that constant is $+1$, then $f = 1$ on all products of transpositions, i.e. everywhere (question 5). If it is $-1$, then $f(\sigma) =
(-1)^p = \varepsilon(\sigma)$ on a product of $p$ transpositions. So $f \in \{1, \varepsilon\}$.

**24.** (i) The [morphism](#def-b1-structures-morphism) property of $\varepsilon$ and the [kernel](#def-b1-structures-morphism) machinery gave $\mathfrak A_n$ its [subgroup](#def-b1-structures-subgroup) structure and its size, and [Proposition 7.11](#prop-b1-structures-kernel)-style reasoning runs through questions 11 and 21. (ii) Counting: $\abs{\mathfrak S_n} = n!$, the halving argument of question 11, and the count $20\,160$ of question 20 are [Chapter 2](https://one-course.com/books/math/3/en/chapter/2-counting#ch-b1-counting) at work. (iii) Questions 8–9 resolve a genuine well-definedness problem — “the parity of the number of transpositions” presupposes that this parity does not depend on the factorization, exactly as $\Z/n\Z$’s operations required representative-independence in [Definition 7.24](#def-b1-structures-zn).

**25.** The signature is a single $\{\pm1\}$-valued computation, proved once to be well defined, and it does three jobs at once: internally, it cuts $\mathfrak S_n$ in half and isolates $\mathfrak A_n$ with its $3$-cycle generators; externally, it decides in one line a question (“can these two tiles be swapped?”) that naive search could never settle, since no finite list of failed move sequences proves impossibility; and structurally, it is the alternating-sign engine inside the formula $\det A = \sum_\sigma \varepsilon(\sigma)\,
a_{1\sigma(1)}\cdots a_{n\sigma(n)}$ of [Chapter 22](https://one-course.com/books/math/3/en/chapter/22-determinants-and-linear-systems#ch-b1-det). The pattern — find a quantity conserved by every elementary move, compute it at the start and at the target — is the mathematician’s standard weapon against “is it possible?” questions, and it will return whenever a [group](#def-b1-structures-group) acts on a [set](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-sets) of states.