## 5.1 定义和记号

In general, the permutations of a set $X$ form a group $S_X$. If $X$ is a finite set, we can assume $X = \{1, 2, \dots, n\}$. In this case we write $S_n$ instead of $S_X$. The following theorem says that $S_n$ is a group. We call this group the **symmetric group** on $n$ letters.

**Theorem 5.1.** The symmetric group on $n$ letters, $S_n$, is a group with $n!$ elements, where the binary operation is the composition of maps.

A subgroup of $S_n$ is called a **permutation group**.

A permutation $\sigma \in S_X$ is a **cycle of length** $k$ if there exist elements $a_1, a_2, \dots, a_k \in X$ such that
$$ \sigma(a_1)=a_2, \sigma(a_2)=a_3, \dots, \sigma(a_k)=a_1$$
and $\sigma(x) = x$ for all other elements $x \in X$. We will write $(a_1, a_2, \dots, a_k)$ to denote the cycle $\sigma$. Cycles are the building blocks of all permutations.

Two cycles in $S_X, \sigma=(a_1, a_2, \dots, a_k)$ and $\tau = (b_1, b_2, \dots, b_l)$ are **disjoint** if $a_i \neq b_j$ for all $i$ and $j$.

**Proposition 5.8.** Let $\sigma$and $\tau$ be two disjoint cycles in $S_X$. Then $\sigma\tau = \tau\sigma$.

**Theorem 5.9.** Every permutation in $S_n$ can be written as the product of disjoint cycles.

The simplest permutation is a cycle of length 2. Such cycles are called **transpositions**.

**Proposition 5.12.** Any permutation of a finite set containing at least two elements can be written as the product of transpositions.

**Lemma 5.14.** If the identity is written as the product of $r$ transpositions,
$$id = \tau_1 \tau_2 \dots \tau_r,$$
then $r$ is an even number.

**Theorem 5.15.** If a permutation $\sigma$ can be expressed as the product of an even number of transpositions, then any other product of transpositions equaling $\sigma$ must also contain an even number of transpositions. Similarly, if $\sigma$ can be expressed as the product of an odd number of transpositions, then any other product of transpositions equaling $\sigma$ must also contain an odd number of transpositions.

One of the most important subgroups of $S_n$ is the set of all even permutations, $A_n$. The group $A_n$ is called the **alternating group on $n$ letters**.

**Theorem 5.16.** The set $A_n$ is a subgroup of $S_n$.

**Proposition 5.17.** The number of even permutations in $S_n$, $n \geqslant 2$, is equal to the number of odd permutations; hence, the order of $A_n$ is $n!/2$.

## 5.2 二面体群

For $n = 3, 4, \dots$, we define the **$n$th dihedral group** to be the group of rigid motions of a regular $n$-gon. We will denote this group by $D_n$.

**Theorem 5.20.** The dihedral group, $D_n$, is a subgroup of $S_n$ of order $2n$.

**Theorem 5.23.** The group $D_n$, $n \geqslant 3$, consists of all products of the two elements $r$ and $s$, satisfying the relations
$$r^n=1, s^2=1, srs=r^{-1}.$$

**Proposition 5.27.** The group of rigid motions of a cube contains $24$ elements.

**Theorem 5.28.** The group of rigid motions of a cube is $S_4$.

## 6.1 陪集

Let $G$ be a group and $H$ a subgroup of $G$. Define a **left coset** of $H$ with **representative** $g \in G$ to be the set
$$gH = \{gh : h \in H\}$$
**Right cosets** can be defined similarly by
$$Hg = \{hg : h \in H\}$$

**Lemma 6.3.** Let $H$ be a subgroup of a group $G$ and suppose that $g_1, g_2 \in G$. The following conditions are equivalent.

- $g_1H = g_2H$;
- $Hg_1^{-1} = Hg_2^{-1}$;
- $g_1H \subset g_2H$;
- $g2 \in g1H$;
- $g_1^{-1}g_2 \in H$.

**Theorem 6.4.** Let $H$ be a subgroup of a group $G$. Then the left cosets of $H$ in $G$ partition
$G$. That is, the group $G$ is the disjoint union of the left cosets of $H$ in $G$.

Let $G$ be a group and $H$ be a subgroup of $G$. Define the index of $H$ in $G$ to be the number of left cosets of $H$ in $G$. We will denote the index by $[G : H]$.

**Theorem 6.8.** Let $H$ be a subgroup of a group $G$. The number of left cosets of $H$ in $G$ is the same as the number of right cosets of $H$ in $G$.

## 6.2 拉格朗日定理

**Proposition 6.9.** Let $H$ be a subgroup of $G$ with $g \in G$ and define a map $\phi: H \rightarrow gH$ by $\phi(h) = gh$. The map $\phi$ is bijective; hence, the number of elements in $H$ is the same as the number of elements in $gH$.

**Theorem 6.10 Lagrange.** Let $G$ be a finite group and let $H$ be a subgroup of $G$. Then $|G|/|H| = [G : H]$ is the number of distinct left cosets of $H$ in $G$. In particular, the number of elements in $H$ must divide the number of elements in $G$.

**The converse of Lagrange’s Theorem is false.**

**Corollary 6.11.** Suppose that $G$ is a finite group and $g \in G$. Then the order of $g$ must divide the number of elements in $G$.

**Corollary 6.12.** Let $|G| = p$ with $p$ a prime number. Then $G$ is cyclic and any $g \in G$ such that $g \neq e$ is a generator.

**Corollary 6.13.** Let $H$ and $K$ be subgroups of a finite group $G$ such that $G \supset H \supset K$.
Then
$$[G : K] = [G : H][H : K].$$

**Proposition 6.15.** The group $A_4$ has no subgroup of order $6$.

**Theorem 6.16.** Two cycles $\tau$ and $\mu$ in $S_n$ have the same length if and only if there exists
a $\sigma \in S_n$ such that $\mu = \sigma \tau \sigma^{-1}$.

## 6.3 费马与欧拉定理

The **Euler $\phi$-function** is the map $\phi : \mathbb{N} \rightarrow \mathbb{N}$ defined by $\phi(n) = 1$ for $n = 1$, and, for $n > 1$, $\phi(n)$ is the number of positive integers $m$ with $1 \leqslant m < n$ and $\gcd(m,n) = 1$.

**Theorem 6.17.** Let $U(n)$ be the group of units in $\mathbb{Z}_n$. Then $|U(n)| = \phi(n)$.

**Theorem 6.18 Euler’s Theorem.** Let $a$ and $n$ be integers such that $n > 0$ and $\gcd(a,n) = 1$. Then $a^{\phi(n)} \equiv 1 \mod n$.

**Theorem 6.19 Fermat’s Little Theorem.** Let $p$ be any prime number and suppose that $p \nmid a$ ($p$ does not divide $a$). Then
$$a^{p-1} \equiv 1 \mod p.$$
Furthermore, for any integer $b$, $b^p \equiv b \mod p$.