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$.

1. Addition and multiplication are commutative: $$a+b \equiv b+a \mod n$$ $$ab \equiv ba \mod n$$
2. Addition and multiplication are associative: $$(a+b)+c \equiv a+(b+c) \mod n$$ $$(ab)c \equiv a(bc) \mod n$$
3. There are both additive and multiplicative identities: $$a+0 \equiv a \mod n$$ $$a\cdot 0 \equiv 0 \mod n$$
4. Multiplication distributes over addition: $$a(b+c) \equiv ab+ac\mod n$$
5. For every integer $a$ there is an additive inverse $−a$: $$a + (-a) \equiv 0 \mod n$$
6. 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$,

1. $g^m g^n = g^{m+n}$ for all $m, n \in \mathbb{Z}$;
2. $(g^m)^n = g^{mn}$ for all $m, n \in \mathbb{Z}$;
3. $(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.

1. The identity $e$ of $G$ is in $H$.
2. If $h_1, h_2 \in H$, then $h_1 h_2 \in H$.
3. 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.