## 3.1 整数等价类和对称性

**Proposition 3.4.** Let $Z_n$ be the set of equivalence classes of the integers mod $n$ and
$a, b, c \in Z_n$.

- Addition and multiplication are commutative: $$a+b \equiv b+a \mod n$$ $$ab \equiv ba \mod n$$
- Addition and multiplication are associative: $$(a+b)+c \equiv a+(b+c) \mod n$$ $$(ab)c \equiv a(bc) \mod n$$
- There are both additive and multiplicative identities: $$a+0 \equiv a \mod n$$ $$a\cdot 0 \equiv 0 \mod n$$
- Multiplication distributes over addition: $$a(b+c) \equiv ab+ac\mod n$$
- For every integer $a$ there is an additive inverse $−a$: $$a + (-a) \equiv 0 \mod n$$
- Let $a$ be a nonzero integer. Then $\gcd(a, n) = 1$ if and only if there exists a multiplicative inverse $b$ for $a \mod n$; that is, a nonzero integer $b$ such that $$ab\equiv 1 \mod n$$

A **symmetry** of a geometric figure is a rearrangement of the figure preserving the arrangement of its sides and vertices as well as its distances and angles. A map from the plane to itself preserving the symmetry of an object is called a **rigid motion**.

## 3.2 定义与例子

### 群的定义

A **binary operation** or **law of composition** on a set $G$ is a function $G \times G \rightarrow G$ that assigns to each pair $(a, b) \in G \times G$ a unique element $a \circ b$, or $ab$ in $G$, called the composition of $a$ and $b$. A group $(G, \circ)$ is a set $G$ together with a law of composition $(a, b) \mapsto a \circ b$ that
satisfies the following axioms.

- The law of composition is
**associative**. That is, $$(a \circ b) \circ c = a \circ (b \circ c)$$ for $a, b, c \in G$. - There exists an element $e \in G$, called the
**identity element**, such that for any element $a \in G$ $$e \circ a = a \circ e = a$$ - For each element $a \in G$, there exists an
**inverse element**in $G$, denoted by $a^{-1}$, such that $$a \circ a^{-1} = a^{-1} \circ a = e$$

A group $G$ with the property that $a \circ b = b \circ a$ for all $a, b \in G$ is called **abelian（阿贝尔）** or **commutative**. Groups not satisfying this property are said to be **nonabelian** or **non-commutative**.

It is often convenient to describe a group in terms of an addition or multiplication table. Such a table is called a **Cayley table**.

A group is **finite**, or has **finite order**, if it contains a finite number of elements; otherwise, the group is said to be **infinite** or to have **infinite order**. The **order** of a finite group is the number of elements that it contains.

### 群的基本性质

**Proposition 3.17.** The identity element in a group $G$ is unique; that is, there exists only one element $e \in G$ such that $eg = ge = g$ for all $g \in G$.

**Proposition 3.18.** If $g$ is any element in a group $G$, then the inverse of $g$, denoted by $g^{-1}$, is unique.

**Proposition 3.19.** Let $G$ be a group. If $a, b \in G$, then $(ab)^{−1} = b^{−1} a^{−1}$.

**Proposition 3.20.** Let $G$ be a group. For any $a \in G$, $(a^{−1})^{-1} = a$.

**Proposition 3.21.** Let $G$ be a group and $a$ and $b$ be any two elements in $G$. Then the equations $ax = b$ and $xa = b$ have unique solutions in $G$.

**Proposition 3.22.** If $G$ is a group and $a, b, c \in G$, then $ba = ca$ implies $b = c$ and $ab = ac$ implies $b = c$.

This proposition tells us that the right and left cancellation laws are true in groups.

**Theorem 3.23.** In a group, the usual laws of exponents hold; that is, for all $g, h \in G$,

- $g^m g^n = g^{m+n}$ for all $m, n \in \mathbb{Z}$;
- $(g^m)^n = g^{mn}$ for all $m, n \in \mathbb{Z}$;
- $(gh)^n = (h^{−1}g^{−1})^{−n}$ for all $n \in \mathbb{Z}$. Furthermore, if $G$ is abelian, then $(gh)^n = g^n h^n$.

## 3.3 子群

### 定义

We define a **subgroup** $H$ of a group $G$ to be a subset $H$ of $G$ such that when the group operation of $G$ is restricted to $H$, $H$ is a group in its own right.

The subgroup $H = {e}$ of a group $G$ is called the **trivial subgroup**. A subgroup that is a proper subset of $G$ is called a **proper subgroup**.

### 定理

**Proposition 3.30.** A subset $H$ of $G$ is a subgroup if and only if it satisfies the following conditions.

- The identity $e$ of $G$ is in $H$.
- If $h_1, h_2 \in H$, then $h_1 h_2 \in H$.
- If $h \in H$, then $h^{−1} \in H$.

**Proposition 3.31.** Let $H$ be a subset of a group $G$. Then $H$ is a subgroup of $G$ if and only if $H \neq \emptyset$, and whenever $g, h \in H$ then $gh^{−1}$ is in $H$.

## 4.1 循环子群

### 循环群的定义

**Theorem 4.3.** Let $G$ be a group and $a$ be any element in $G$. Then the set
$$\langle a \rangle = {a^k : k \in \mathbb{Z}} $$
is a subgroup of $G$. Furthermore, $\langle a \rangle$ is the smallest subgroup of $G$ that contains $a$.

For $a \in G$, we call $\langle a \rangle$ the **cyclic subgroup** generated by $a$. If $G$ contains some element $a$ such that $G = \langle a \rangle$, then $G$ is a **cyclic group**. In this case $a$ is a **generator** of $G$. If $a$ is an element of a group $G$, we define the **order** of a to be the smallest positive integer $n$ such that $a^n = e$, and we write $|a|=n$. If there is no such integer $n$, we say that the order of $a$ is **infinite** and write $|a| = \infty$ to denote the order of $a$.

**Theorem 4.9.** Every cyclic group is abelian.

### 循环群的子群

**Theorem 4.10.** Every subgroup of a cyclic group is cyclic.

**Corollary 4.11.** The subgroups of $\mathbb{Z}$ are exactly $n\mathbb{Z}$ for $n = 0, 1, 2, \dots$.

**Proposition 4.12.** Let $G$ be a cyclic group of order $n$ and suppose that $a$ is a generator for $G$. Then $a^k = e$ if and only if $n$ divides $k$.

**Theorem 4.13.** Let $G$ be a cyclic group of order $n$ and suppose that $a \in G$ is a generator of the group. If $b = a^k$, then the order of $b$ is $n/d$, where $d = \gcd(k, n)$.

**Corollary 4.14.** The generators of $\mathbb{Z}_n$ are the integers $r$ such that $1 \leqslant r < n$ and $\gcd(r, n) = 1$.

## 4.2 复数乘法群

**Proposition 4.20.** Let $z = r \text{ cis } \theta$ and $w = s \text{ cis } \phi$ be two nonzero complex numbers. Then
$$zw = rs \text{ cis }(\theta + \phi)$$

**Theorem 4.22 DeMoivre.** Let $z = r \text{ cis } \theta$ be a nonzero complex number. Then
$$[r \text{ cis } \theta]^n = r^n \text{ cis }(n\theta)$$
for $n = 1, 2, \dots$.

### 圆群和单位根

We first consider **the circle group**, $\mathbb{T} = {z \in \mathbb{C} : |z| = 1}$.

**Proposition 4.24.** The circle group is a subgroup of $\mathbb{C} ^*$.

The complex numbers satisfying the equation $z^n = 1$ are called the $n$**th roots of unity**.

**Theorem 4.25.** If $z^n = 1$, then the $n$th roots of unity are
$$ z = \text{ cis } (\dfrac{2k\pi}{n})$$
where $k = 0, 1, \dots, n - 1$. Furthermore, the $n$th roots of unity form a cyclic subgroup of $\mathbb{T}$ of order $n$.

A generator for the group of the $n$th roots of unity is called a **primitive $n$th root of unity**.

## 4.3 快速幂

The laws of exponents still work in $\mathbb{Z}_n$; that is, if $b \equiv a^x \mod n$ and $c \equiv a^y \mod n$, then $bc \equiv a^{x+y} \mod n$. We can compute $a^{2^k} \mod n$ in $k$ multiplications by computing $$a^{2^0} \mod n, a^{2^1} \mod n, \cdots, a^{2^k} \mod n$$ Each step involves squaring the answer obtained in the previous step, dividing by $n$, and taking the remainder.

## Loading Comments By Disqus