抽象代数笔记（2024-10-5 更新）

序言

抽象代数是数学的基础，也是密码学的基础。

之前大学期间只学了概念、定理等，对证明不重视，导致基础比较薄弱，因此重学并记录笔记在此。本文将

集合

笛卡尔积

笛卡尔积。 笛卡尔积是两个集合的所有可能有序对的集合。如果 $A$ 和 $B$ 是集合，则 $A$ 和 $B$ 的笛卡尔积记作 $A \times B$，定义为 $\{(a, b) : a \in A \text{ and } b \in B\}$。

关系

关系。 如果 $A$ 和 $B$ 是两个集合，那么从 $A$ 到 $B$ 的一个关系 $R$ 可以被视为一对序偶的集合，其中每个序偶的第一个元素来自集合 $A$，第二个元素来自集合 $B$。即 $R$ 是 $A \times B$ 的子集。

数学上，这可以写成 $R \subseteq A \times B$。如果 $(a, b) \in R$，我们通常写作 $aRb$，表示元素 $a$ 与元素 $b$ 之间存在关系 $R$。

域

域。 域指的是所有可能输入值的集合。具体地说，如果 $R$ 是从集合 $A$ 到集合 $B$ 的一个关系，那么 $A$ 被称为这个关系的定义域或域（Domain）。在函数 $f: A \rightarrow B$ 的情况下，集合 $A$ 是函数 $f$ 的域。

例如，考虑一个简单的函数 $f(x) = x^2$，如果我们定义 $f$ 的域为所有实数 $\mathbb{R}$，则 $f$ 的域就是 $\mathbb{R}$，意味着函数可以接受任何实数作为输入。

映射

映射。 映射（也称函数）是从一个集合到另一个集合的规则，该规则将第一个集合中的每一个元素与第二个集合中的唯一一个元素关联起来。

映射的类型

映射的类型。 映射可以根据其性质分类，例如：

• 一对一映射 或 单射 (one-to-one)：如果每个元素在目标集中只有一个对应元素。

• 满射 (onto)：如果目标集中的每个元素至少有一个原像。

• 双射 (bijective)：既是单射又是满射。

可逆性

可逆性。

• 如果一个函数有逆映射（inverse mapping），则称其为可逆的。

• 函数 $f$ 的逆映射通常记为 $f^{-1}$。

恒等映射

恒等映射。

• 对于任意集合 $S$，恒等映射 $\text{id}_S$（或简称为 $\text{id}$ ）是从 $S$ 到 $S$ 的一个映射。

• 定义为 $\text{id}(s) = s$，对所有 $s \in S$ 都成立。

• 这意味着每个元素都映射到其自身。

恒等映射和可逆性的关系

恒等映射和可逆性的关系。

• 如果映射 $g: B \to A$ 是映射 $f: A \to B$ 的逆映射，则需满足：

  • $g \circ f = \text{id}_A$（先应用 $f$ 再应用 $g$ 返回 $A$ 中的原始元素）。

  • $f \circ g = \text{id}_B$（先应用 $g$ 再应用 $f$ 返回 $B$ 中的原始元素）。

• 这意味着逆映射可以“撤销”原映射的效果。

映射组合性质定理

映射组合性质定理。 令 $f: A \to B, g: B\to C, h: C\to D$

1. 组合的结合性：

   • 说明：映射的组合是结合的，即 $(h \circ g) \circ f = h \circ (g \circ f)$。

   • 证明：对于任意 $x \in A$，

     
     $$
     ((h \circ g) \circ f)(x) = (h \circ g)(f(x)) = h(g(f(x)))
     $$
     

     
     $$
     (h \circ (g \circ f))(x) = h((g \circ f)(x)) = h(g(f(x)))
     $$
     

     因此，$(h \circ g) \circ f = h \circ (g \circ f)$。

2. 一一性：

   • 说明：如果 $f$ 和 $g$ 都是一一映射，则 $g \circ f$ 也是一一映射。

   • 证明：假设 $g(f(x_1)) = g(f(x_2))$，由于 $g$ 是一一的，得到 $f(x_1) = f(x_2)$。再由于 $f$ 是一一的，得到 $x_1 = x_2$。因此，$g \circ f$ 是一一的。

3. 满射性：

   • 说明：如果 $f$ 和 $g$ 都是满射，则 $g \circ f$ 也是满射。

   • 证明：对于任意 $z \in C$，由于 $g$ 是满射，存在 $y \in B$ 使得 $g(y) = z$。由于 $f$ 是满射，存在 $x \in A$ 使得 $f(x) = y$。因此，$g(f(x)) = z$，说明 $g \circ f$ 是满射。

4. 双射性：

   • 说明：如果 $f$ 和 $g$ 都是双射，则 $g \circ f$ 也是双射。

   • 证明：双射是同时一一且满的映射。由前两条性质可知，如果 $f$ 和 $g$ 都是一一且满的，则 $g \circ f$ 也是一一且满的，因此 $g \circ f$ 是双射。

映射可逆性定理

映射可逆性定理。 一个映射可逆的充要条件是该映射既是一一映射又是满射。

1. 正向证明：假设 $f: A \to B$ 是可逆的，且其逆为 $g: B \to A$。

   • 由于可逆，故 $g \circ f = \text{id}_A$ 是恒等映射，即 $g(f(a)) = a$ 对所有 $a \in A$ 都成立。

   • 如果 $f(a_1) = f(a_2)$，则 $g(f(a_1)) = g(f(a_2))$ 导致 $a_1 = a_2$，因此 $f$ 是一一映射。

   • 对于任意 $b \in B$，需要找到一个 $a \in A$ 使得 $f(a) = b$。令 $a = g(b)$，则 $f(g(b)) = b$，因此 $f$ 是满射。

2. 逆向证明：假设 $f$ 是双射（既一一又满射）。

   • 对于任意 $b \in B$，由于 $f$ 是满射，存在 $a \in A$ 使得 $f(a) = b$。

   • 由于 $f$ 是一一的，$a$ 是唯一的。

   • 定义 $g: B \to A$ 使得 $g(b) = a$，则 $g$ 是 $f$ 的逆映射。

证明思路分析。

• 正向，通过假设两个变量 $a_{1},a_{2}$ ，结合复合恒等性，推出他们相同来证明了一一性。漫射性通过对所有目标集合的元素都检查是否覆盖来解决。

• 逆向，由于任何 b 都能在对应到唯一的 a，满足函数的定义，因此能定义一个逆映射。

自反、对称和传递

自反、对称和传递。

1. 自反性（Reflexivity）：

   • 一个关系 $R$ 在集合 $A$ 上是自反的，如果对于集合中的每一个元素 $a$，都有 $(a, a) \in R$。

   • 换句话说，每个元素都与自身相关联。

2. 对称性（Symmetry）：

   • 一个关系 $R$ 在集合 $A$ 上是对称的，如果对于集合中的任意两个元素 $a$ 和 $b$，只要 $(a, b) \in R$，就有 $(b, a) \in R$。

   • 换句话说，如果一个元素与另一个元素相关联，那么反过来也成立。

3. 传递性（Transitivity）：

   • 一个关系 $R$ 在集合 $A$ 上是传递的，如果对于集合中的任意三个元素 $a$、$b$ 和 $c$，只要 $(a, b) \in R$ 且 $(b, c) \in R$，就有 $(a, c) \in R$。

   • 换句话说，关系可以“传递”通过中间元素。

例如，整数集合上的小于等于关系 (≤) 是传递的，因为如果 $a ≤ b$ 且 $b ≤ c$，那么 $a ≤ c$。

等价关系、等价类

等价关系、等价类。 等价关系是具有自反性、对称性和传递性的二元关系。等价类是由等价关系产生的集合，其中的每个元素都与该集合中的其他元素等价。如果 $R$ 是集合 $S$ 上的一个等价关系，则对于 $S$ 中的每一个元素 $s$，等价类就是所有与 $s$ 相关联的元素的集合，记作 $[s]$。

为什么等价要求自反性、对称性和传递性？ 等价关系的设计旨在将集合中的元素分组，使得每个组（即等价类）中的元素在某种意义上是“相同”的或具有某种共同特征。

例如所有字符串的集合上定义长度相等为一个等价关系。则 “dog” 和 “cat” 会被划分到一个等价类，“leet” 和 “code” 会被划分到另一个等价类。自反保证自身的一致性，对称保证等价不分先后，例如 “dog” 等价于 “cat” 与 “cat” 等价于 “dog“ 两个命题都是对的。传递性则保证完整性。传输 a 等价于 b 和 b 等价于 c 都成立，则他们三个应该在一组。

更严格的原因可以通过等价关系与集合划分等价定理来说明。

划分

分组/划分（partition）。 将一个集合分成若干个不相交的子集，这些子集的并集等于原集合。划分具有以下特征：

1. 不相交：每两个不同的子集是互不相交的，即没有公共元素。

2. 覆盖原集合：所有子集的并集等于原集合。

3. 非空：每个子集都是非空的。

等价关系与集合划分等价定理

等价关系与集合划分等价定理。

• 定理

  1. 给定集合 $X$ 上的一个等价关系 $\sim$，其等价类构成 $X$ 的一个划分。

  2. 反之，如果 $P = \{X_i\}$ 是集合 $X$ 的一个划分，那么可以定义一个等价关系，使得每个 $X_i$ 是一个等价类。

• 证明

  1. 等价关系到划分：

     • 假设 $\sim$ 是 $X$ 上的一个等价关系。

     • 对于任意 $x \in X$，自反性保证 $x \in [x]$，因此等价类 $[x]$ 非空。

     • 由于 $X = \bigcup_{x \in X} [x]$，这些等价类的并集覆盖整个 $X$。

     • 对于任意 $x, y \in X$，如果 $[x] \cap [y] \neq \emptyset$，则存在 $z \in [x] \cap [y]$，即 $z \sim x$ 且 $z \sim y$。由对称性和传递性，得到 $x \sim y$，因此 $[x] = [y]$。

     • 因此，等价类要么不相交，要么相等。

  2. 划分到等价关系：

     • 假设 $P = \{X_i\}$ 是 $X$ 的一个划分。

     • 定义关系 $\sim$ 为：如果 $x, y$ 属于同一个子集 $X_i$，则 $x \sim y$。

     • $\sim$ 是自反的，因为每个元素 $x$ 属于某个子集 $X_i$。

     • $\sim$ 是对称的，因为如果 $x \sim y$，则 $x, y$ 同属一个子集。

     • $\sim$ 是传递的，因为如果 $x \sim y$ 且 $y \sim z$，则 $x, y, z$ 同属一个子集。

     • 因此，$\sim$ 是一个等价关系。

等价类不相交性推论

等价类不相交性推论。 在一个等价关系下，两个等价类要么完全不相交，要么完全相等。证明：

• 假设 $[x]$ 和 $[y]$ 是集合 $X$ 上等价关系 $\sim$ 的两个等价类。

1. 假设 $[x] \cap [y] \neq \emptyset$：

   • 这意味着存在一个元素 $z$ 使得 $z \in [x]$ 且 $z \in [y]$，即 $z \sim x$ 且 $z \sim y$。

   • 根据等价关系的传递性和对称性，如果 $z \sim x$ 且 $z \sim y$，则 $x \sim y$。

   • 因此，对于任何 $a \in [x]$，由于 $a \sim x$ 且 $x \sim y$，传递性得出 $a \sim y$，即 $a \in [y]$。

   • 同理，对于任何 $b \in [y]$，有 $b \sim y$ 且 $y \sim x$，传递性得出 $b \sim x$，即 $b \in [x]$。

   • 由此可得 $[x] = [y]$。

2. 结论：

   • 如果两个等价类有交集，则它们实际上是相等的。

   • 因此，两个等价类要么不相交，要么完全相等。

整数

数学归纳法

数学归纳法。数学归纳法是 Peano 公理的一部分，即自然数的基本性质的一种，它是实现从有限到无限的证明的方式。

数学归纳法的第一原则

数学归纳法的第一原则。

• 设 $S(n)$ 是关于整数 $n$ 的一个命题，定义在自然数集合 $\mathbb{N}$ 上。

  1. 基始步：证明 $S(n_0)$ 对某个整数 $n_0$ 成立。

  2. 归纳步：假设 $S(k)$ 对所有 $k \geq n_0$ 成立，证明 $S(k+1)$ 也成立。

• 如果这两步都能证明，那么 $S(n)$ 对所有 $n \geq n_0$ 成立。

另一种表述形式：

• 令 $S$ 是自然数构成的集合。如果：

  1. $1 \in S$

  2. $\forall k \in \mathbb{N}$，成立 $k \in S \to k + 1 \in S$

1. 那么 $S = \mathbb{N}$

根据对自然数的实际定义情况，第一条可以是 $0 \in S$

数学归纳法的第二原则

数学归纳法的第二原则或“强归纳法”。

• 设 $S(n)$ 是关于整数 $n$ 的一个命题，定义在自然数集合 $\mathbb{N}$ 上。

  1. 基始步：证明 $S(n_0)$ 对某个整数 $n_0$ 成立。

  2. 强归纳步：假设 $S(n_0), S(n_0+1), \ldots, S(k)$ 都成立，证明 $S(k+1)$ 也成立。

• 如果这两步都能证明，那么 $S(n)$ 对所有 $n \geq n_0$ 成立。

良序原则

良序原则（Principle of Well-Ordering）。 自然数的每个非空子集都有一个最小元素。

引理：1是最小正自然数

引理：数学归纳法原理暗示1是最小的正自然数。

• 证明：设 $S = \{ n \in \mathbb{N} : n \geq 1 \}$。显然 $1 \in S$。假设 $n \in S$，因为 $0 < 1$，所以 $n = n + 0 < n + 1$。因此，$n+1 \in S$。根据数学归纳法，$S = \mathbb{N}$。

  • 注：此证明采用不含0的自然数定义。

• 证明思路分析：通过数学归纳法，证明表明从1开始，所有大于等于1的自然数都属于集合 S，从而确认1是最小的正整数。

定理：良序原则与数学归纳法是等价的

定理：良序原则与数学归纳法是等价的。 每个非空的自然数集合都有最小元。

证明：

采用排除 0 的自然数定义

1. 从良序原则推出数学归纳法

目标： 假设良序原则成立，证明数学归纳法成立。

数学归纳法的表述： 若集合 $S \subseteq \mathbb{N}$ 满足：

• $1 \in S$；

• 对任意 $k \in \mathbb{N}$，如果 $k \in S$，则 $k + 1 \in S$；

则 $S = \mathbb{N}$。

证明过程：

• 假设集合 $S \subseteq \mathbb{N}$ 满足上述两个条件，但 $S \neq \mathbb{N}$。则其补集 $\mathbb{N} \setminus S$ 非空。

  • 注：构造了数学归纳法的否定，以便反证。

• 根据良序原则，$\mathbb{N} \setminus S$ 存在最小元素，记为 $m$。

• 由于 $m \notin S$，根据条件 $1 \in S$，因此 $m > 1$。

  • 注：因为 $m \in \mathbb{N} \setminus S$ 所以 $m \notin S$

  • 注：因为 $m \in \mathbb{N} \setminus S$ 所以 $m \ne 1$，又因为自然数 $m > 0$，所以 $m > 1$

• 则 $m - 1 \in S$

  • 注：因为 $m$ 是 $\mathbb{N} \setminus S$ 的最小元，因此 $m - 1\not\in \mathbb{N} \setminus S$. 又因为 $m > 1$，故有。

• 根据数学归纳的第二条件，若 $k \in S$，则 $k + 1 \in S$。因此，$m - 1 \in S$ 推出 $m = (m - 1) + 1 \in S$。

  • 注：此处考虑 $k = m - 1$

• 这与 $m \notin S$ 矛盾。因此，假设不成立，故 $S = \mathbb{N}$。

2. 从数学归纳法推出良序原则

要从数学归纳法推出良序原则，我们需要证明每一个非空的自然数集合都有最小元。以下是详细的推导过程：

良序原则：每一个非空的自然数集合 $S \subseteq \mathbb{N}$ 都存在一个最小元，即存在 $m \in S$，使得对于所有 $s \in S$，有 $m \leq s$。

数学归纳法的基本形式包括两个步骤：

1. 基例：证明命题对最小的自然数（通常是 0 或 1）成立。

2. 归纳步骤：假设命题对某个自然数 $k$ 成立，进而证明命题对 $k+1$ 也成立。

现在，我们将使用数学归纳法来证明良序原则。

证明过程

目标：证明每一个非空的自然数集合 $S$ 都有最小元。

假设：反设存在一个非空的自然数集合 $S$，且 $S$ 没有最小元。

定义：设 $P(n)$ 表示：如果一个非空的自然数集合 $S \subseteq \mathbb{N}$ 满足 $S \subseteq \{1,2,\ldots,n\}$，则 $S$ 有最小元。

我们将通过数学归纳法证明对于所有 $n \in \mathbb{N}$，命题 $P(n)$ 成立。

基例 ($n = 1$)：

• 如果 $S \subseteq \{1\}$ 且 $S$ 非空，则 $S = \{1\}$。

• 因此，1 是 $S$ 的最小元。

• 所以，$P(1)$ 成立。

归纳步骤：

• 假设对于某个 $k \in \mathbb{N}$，命题 $P(k)$ 成立，即：任何非空的自然数集合 $S \subseteq \{1,2,\ldots,k\}$ 都有最小元。

• 现在考虑 $n = k+1$，即证明 $P(k+1)$ 成立。

• 令 $S \subseteq \{1,2,\ldots,k+1\}$ 且 $S$ 非空。

  有两种情况：

  1. 情况一：$k+1 \in S$。

     • 如果 $k+1$ 是 $S$ 的最小元，那么问题解决。

     • 如果 $k+1$ 不是最小元，那么 $S \setminus \{k+1\}$ 也是非空的，因为存在比 $k+1$ 小的元素。

     • 由于 $S \setminus \{k+1\} \subseteq \{1,2,\ldots,k\}$，根据归纳假设，$S \setminus \{k+1\}$ 有最小元。

  2. 情况二：$k+1 \notin S$。

     • 则 $S \subseteq \{1,2,\ldots,k\}$。

     • 根据归纳假设，$S$ 有最小元。

• 在这两种情况下，集合 $S$ 都存在最小元。

• 因此，$P(k+1)$ 成立。

思想。

• 当使用数学归纳法时，一个难点在于定义一个恰当的谓词 $P(n)$。

  • 本例中如果从“每一个非空的自然数集合”的角度试图定义集合，则难以与 $P(n)$ 直接关联，因为一般想到的是不同集合是任意的、不连续的。

  • 于是想到可以从集合的构成来定义，即从连续的自然数集合中选择不同的元素来构成。

• 此外就是如何让归纳步骤与假设产生关联。

  • 本例中利用新的成分 $k+1$ 的分类讨论将其中部分情况转化到假设，剩余的情况则可直接得出。

除法定理

除法定理。 对于任意整数 $a$ 和 $b$（其中 $b > 0$），存在唯一的整数 $q$ 和 $r$，使得：

$$
a = bq + r
$$

且

$$
0 \leq r < b
$$

证明：

• $q$ 和 $r$ 的存在性：

  1. 集合定义：

     • 定义集合 $S = \{ a - bk : k \in \mathbb{Z}, a - bk \geq 0 \}$。

  2. 集合 $S$ 非空：

     • 如果 $0 \in S$，则 $b$ 整除 $a$，可以设 $q = a/b$ 且 $r = 0$。

     • 如果 $a > 0$，则 $a - b \cdot 0 = a \in S$。

     • 如果 $a < 0$，则 $a - b(2a) = a(1-2b) \in S$。

     • 因此，$S$ 非空。这意味着 $r$ 的存在性。

  3. 良序原则：

     • 根据良序原则，$S$ 有最小元素，记为 $r = a - bq$。

     • 这意味着 $a = bq + r$，且 $r \geq 0$。

  4. $r$ 的界限：

     • 假设 $r \geq b$。则 $a - b(q+1) = a - bq - b = r - b \geq 0$。

     • 这意味着 $r - b$ 也在 $S$ 中，与 $r$ 是最小元素矛盾。

     • 因此，$r < b$。

• $q$ 和 $r$ 的唯一性：

  1. 假设有两组表示：

     • 假设存在整数 $q, r$ 和 $q', r'$ 满足：

       
       $$
       a = bq + r \quad \text{且} \quad a = bq' + r'
       $$
       

       
       $$
       0 \leq r, r' < b
       $$
       

  2. 等式和可整除性：

     • 则 $bq + r = bq' + r'$。

     • 重排得 $b(q - q') = r' - r$。

     • 由于 $0 \leq r, r' < b$，所以 $r' - r = 0$。

     • 因此，$r = r'$ 且 $q = q'$。

思想。

• 求某个值的存在性，则为其构造集合，转为证明集合非空。

  • 本例转换为求 $\{ a-bk \}$ 的存在性。

    • 首先考虑当 0 位于集合时，代表 $a-bk = 0$ 可成立。$q,r$ 皆存在。

    • 注意到 $k$ 是可以任选的。

    • 取 $k=0$ 时，集合为 $\{ a \}$，此时 $a = b\cdot 0 + r$，需要让 $r \geq 0$。因此才分类讨论 $a > 0$ 的情况。

    • 此时还未讨论 $a < 0$ 的情况。需要找到一个 $k$ 值，使得 $a - bk \geq 0$。取 $k=a$ 是不够的，于是取 $k = 2a$，这样确保 $a - b(2a) = a - 2ab = a(1-2b)$ 两个因式都小于 0.

  • 集合非空，正整数，要素齐全，说明存在最小元 $r = a - bq \geq 0$。

  • 剩下要证明 $r < b$。

    • 想直接反证 $a - bq \geq b$ 则 是困难的。

    • 但可以考虑作差 $r - b <0$，代入 $r = a - bq$ 得到 $a - bq - b < 0$

    • 即 $a - (q + 1)b < 0$，其否定为 $a - (q+1)b \geq 0$，满足 $S$ 的定义

    • 这表示 $r - b \in S$，与 $r$ 是最小元素矛盾。

    • 这里利用做差构造出 $q+1$，来龙去脉是清晰的。

• 唯一性的证明比较简单，即假设不唯一然后推出他们同一。

最大公约数

最大公约数。 对于两个整数 a 和 b，它们的最大公约数是满足以下条件的最大正整数 d：

1. d 是 a 的约数（即 a 可以被 d 整除）

2. d 是 b 的约数（即 b 可以被 d 整除）

用数学符号表示，可以写作：

$$
GCD(a,b) = \max\{d \in \mathbb{Z}^+ : d|a \text{ and } d|b\}
$$

其中：

• $\mathbb{Z}^+$ 表示正整数集

• $d|a$ 表示 d 整除 a

• $\max$ 表示取最大值

性质：

1. 线性组合性质：存在整数 x 和 y，使得 $GCD(a,b) = ax + by$

2. 唯一性：满足上述条件的 d 是唯一的

3. 非负性：对于 a 和 b 不全为 0 的情况，GCD(a,b) 总是正的

4. 如果 a = b = 0，则规定 GCD(0,0) = 0

这个定义可以扩展到两个以上的整数，即求多个整数的最大公约数。对于整数 $a_1, a_2, ..., a_n$，它们的最大公约数是能够同时整除所有这些数的最大正整数。

贝祖定理（Bézout’s Theorem）

贝祖定理（Bézout’s Theorem）。 对于任意两个非零整数 $a$ 和 $b$，存在整数 $r$ 和 $s$，使得它们的最大公约数可以表示为 $ar + bs$。此外，$a$ 和 $b$ 的最大公约数是唯一的。

证明：

1. 定义集合 $S$： 定义集合 $S = \{am + bn : m, n \in \mathbb{Z} \text{ 且 } am + bn > 0\}$。这个集合包含所有可以表示为 $am + bn$ 的正整数。

2. 利用良序原理： 根据良序原理，任何非空的正整数集合都有一个最小元素。因为 $S$ 非空，所以 $S$ 中存在一个最小的正整数，记作 $d = ar + bs$。

3. 假设 $d$ 不是最大公约数： 假设 $d \neq \gcd(a, b)$，考察 $a,d$ 的关系。根据除法原理，存在余数 $r'$ 使得 $a = dq + r'$ 且 $0 \leq r' < d$。

4. 推导矛盾： 如果 $r' > 0$，则

   
   $$
   r' = a - dq = a - (ar + bs)q = a(1 - rq) + b(-sq),
   $$
   

   这意味着 $r'$ 也是集合 $S$ 的一个元素。然而，这与 $d$ 是集合 $S$ 的最小正整数相矛盾。因此，$r' = 0$，说明 $d$ 整除 $a$。同理，$d$ 也整除 $b$。

5. 唯一性证明： 假设 $d'$ 是另一个 $a$ 和 $b$ 的公约数，则 $d' \mid a$ 且 $d' \mid b$。因为 $d = ar + bs$，所以 $d' \mid d$。因此，$d$ 是 $a$ 和 $b$ 的唯一最大公约数。

推论：两个互素整数存在表示为 1 的线性组合

贝祖定理推论：两个互素整数存在表示为 1 的线性组合。 如果 $a$ 和 $b$ 互素（即 $\gcd(a, b) = 1$），那么存在整数 $r$ 和 $s$，使得 $ar + bs = 1$。

扩展欧几里得算法

目标。 扩展欧几里得算法用于计算两个整数 $a$ 和 $b$ 的最大公约数 $\gcd(a, b)$，并找到整数 $r$ 和 $s$，使得 $ar + bs = \gcd(a, b)$。

扩展欧几里得算法。

1. 欧几里得算法：计算 $\gcd(a, b)$ 的步骤是反复使用除法，直到余数为零。

   • 设 $a = bq_1 + r_1$

   • 继续用 $b$ 和 $r_1$ 做除法：$b = r_1q_2 + r_2$

   • 重复以上步骤，直到余数为零。

2. 扩展步骤：在计算每一步的同时，记录如何表示余数为前面两个数的线性组合。

   • 通过反向代入，逐步找到 $r$ 和 $s$。

代码。

 1def extended_gcd(a, b):
 2    if a == 0 and b == 0:
 3        return (0, 0, 0)  # Both a and b are 0, gcd is undefined
 4    
 5    if a == 0:
 6        return (b, 0, 1)  # GCD is b, r = 0, s = 1
 7    
 8    if b == 0:
 9        return (a, 1, 0)  # GCD is a, r = 1, s = 0
10    
11    r0, r1, s0, s1 = 1, 0, 0, 1
12    
13    while b != 0:
14        q, a, b = a // b, b, a % b
15        r0, r1 = r1, r0 - q * r1
16        s0, s1 = s1, s0 - q * s1
17    
18    return (a, r0, s0)
19
20print(extended_gcd(48, 18)) # (6, -1, 3)
21print(extended_gcd(0, 5))   # (5, 0, 1)
22print(extended_gcd(9, 9))   # (9, 0, 1)
23print(extended_gcd(5, 0))   # (5, 1, 0)
24print(extended_gcd(0, 0))   # (0, 0, 0)

素数

素数。 设 $p$ 是一个大于1的整数。如果 $p$ 只有1和 $p$ 本身两个正因数，则称 $p$ 为素数。大于1的非素数称为合数。

欧几里得引理

欧几里得引理。 设 $a$ 和 $b$ 是整数，且 $p$ 是素数。如果 $p$ 除 $ab$，那么 $p$ 要么除 $a$，要么除 $b$。

欧几里得引理证明。 假设 $p$ 不除 $a$，需要证明 $p$ 除 $b$。因为 $\gcd(a, p) = 1$，存在整数 $r$ 和 $s$ 使得 $ar + ps = 1$。因此，$b = b \cdot 1 = (ab)r + p(bs)$。观察表达式右边的每一项：$p$ 除 $ab$ 和 $p(bs)$，所以 $p$ 必须除 $b$。

无限素数引理

无限素数引理。 存在无限多个素数。

无限素数引理证明。

• 反证法。

  • 假设只有有限多个素数，记为 $p_1, p_2, \ldots, p_n$。令 $P = p_1p_2 \cdots p_n + 1$。

    • 注：+1 是为了确保 P 不能被已知的素数整除，产生 1 的余数。

  • 如果素数的数量有限，那么 $P$ 必须能被某个 $p_i$ 整除，但 $P - p_1p_2 \cdots p_n = 1$，这意味着 $P$ 除以其中一个或多个总产生余数 1.

    • 这是因为 $P$ 除以 $p_1p_2 \cdots p_n$ 部分的余数总是 0.

    • 而除以 $1$ 的部分余数总是 $1$.

    • 合起来，余数总是 $1$

  • 导致矛盾（$P$ 无法通过已知的素数合成）。因此，$P$ 要么是素数，要么存在一个不在 $p_i$ 中的素数能整除 $P$。

• 注：这并不能说明 $P$ 是一个素数。它可能是大于 $p_1,p_2 \cdots p_n$ 中任何一个的新的素数组合的合数。

算术基本定理

算术基本定理。

• 设 $n$ 是一个大于1的整数，则 $n$ 可以唯一分解为素数的乘积，即

  
  $$
  n = p_1 p_2\cdots p_k
  $$
  

• 其中 $p_1, \ldots, p_k$ 是素数（不一定不同）。进一步地，这种分解是唯一的；即如果

  
  $$
  n = p_1 p_2 \cdots p_k = q_1 q_2 \cdots q_l
  $$
  

  则 $k = l$ 且 $p_i$ 和 $q_i$ 是相同的素数，只是顺序不同。

算术基本定理的证明。

• 唯一性。

  • 首先，对于 $n = 2$，这个情况显然成立，因为2是质数。

  • 然后，假设对于所有小于 $n$ 的整数，其质因数分解都是唯一的。

  • 现在考虑整数 $n$，假设 $n$ 有两种不同的质因数分解方式：

  
  $$
    n = p_1 p_2 \ldots p_k = q_1 q_2 \ldots q_l
  $$
  

  $

    - 其中 $p_1 \leq p_2 \leq \ldots \leq p_k$ 和 $q_1 \leq q_2 \leq \ldots \leq q_l$，且 $p_i$ 和 $q_j$ 都是质数。
    - 根据质数的定义和性质，$p_1$ 必定等于 $q_1$（因为质数只能被1和自身整除），从而可以将两边同时除以 $p_1$，得到：
  
    $$
    p_2 \ldots p_k = q_2 \ldots q_l
    $$
  
    - 由归纳假设，小于 $n$ 的数的质因数分解是唯一的，因此 $k = l$ 且每个 $p_i$ 对应相等的 $q_i$。这证明了 $n$ 的质因数分解也是唯一的。
  

• 存在性。

  • 假设存在一些整数不能被写成质数的乘积形式，设 $S$ 为这样的所有整数的集合。根据良序原理，集合 $S$ 必有一个最小元素，设为 $a$。

    • 如果 $a$ 是质数，则 $a$ 已经是质数的乘积，这与 $a$ 属于 $S$ 矛盾。

    • 如果 $a$ 不是质数，则 $a$ 可以被分解为两个更小的数的乘积，即 $a = a_1 a_2$，其中 $1 < a_1, a_2 < a$。

      • 根据 $a$ 是 $S$ 中最小的元素，$a_1$ 和 $a_2$ 不属于 $S$，即它们可以被分解为质数的乘积。

      • 因此，$a$ 也可以被分解为质数的乘积，这与 $a$ 属于 $S$ 矛盾。

米勒-拉宾素性测试

米勒-拉宾测试（Miller-Rabin Primality Test）是一个概率性的素性测试方法，它非常适合用于生成大素数。虽然它有一个小概率会错误地将一个合数判断为素数，但通过多次测试可以将这个错误概率降低到非常小。

算法描述：

• 将 $n-1$ 分解为 $2^s \cdot d$，使得 $d$ 是奇数。

• 随机选择一个数 $a$（$1 < a < n-1$）。

• 计算 $x = a^d \mod n$。

• 如果 $x = 1$ 或 $x = n-1$，则 $n$ 可能是素数。

• 否则，重复计算 $x = x^2 \mod n$ 直到 $s-1$ 次。如果在这过程中 $x$ 变为 $n-1$，则 $n$ 可能是素数。

• 如果上述测试都没有判断 $n$ 是素数，那么 $n$ 是合数。

Python 实现：

 1import random
 2import time
 3
 4def miller_rabin(n, k):
 5    if n % 2 == 0:
 6        return False
 7    r, d = 0, n - 1
 8    while d % 2 == 0:
 9        d >>= 1
10        r += 1
11    for _ in range(k):
12        a = random.randrange(2, n - 1)
13        x = pow(a, d, n)
14        if x == 1 or x == n - 1:
15            continue
16        for _ in range(r - 1):
17            x = pow(x, 2, n)
18            if x == n - 1:
19                break
20        else:
21            return False
22    return True
23
24def generate_large_prime(length, max_tries=1000):
25    tries = 0
26    while tries < max_tries:
27        p = random.getrandbits(length)
28        p |= (1 << (length - 1)) | 1  # Ensure p is odd and has the correct bit length
29        if miller_rabin(p, 40):
30            return p
31        tries += 1
32    raise Exception("Failed to generate a prime within the maximum number of tries")
33
34# Generate a 1024-bit prime
35try:
36    print(generate_large_prime(1024))
37except Exception as e:
38    print(e)

群

半群

半群（Semigroup）由一个集合和一个在此集合上的二元运算所组成，满足以下条件：

1. 封闭性：对于集合中的任意两个元素 $a$ 和 $b$，其运算结果 $a \cdot b$ 也必须属于这个集合。

2. 结合律：对于集合中的任意三个元素 $a$，$b$，和 $c$，必须满足 $(a \cdot b) \cdot c = a \cdot (b \cdot c)$。

简单来说，半群是一个只满足封闭性和结合律的代数结构。

为什么要把结合律设置为半群的要素？

避免运算的结果依赖于操作数的顺序。

幺半群

如果半群存在单位元，则成为幺半群。

群

一个群由一个集合和一个在此集合上的二元运算组成，满足以下条件：

1. 封闭性：对于集合中的任意两个元素 $a$ 和 $b$，其运算结果 $a \cdot b$ 也必须属于这个集合。

2. 结合律：对于集合中的任意三个元素 $a$，$b$，和 $c$，必须满足 $(a \cdot b) \cdot c = a \cdot (b \cdot c)$。

3. 单位元存在：集合中存在一个特殊的元素 $e$，称为单位元，使得对于集合中的任何元素 $a$，都有 $e \cdot a = a \cdot e = a$。

4. 逆元存在：对于集合中的每一个元素 $a$，存在另一个元素 $b$ 在集合中，使得 $a \cdot b = b \cdot a = e$，这里的 $b$ 称为 $a$ 的逆元。

简而言之，存在单位元和逆元的半群是群。

群的一个典型例子是整数集合 $\mathbb{Z}$ 配合加法运算。在这个例子中，加法运算满足封闭性和结合律，加法的单位元是0（即对任何整数 $a$，有 $0 + a = a + 0 = a$），每个整数 $a$ 的逆元是 $-a$（即 $a + (-a) = 0$）。因此，整数集合配合加法运算构成一个群。

群的基本性质

单位元的唯一性。 存在且仅存在一个元素 $e$ 在群 $G$ 中，使得对所有 $g$ 在 $G$ 中都有 $eg = ge = g$。

单位元的唯一性证明：

• 假设 $e$ 和 $e'$ 都是 $G$ 中的单位元，即 $eg = ge = g$ 和 $e'g = ge' = g$ 对所有 $g$ 在 $G$ 中成立。

• 需要证明 $e = e'$。

  • 如果我们认为 $e$ 是单位元，那么 $ee' = e'$；

  • 如果 $e'$ 是单位元，那么 $ee' = e$。

  • 结合这两个等式，我们得到 $e = e'$。

逆元的唯一性。 如果 $g$ 是群 $G$ 中的任意元素，那么 $g$ 的逆元，记作 $g^{-1}$，是唯一的。

逆元的乘法性质

让 $G$ 是一个群，如果 $a, b$ 属于 $G$，那么 $(ab)^{-1} = b^{-1}a^{-1}$.

证明： 设 $a, b$ 属于 $G$。那么 $abb^{-1}a^{-1} = aa^{-1} = e$。类似地，$b^{-1}a^{-1}ab = b^{-1}b = e$。

根据逆元的唯一性，如果某个元素 $x$ 满足 $xy = yx = e$，那么 $x$ 必然是 $y$ 的逆元。在这个情况下，$b^{-1}a^{-1}$ 使得与 $ab$ 的乘积为单位元 $e$，因此 $b^{-1}a^{-1}$ 是 $ab$ 的逆元。，$(ab)^{-1} = b^{-1}a^{-1}$。

推论：让 $G$ 是一个群，如果 $a \in G$ 则 $(a^{-1})^{-1} = a$

解的唯一性

设 $G$ 是一个群，$a$ 和 $b$ 是 $G$ 中的任意两个元素。那么方程 $ax = b$ 和 $xa = b$ 在 $G$ 中有唯一解。

证明： 假设 $ax = b$。我们必须证明存在这样一个 $x$。我们可以通过两边左乘 $a^{-1}$（$a$ 的逆元）来找到 $x$：$x = a^{-1}b$。

为了证明解的唯一性，假设 $x_1$ 和 $x_2$ 都是 $ax = b$ 的解，即 $ax_1 = b$ 和 $ax_2 = b$。所以 $ax_1 = ax_2$。根据消去律，我们有 $x_1 = x_2$。

同理，方程 $xa = b$ 的解也是唯一的，证明方法类似。

消去律

如果 $G$ 是一个群，并且 $a, b, c$ 是 $G$ 中的元素，那么 $ba = ca$ 意味着 $b = c$；同样，$ab = ac$ 也意味着 $b = c$。

这是关于群中指数律的定理，描述了群中元素的幂运算的基本规则。下面是这个定理的中文翻译及解释：

群中的指数律

在一个群中，常见的指数律成立；也就是说，对于所有 $g, h$ 属于群 $G$，以下性质成立：

1. 乘法指数律：$g^m g^n = g^{m+n}$ 对所有整数 $m, n$ 成立。

2. 幂的幂：$(g^m)^n = g^{mn}$ 对所有整数 $m, n$ 成立。

3. 逆元的幂：$(gh)^n = (h^{-1} g^{-1})^n$ 对所有整数 $n$ 成立。

此外，如果群 $G$ 是交换群（阿贝尔群），则 $(gh)^n = g^n h^n$。

常见的半群

1. 所有的群都是半群。

2. 考虑是半群但不是群的结构，一般分为两类，一类是缺乏单位元，一类是缺乏逆元。

   1. 缺乏逆元：

      1. 自然数的加法：集合 $\mathbb{N} = \{0, 1, 2, 3, \ldots\}$ 配合加法运算构成一个半群。这个结构满足封闭性和结合律，但不是群，因为除了0之外的其他自然数没有加法逆元。

      2. 正整数的乘法：集合 $\mathbb{N}^+ = \{1, 2, 3, \ldots\}$ 配合乘法运算也构成一个半群。这个结构同样满足封闭性和结合律，但不是群，因为除了1之外的其他正整数没有乘法逆元。

      3. 矩阵的乘法：特定大小的矩阵集合，如所有 $n \times n$ 的非奇异矩阵配合矩阵乘法运算，构成一个半群。这个结构满足封闭性和结合律，但不一定每个矩阵都有逆矩阵，尤其是当考虑所有 $n \times n$ 矩阵（包括奇异矩阵）时。

      4. 函数的复合：给定集合上的所有函数配合函数复合运算构成一个半群。例如，集合 $X$ 上的所有从 $X$ 到 $X$ 的函数，配合复合运算。这个结构满足封闭性和结合律，但函数复合通常没有逆运算。

   2. 缺乏单位元：

      1. 正整数的加法：集合 $\mathbb{N}^+ = \{1, 2, 3, \ldots\}$ 配合加法运算构成一个半群。这个结构满足封闭性和结合律，但没有单位元，因为在正整数中没有任何一个数可以使得对任意的 $n$ 都有 $n + e = n$。

      2. 非空字符串的连接：考虑所有非空字符串的集合，配合字符串连接操作构成一个半群。例如，集合 $\{\text{"a"}, \text{"b"}, \text{"ab"}, \text{"ba"}, \ldots\}$ 配合字符串连接操作。这个结构满足封闭性和结合律，但没有单位元（即不存在一个空字符串元素使得任何字符串连接空字符串等于字符串本身）。

      3. 正方形矩阵的乘法（不包括零矩阵）：考虑所有 $n \times n$ 非零矩阵的集合，这些矩阵配合矩阵乘法运算构成一个半群。这个结构满足封闭性和结合律，但没有单位元，因为不包括单位矩阵。

      4. 正实数的乘法：集合 $\mathbb{R}^+ = \{x \in \mathbb{R} : x > 0\}$ 配合乘法运算构成一个半群。这个结构满足封闭性和结合律，但没有单位元，因为只考虑正实数，不包括1。

模运算的定义

给定两个整数 $a$ 和 $n$，$n$ 不为零，$a$ 模 $n$ 的结果是一个整数 $r$，满足以下条件：

• $r = a - nk$，其中 $k$ 是使得 $r$ 是非负且小于 $n$ 的整数的值。

写作：

$$
a \equiv r \mod n
$$

这表示 $a$ 除以 $n$ 的余数是 $r$。

模运算的性质

1. 闭合性：对于任何整数 $a$ 和 $b$，和 $(a + b) \mod n$ 和积 $(a \times b) \mod n$ 都是定义良好的整数。

2. 结合律：加法和乘法的模运算满足结合律。

3. 分配律：模运算对于加法和乘法都满足分配律。

mod n 同余关系

定义：模 $n$ 同余关系

对于任意整数 $a$ 和 $b$，如果 $n$ 能够整除 $a - b$，即存在一个整数 $k$ 使得

$$
a - b = kn
$$

则称 $a$ 与 $b$ 关于模 $n$ 同余，记作

$$
a \equiv b \ (\mathrm{mod}\ n)
$$

性质：mod n 同余关系是等价的。 整数 mod n 等价类构成的集合记作 $\mathbb{Z}_{n}$

证明。

1. 自反性（Reflexive） 任意整数 $a$，有

$$
a - a = 0
$$

且 $0$ 可以表示为 $0 \times n$，所以 $n$ 整除 $a - a$。因此，

$$
a \equiv a \ (\mathrm{mod}\ n)
$$

证明自反性成立。 2. 对称性（Symmetric） 假设 $a \equiv b \ (\mathrm{mod}\ n)$，即 $n$ 整除 $a - b$，那么存在整数 $k$ 使得

$$
a - b = kn
$$

则

$$
b - a = -kn
$$

因为 $-k$ 也是整数，所以 $n$ 也整除 $b - a$。因此，

$$
b \equiv a \ (\mathrm{mod}\ n)
$$

证明对称性成立。

3. 传递性（Transitive） 假设 $a \equiv b \ (\mathrm{mod}\ n)$ 且 $b \equiv c \ (\mathrm{mod}\ n)$，即

   • $n$ 整除 $a - b$，存在整数 $k$ 使得 $a - b = kn$

   • $n$ 整除 $b - c$，存在整数 $m$ 使得 $b - c = mn$ 将两式相加，得到

$$
(a - b) + (b - c) = a - c = (k + m)n
$$

说明 $n$ 整除 $a - c$，即

$$
a \equiv c \ (\mathrm{mod}\ n)
$$

证明传递性成立。

对称群

对称群 $S_n$

对称群 $S_n$ 是由所有 $n$ 个元素的排列（置换）所组成的群。

• 阶：对称群 $S_n$ 的阶（即元素的个数）为 $n!$。

• 群运算：群运算通常采用排列的复合，即依次执行多个排列。

以 $S_3$ 为例，它是包含 3 个元素的对称群，具体来说，它是由三个不同元素（例如 $\{1, 2, 3\}$）的所有排列组成的群。

$S_3$ 的元素

$S_3$ 包含以下 6 个排列：

1. 恒等排列 $e$：不改变任何元素的位置。

   
   $$
   e = \begin{pmatrix}
   1 & 2 & 3 \\
   1 & 2 & 3
   \end{pmatrix}
   $$
   

2. 置换 $(12)$：交换元素 1 和 2。

   
   $$
   (12) = \begin{pmatrix}
   1 & 2 & 3 \\
   2 & 1 & 3
   \end{pmatrix}
   $$
   

3. 置换 $(13)$：交换元素 1 和 3。

   
   $$
   (13) = \begin{pmatrix}
   1 & 2 & 3 \\
   3 & 2 & 1
   \end{pmatrix}
   $$
   

4. 置换 $(23)$：交换元素 2 和 3。

   
   $$
   (23) = \begin{pmatrix}
   1 & 2 & 3 \\
   1 & 3 & 2
   \end{pmatrix}
   $$
   

5. 循环置换 $(123)$：1 → 2, 2 → 3, 3 → 1。

   
   $$
   (123) = \begin{pmatrix}
   1 & 2 & 3 \\
   2 & 3 & 1
   \end{pmatrix}
   $$
   

6. 循环置换 $(132)$：1 → 3, 3 → 2, 2 → 1。

   
   $$
   (132) = \begin{pmatrix}
   1 & 2 & 3 \\
   3 & 1 & 2
   \end{pmatrix}
   $$
   

   群的结构

$S_3$ 中的元素可以通过置换的复合来进行群运算。例如：

• $(12) \circ (13) = (123)$

• $(123) \circ (132) = e$

$(12) \circ (13) = (123)$

• $(13)$ 的作用：

  • $1 \to 3$

  • $3 \to 1$

  • $2$ 不变

• $(12)$ 的作用：

  • $1 \to 2$

  • $2 \to 1$

  • $3$ 不变

复合运算 $(12) \circ (13)$ 从右到左进行：

• 作用于 1：

  • $(13)$ 将 $1 \to 3$

  • $(12)$ 对 $3$ 不起作用，所以 $1 \to 3$

• 作用于 2：

  • $(13)$ 对 $2$ 不起作用，所以 $2 \to 2$

  • $(12)$ 将 $2 \to 1$

• 作用于 3：

  • $(13)$ 将 $3 \to 1$

  • $(12)$ 将 $1 \to 2$

结果是 $(123)$，即：

$$
1 \to 3, \quad 2 \to 1, \quad 3 \to 2 
$$

$(123) \circ (132) = e$

• $(132)$ 的作用：

  • $1 \to 3$

  • $3 \to 2$

  • $2 \to 1$

• $(123)$ 的作用：

  • $1 \to 2$

  • $2 \to 3$

  • $3 \to 1$

复合运算 $(123) \circ (132)$ 从右到左进行：

• 作用于 1：

  • $(132)$ 将 $1 \to 3$

  • $(123)$ 将 $3 \to 1$

• 作用于 2：

  • $(132)$ 将 $2 \to 1$

  • $(123)$ 将 $1 \to 2$

• 作用于 3：

  • $(132)$ 将 $3 \to 2$

  • $(123)$ 将 $2 \to 3$

结果是恒等置换 $e$，即：

$$
1 \to 1, \quad 2 \to 2, \quad 3 \to 3 
$$

因此，$(123) \circ (132) = e$。

符号表示与循环表示

在 $S_3$ 中，排列常用循环表示法来表示。一个置换可以分解为若干个不相交的循环。例如：

• $(123)$ 表示一个 3-循环，依次将 1 送到 2，将 2 送到 3，将 3 送回 1。

• $(12)$ 表示一个 2-循环（也称为交换置换），只交换元素 1 和 2，元素 3 保持不动。

模加法群

对于任何正整数 $n$，整数集合 $\{0, 1, 2, \dots, n-1\}$ 配合模 $n$ 的加法运算形成一个群，称为模加法群或加法循环群 $\mathbb{Z}/n\mathbb{Z}$。这个群的运算规则是：

$$
a \oplus b = (a + b) \mod n
$$

在这个群中：

• 封闭性：任何两个元素的和，模 $n$ 后仍然是集合 $\{0, 1, 2, \dots, n-1\}$ 中的元素。

• 结合律：加法的结合律保持不变，即 $(a \oplus b) \oplus c = a \oplus (b \oplus c)$。

• 单位元：$0$ 是单位元，因为对任何元素 $a$，有 $a \oplus 0 = a$。

• 逆元：每个元素 $a$ 的逆元是 $n-a$，满足 $a \oplus (n-a) = 0$。

模乘法群

对于模 $n$ 的乘法来说，不是所有元素都能形成群，因为不是每个元素在模 $n$ 下都有乘法逆元。只有当元素与 $n$ 互质（即元素和 $n$ 的最大公约数为 1）时，该元素才有逆元。集合 $\mathbb{Z}_n^*$ 包含了所有与 $n$ 互质的整数，这个集合配合模 $n$ 的乘法运算可以形成一个群，称为模乘法群。

在模乘法群中：

• 封闭性：互质的元素相乘，其结果模 $n$ 后仍然与 $n$ 互质。

• 结合律：乘法的结合律保持不变，即 $(a \cdot b) \cdot c = a \cdot (b \cdot c)$。

• 单位元：$1$ 是单位元，因为对任何与 $n$ 互质的元素 $a$，有 $a \cdot 1 = a$。

• 逆元：每个与 $n$ 互质的元素 $a$ 都存在一个逆元 $b$，使得 $a \cdot b \equiv 1 \pmod{n}$。

Cayley 表

Cayley 表（Cayley Table）用于表示群的运算规则。以下是一个简单的例子，展示了模 3 的整数加法群 $\mathbb{Z}_3 = \{0, 1, 2\}$：

$$
\begin{array}{c|ccc}
+ & 0 & 1 & 2 \\
\hline
0 & 0 & 1 & 2 \\
1 & 1 & 2 & 0 \\
2 & 2 & 0 & 1 \\
\end{array}
$$

• 行和列：代表群中的元素。

• 单元格：表示行元素和列元素的加法结果，模 3 计算。

例如，第二行和第三列的交叉点是 1 + 2，结果是 0（因为 $1 + 2 = 3 \equiv 0 \mod 3$）。

一般线性群

$GL_2(\mathbb{R})$ 表示所有 $2 \times 2$ 可逆矩阵的集合，在矩阵乘法下形成一个群，这样的群称为一般线性群。

1. 矩阵的可逆性：

   • 一个矩阵 $A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}$ 是可逆的，当且仅当其行列式不为零，即 $\det(A) = ad - bc \neq 0$。

2. 单位矩阵：

   • $GL_2(\mathbb{R})$ 的单位元是 $I = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$。

3. 逆矩阵：

   • 矩阵 $A$ 的逆是

   
   $$
   A^{-1} = \frac{1}{ad - bc} \begin{pmatrix} d & -b \\ -c & a \end{pmatrix}
   $$
   

4. 群性质：

   • 矩阵乘法是结合的。

   • 两个可逆矩阵的乘积仍然是可逆的。

   • 矩阵乘法一般不是交换的（即 $AB \neq BA$），因此 $GL_2(\mathbb{R})$ 是一个非交换群（非阿贝尔群）。

这些性质说明了 $GL_2(\mathbb{R})$ 在矩阵乘法下形成一个群。

四元数群

下面描述了四元数群 $Q_8$，其元素是特定的 $2 \times 2$ 矩阵。以下是一些关键点：

• $I = \begin{pmatrix} 0 & 1 \\ -1 & 0 \end{pmatrix}$

• $J = \begin{pmatrix} 0 & i \\ i & 0 \end{pmatrix}$

• $K = \begin{pmatrix} i & 0 \\ 0 & -i \end{pmatrix}$

关系

• $I^2 = J^2 = K^2 = -1$

• $IJ = K$, $JK = I$, $KI = J$

• $JI = -K$, $KJ = -I$, $IK = -J$

• 元素集合：$\{ \pm 1, \pm I, \pm J, \pm K \}$

• $Q_8$ 是一个非交换群（非阿贝尔群），因为乘法不满足交换律。

非零复数群

非零复数集合 $\mathbb{C}^*$ 在乘法运算下构成一个群。

性质

1. 集合：

   • $\mathbb{C}^*$ 是所有非零复数的集合。

2. 运算：

   • 乘法是定义在 $\mathbb{C}^*$ 上的二元运算。

3. 单位元：

   • 单位元是 1，因为对于任何复数 $z$，有 $z \cdot 1 = z$。

4. 逆元：

   • 对于非零复数 $z = a + bi$，其逆元是：

   
   $$
   z^{-1} = \frac{a - bi}{a^2 + b^2}
   $$
   

   这个逆元确保 $z \cdot z^{-1} = 1$。

5. 结合性：

   • 复数乘法是结合的。

单位群

定义

• 单位：在模 $n$ 下，一个整数 $a$ 是单位，如果存在一个整数 $b$ 使得 $a \times b \equiv 1 \pmod{n}$。

• 单位群 $U(n)$：由所有小于 $n$ 且与 $n$ 互质的整数组成的集合。

性质

• 群性质：单位群在模 $n$ 下的乘法运算中是一个群。这意味着它满足封闭性、结合性，有单位元（即 1），并且每个元素都有逆元。

• 阶：单位群的阶（元素个数）是欧拉函数 $\phi(n)$ 的值，表示小于 $n$ 且与 $n$ 互质的整数的个数。

示例

对于 $n = 9$，单位群 $U(9)$ 是 $\{1, 2, 4, 5, 7, 8\}$，因为这些数与 9 互质。

子群

设 $G$ 是一个群，$H$ 是 $G$ 的一个非空子集。如果 $H$ 本身在 $G$ 的运算下也是一个群，则称 $H$ 是 $G$ 的一个子群（Subgroup），记作 $H \leq G$。

具体条件： 为了确保 $H$ 是 $G$ 的子群，通常需要满足以下三个条件（群的子群判别定理）：

1. 封闭性：对于任意 $a, b \in H$，有 $ab \in H$。

2. 存在逆元：对于任意 $a \in H$，其逆元 $a^{-1} \in H$。

3. 包含单位元：$H$ 包含 $G$ 的单位元 $e$。

子群判别定理

子群判别定理。 如果 $H$ 非空，且对任意 $a, b \in H$，有 $ab^{-1} \in H$，则 $H$ 是 $G$ 的子群。

证明。

• 首先，根据条件，$H$ 是非空的。这保证了 $H$ 至少含有一个元素。

• 单位元。

  • 取 $a = b$（因为 $a, b \in H$），则根据条件有：

  
  $$
    ab^{-1} = aa^{-1} = e \in H
  $$
  

  $

  • 其中，$e$ 是群 $G$ 的单位元。因此，单位元 $e$ 在 $H$ 中。

• 逆元。

  • 利用条件 $ab^{-1} \in H$。因为 $e \in H$ 且 $a \in H$，将 $b = e$ 代入条件，有：

$$
ae^{-1} = a e = a \in H
$$

- 同理 $a^{-1} \in H$（因为 $H$ 对任意元素的逆元也是封闭的）。

• 闭合性。
  • 然后，对于任意 $a, b \in H$，由于 $b^{-1} \in H$，根据条件（代入 $b = b^{-1}$）：

$$
a (b^{-1})^{-1} = a b \in H
$$

- 因此，$H$ 在群运算下是封闭的。

• 因此 $H$ 是 $G$ 的子群。

真子群

如果 $H$ 是 $G$ 的子群，且 $H$ 本身不等于 $G$，即 $H \neq G$，则称 $H$ 是 $G$ 的一个真子群（Proper Subgroup），记作 $H < G$。

说明：

• 真子群强调的是子群不等于整个群本身。

• 每个群至少有两个真子群：包含单位元的平凡子群 $\{e\}$ 和群本身（如果认为群本身也是真子群，则不成立，因为真子群需满足 $H \neq G$）。

共轭操作的定义

共轭（Conjugation） 在一个群 $G$ 中，由某个元素 $g$ 定义的共轭映射。具体定义如下：

给定群 $G$ 中的任意一个元素 $g$，定义映射 $\phi_g: G \to G$ 为

$$
\phi_g(x) = g x g^{-1}, \quad \forall x \in G。
$$

这个映射 $\phi_g$ 就称为由 $g$ 定义的共轭映射。通过共轭映射得到的新元素 $\phi_g(x)$ 被称为 $x$ 的共轭元素，记作 $x^g = g x g^{-1}$。

共轭关系在群中是一种等价关系，这意味着：

1. 自反性：对任意 $x \in G$，有 $x^e = exe^{-1} = x$（其中 $e$ 是群的单位元）。

2. 对称性：如果 $y = x^g$，则 $x = y^{g^{-1}}$。

3. 传递性：如果 $y = x^g$ 且 $z = y^h$，则 $z = x^{gh}$。

因此，共轭关系将群 $G$ 分割成若干共轭类，每个共轭类包含互为共轭的元素。

共轭等价关系证明

在群论中，共轭关系定义为：对于群 $G$ 中的元素 $a$ 和 $b$，若存在 $g \in G$ 使得 $b = g a g^{-1}$，则称 $a$ 与 $b$ 是共轭的，记作 $a \sim b$。

为了证明共轭关系是一个等价关系，我们需要验证它满足自反性、对称性和传递性这三个性质。

• 自反性。

  • 取群中的单位元 $e$，则

  
  $$
    e a e^{-1} = e a e = a
  $$
  

  $

  • 因此，存在 $g = e \in G$ 使得 $a = g a g^{-1}$，即 $a \sim a$。

• 对称性。

  • 假设 $a \sim b$，即存在 $g \in G$ 使得

  
  $$
    b = g a g^{-1}
  $$
  

  $

  • 我们需要找到一个元素 $h \in G$ 使得 $a = h b h^{-1}$。观察到选取 $h = g^{-1}$，则

  
  $$
    h b h^{-1} = g^{-1} b g = g^{-1} (g a g^{-1}) g = a
  $$
  

  $

  • 因此，$b \sim a$。

• 传递性。

  • 假设 $a \sim b$ 和 $b \sim c$，即存在 $g, h \in G$ 使得

  
  $$
    b = g a g^{-1} \quad \text{和} \quad c = h b h^{-1}
  $$
  

  $

  • 将 $b$ 的表达式代入 $c$ 的表达式中，得到

  
  $$
    c = h (g a g^{-1}) h^{-1} = (h g) a (h g)^{-1}
  $$
  

  $

  • 设 $k = h g \in G$，则

  
  $$
    c = k a k^{-1}
  $$
  

  $

  • 因此，存在 $k \in G$ 使得 $a \sim c$。

共轭操作的几何视角

从几何角度来看，共轭操作可以理解为对对称性的“变换”。具体来说，可以将群视为描述某种几何对象对称性的群（比如旋转对称群、镜像对称群等），而共轭操作则对应于在不同的参考系下观察这些对称操作。

对称群 $S_3$

考虑正三角形的对称群 $S_3$，包含6个元素：3个旋转（包括恒等变换）和3个反射。

1. 旋转：

   • 恒等变换 $e$

   • 顺时针旋转 $r$（120°）

   • 顺时针旋转 $r^2$（240°）

2. 反射：

   • 关于通过顶点1的对称轴的反射 $s_1$

   • 关于通过顶点2的对称轴的反射 $s_2$

   • 关于通过顶点3的对称轴的反射 $s_3$

在这个群中，共轭操作可以解释为在不同的参考框架下观察反射和旋转。例如，假设我们取一个旋转 $r$ 来共轭一个反射 $s_1$：

$$
r s_1 r^{-1} = s_2
$$

这表示，如果我们先旋转正三角形，再进行关于顶点2的反射，最后逆旋转回原位置，其效果与直接对顶点1进行反射是相同的。因此，反射 $s_1$ 和 $s_2$ 是共轭的。

提醒： 在群论中采用右结合运算顺序。$r s_1 r^{-1}$ 的含义是：首先执行 $r^{-1}$（逆时针旋转 120°），然后执行 $s_1$（关于顶点1的反射），最后执行 $r$（顺时针旋转 120°）。

矩阵群中的共轭操作

考虑一般线性群 $GL(n, \mathbb{C})$，即所有 $n \times n$ 可逆矩阵组成的群。在这个群中，共轭操作对应于相似变换。

具体来说，给定矩阵 $A$ 和可逆矩阵 $P$，共轭操作为：

$$
P A P^{-1}
$$

从几何角度看，这种操作相当于在不同基底下表示线性变换 $A$，本质上不改变其固有性质（如特征值、秩等），但可能改变其具体的矩阵形式。例如，所有与对角矩阵共轭的上三角矩阵具有相同的特征值，从而属于同一个共轭类。

例子：三维空间中的绕轴旋转。

在三维空间中，旋转群 $SO(3)$ 的元素表示绕某一轴的旋转。共轭操作可以用来改变旋转轴的方向。

假设我们有一个绕 $z$-轴的旋转矩阵 $R_z(\theta)$，表示绕 $z$-轴旋转角度 $\theta$：

$$
R_z(\theta) = \begin{bmatrix}
\cos \theta & -\sin \theta & 0 \\
\sin \theta & \cos \theta & 0 \\
0 & 0 & 1
\end{bmatrix}
$$

如果我们想将这个旋转轴从 $z$-轴变为另一个方向，比如 $x$-轴，我们可以使用一个旋转矩阵 $Q$ 来实现这一点。假设 $Q$ 是将 $z$-轴转到 $x$-轴的旋转矩阵：

$$
Q = \begin{bmatrix}
0 & 0 & 1 \\
0 & 1 & 0 \\
-1 & 0 & 0
\end{bmatrix}
$$

通过共轭操作，我们可以得到新的旋转矩阵 $R_x(\theta)$：

$$
R_x(\theta) = Q R_z(\theta) Q^{-1}
$$

计算 $Q^{-1}$：

$$
Q^{-1} = Q^T = \begin{bmatrix}
0 & 0 & -1 \\
0 & 1 & 0 \\
1 & 0 & 0
\end{bmatrix}
$$

计算共轭结果：

$$
R_x(\theta) = \begin{bmatrix}
0 & 0 & 1 \\
0 & 1 & 0 \\
-1 & 0 & 0
\end{bmatrix}
\begin{bmatrix}
\cos \theta & -\sin \theta & 0 \\
\sin \theta & \cos \theta & 0 \\
0 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
0 & 0 & -1 \\
0 & 1 & 0 \\
1 & 0 & 0
\end{bmatrix}
$$

这会得到一个绕 $x$-轴旋转的矩阵。这个过程展示了如何通过共轭操作将旋转轴从 $z$-轴变为 $x$-轴，体现了共轭操作在几何中的意义：通过坐标变换改变旋转的参考系。

下面的程序提供了此过程的可视化：

 1import numpy as np
 2import matplotlib.pyplot as plt
 3
 4def rotation_z(theta):
 5    return np.array([
 6        [np.cos(theta), -np.sin(theta), 0],
 7        [np.sin(theta), np.cos(theta), 0],
 8        [0, 0, 1]
 9    ])
10    
11Q = np.array([
12    [0, 0, 1],
13    [0, 1, 0],
14    [-1, 0, 0]
15])
16
17Q_inv = Q.T
18
19theta = np.pi / 4  
20
21R_z = rotation_z(theta)
22R_x = Q @ R_z @ Q_inv
23
24origin = np.array([[0, 0, 0], [0, 0, 0], [0, 0, 0]])
25axis = np.array([[1, 0, 0], [0, 1, 0], [0, 0, 1]])
26
27def plot_and_save(ax, rotated_axis, filename, title):
28    ax.quiver(*origin, *axis, color=['r', 'g', 'b'], linewidth=2)
29    ax.quiver(*origin, *rotated_axis, color=['r', 'g', 'b'], linestyle='dashed')
30    ax.set_xlim([-1, 1])
31    ax.set_ylim([-1, 1])
32    ax.set_zlim([-1, 1])
33    ax.set_xlabel('X')
34    ax.set_ylabel('Y')
35    ax.set_zlabel('Z')
36    ax.set_title(title)
37    plt.savefig(filename)
38    plt.close()
39    
40fig = plt.figure()
41ax = fig.add_subplot(111, projection='3d')
42plot_and_save(ax, axis, 'step_0_original.png', 'Original Axes')
43
44fig = plt.figure()
45ax = fig.add_subplot(111, projection='3d')
46rotated_axis_z = R_z @ axis
47plot_and_save(ax, rotated_axis_z, 'step_1_rotate_z.png', 'Rotation around Z-axis')
48
49fig = plt.figure()
50ax = fig.add_subplot(111, projection='3d')
51rotated_axis_x = R_x @ axis
52plot_and_save(ax, rotated_axis_x, 'step_2_rotate_x.png', 'Rotation around X-axis')

可以看到，虽然我们没有显式编写一个绕 X 轴旋转的矩阵，但利用 $Q$ 是将 $z$-轴转到 $x$-轴，我们相当于在 $x$-轴 应用了绕 $z$-轴旋转变换，然后再将结果转回。

例子：二维空间中的局部旋转

下面的例子示范了对三角形的旋转。共轭操作的直观原理是将三角形平移到参考点（原点）然后施加旋转，然后再平移回原位置。读者可自行运行查看效果。

 1import numpy as np
 2import matplotlib.pyplot as plt
 3
 4triangle = np.array([[1, 1], [2, 3], [3, 1]])
 5
 6triangle_homogeneous = np.hstack((triangle, np.ones((triangle.shape[0], 1))))
 7
 8tx, ty = -2, -2
 9
10T = np.array([
11    [1, 0, tx],
12    [0, 1, ty],
13    [0, 0, 1]
14])
15
16T_inv = np.array([
17    [1, 0, -tx],
18    [0, 1, -ty],
19    [0, 0, 1]
20])
21
22theta = np.radians(45)
23
24R = np.array([
25    [np.cos(theta), -np.sin(theta), 0],
26    [np.sin(theta), np.cos(theta), 0],
27    [0, 0, 1]
28])
29
30def plot_triangle(triangle, title, filename):
31    plt.figure()
32    plt.plot(*triangle.T, 'o-', label='Triangle')
33    plt.fill(*triangle.T, alpha=0.3)
34    plt.xlim(-3, 5)
35    plt.ylim(-3, 5)
36    plt.gca().set_aspect('equal', adjustable='box')
37    plt.title(title)
38    plt.grid(True)
39    plt.savefig(filename)
40    plt.close()
41
42triangle_translated = (T @ triangle_homogeneous.T).T
43plot_triangle(triangle_translated[:, :2], 'Translated to Origin', 'step2_translated.png')
44
45triangle_rotated = (R @ triangle_translated.T).T
46plot_triangle(triangle_rotated[:, :2], 'Rotated', 'step3_rotated.png')
47
48triangle_final = (T_inv @ triangle_rotated.T).T
49plot_triangle(triangle_final[:, :2], 'Moved Back', 'step4_final.png')
50
51plot_triangle(triangle, 'Original Triangle', 'step1_original.png')

验证复数 $a+bi$ 与 $a-bi$ 的共轭性

• 复数的矩阵形式

  • 为了在群论的框架下研究复数的共轭性，我们可以将复数 $z = a + bi$ 表示为二维实矩阵。具体而言，复数 $z$ 对应的矩阵 $M_z$ 定义为：

    
    $$
      M_z = \begin{pmatrix}
      a & -b \\
      b & a
      \end{pmatrix}
    $$
    

    $

  • 这种表示方法保持了复数的加法和乘法性质，使得复数的运算可以转化为矩阵的运算。例如，两个复数 $z_1 = a + b i$ 和 $z_2 = c + d i$ 的和对应矩阵的和：

    
    $$
      M_{z_1} + M_{z_2} = \begin{pmatrix}
      a + c & -(b + d) \\
      b + d & a + c
      \end{pmatrix} = M_{z_1 + z_2}
    $$
    

    $

  • 以及乘法对应矩阵的乘法。

• 目标：

  • 考虑复数对应的矩阵群 $\text{GL}(2, \mathbb{R})$（即所有可逆的 $2 \times 2$ 实矩阵组成的群），我们希望寻找一个矩阵 $P \in \text{GL}(2, \mathbb{R})$，使得：

    
    $$
      P M_z P^{-1} = M_{\overline{z}}
    $$
    

    $

  • 其中 $\overline{z} = a - bi$，对应的矩阵为：

    
    $$
      M_{\overline{z}} = \begin{pmatrix}
      a & b \\
      - b & a
      \end{pmatrix}
    $$
    

    $

• 选择适当的共轭矩阵 $P$：

  • 考虑交换矩阵：

  
  $$
    P = \begin{pmatrix}
    0 & 1 \\
    1 & 0
    \end{pmatrix}
  $$
  

  $

  • 计算 $P M_z P^{-1}$：

  
  $$
    P M_z P^{-1} = \begin{pmatrix}
    0 & 1 \\
    1 & 0
    \end{pmatrix}
    \begin{pmatrix}
    a & -b \\
    b & a
    \end{pmatrix}
    \begin{pmatrix}
    0 & 1 \\
    1 & 0
    \end{pmatrix} = \begin{pmatrix}
    a & b \\
    - b & a
    \end{pmatrix} = M_{\overline{z}}
  $$
  

  $

• 因此，存在矩阵 $P \in \text{GL}(2, \mathbb{R})$（在本例中，$P$ 为交换矩阵），使得 $M_z$ 和 $M_{\overline{z}}$ 是彼此的共轭元素。这验证了在群 $\text{GL}(2, \mathbb{R})$ 中，复数 $a + bi$ 和 $a - bi$ 是共轭的。

正规子群

定义。设 $H$ 是群 $G$ 的一个子群，若对于 $G$ 中的任意元素 $g$，都有 $gHg^{-1} = H$，即 $\forall g \in G, \ gH g^{-1} = H$，则称 $H$ 是 $G$ 的一个正规子群（Normal Subgroup），记作 $H \trianglelefteq G$。

等价条件： 正规子群可以通过多种等价条件来定义，包括但不限于：

1. 左陪集等于右陪集：对于任意 $g \in G$，有 $gH = Hg$。

2. 商群的存在：若 $H$ 是正规子群，则可以构造商群 $G/H$，使得 $G/H$ 本身也是一个群。

3. 结合子群：正规子群在群的同态下具有很好的性质，例如同态映射的核总是正规子群。

示例

• 在阿贝尔群中，所有子群都是正规子群，因为 $gH g^{-1} = H$ 对所有 $g \in G$ 都成立。

• 非阿贝尔群中可能存在非正规子群，例如交错群 $A_4$ 的某些子群。

共轭与正规子群

要理解正规子群的定义 $gHg^{-1} = H$（其中 $H$ 是群 $G$ 的一个子群，$g \in G$），可以从共轭（Conjugation）的角度来分析。

给定群 $G$ 中的一个元素 $g$ 和子群 $H$，我们可以通过「共轭」操作将 $H$ 中的每一个元素 $h$ 转换为 $ghg^{-1}$。具体地，整个子群 $H$ 在元素 $g$ 下的共轭是：

$$
gHg^{-1} = \{ ghg^{-1} \mid h \in H \}
$$

一个子群 $H$ 被称为群 $G$ 的正规子群，如果对于 $G$ 中的任意元素 $g$，都有：

$$
gHg^{-1} = H
$$

这意味着，不论你选择群 $G$ 中哪一个元素 $g$，经过共轭操作后，子群 $H$ 依然保持不变。

这意味着正规子群具有：

• 不变性：正规子群在整个群 $G$ 下保持不变。这种不变性使得我们能够构造商群 $G/H$，因为在正规子群的基础上，群的乘法运算是良好定义的（后文解释）。

• 左陪集与右陪集相同：由于 $H$ 是正规子群，$G$ 的左陪集和右陪集是一致的。这一性质在许多群论的定理和应用中起到了关键作用。

• 同态核：正规子群可以视为某个群同态的核。具体来说，如果存在一个群同态 $\phi: G \to K$，使得 $H = \ker(\phi)$，那么 $H$ 必然是 $G$ 的正规子群。

从直观上看，正规子群 $H$ 是群 $G$ 中一个在「内部结构上对称且稳定」的部分。无论我们如何通过群 $G$ 的元素对 $H$ 进行「旋转」或「翻转」（即共轭操作），$H$ 都不会改变其自身的结构和性质。这种稳定性使得正规子群在构建更复杂的群结构（如商群）时成为不可或缺的工具。

例子：考虑实数的加法群 $(\mathbb{R}, +)$ 和其子群 $H = \mathbb{Z}$（整数集合）。对于任意 $g \in \mathbb{R}$，有：

$$
g + \mathbb{Z} - g = \mathbb{Z}
$$

这表明 $\mathbb{Z}$ 是 $\mathbb{R}$ 的正规子群。从结构观点，表明对整数在数轴上平移，然后移回，整数自身不变。

反例：考虑对称群 $S_3$（所有排列的群）和其子群 $H = \{ e, (1\,2) \}$。取 $g = (1\,3)$，则：

$$
gHg^{-1} = \{ e, (1\,3)(1\,2)(1\,3)^{-1} \} = \{ e, (2\,3) \} \neq H
$$

因此，$H$ 不是 $S_3$ 的正规子群。从结构观点，对于 $(1,2)$，先进行 $(1,3)$ 置换，再进行 $(1,2)$ 置换，最后 $(3,1)$ 无法换回 $(1,2)$。

循环群

循环子群和循环群

在群 $G$ 中，由单个元素 $a$ 生成的子群称为循环子群，记作 $\langle a \rangle$。它包含所有 $a$ 的整数次幂（如果群运算是乘法）或整数倍（如果群运算是加法）。元素 $a$ 称为生成元（Generator）。

例子。 由 3 生成的整数子群 $3\mathbb{Z}$ 包含所有 3 的倍数，如 $\{ \ldots, -6, -3, 0, 3, 6, \ldots \}$。 例子。 子群 $H = \{ 2^n : n \in \mathbb{Z} \}$ 是非零有理数的乘法群的一个子群。它由元素 2 生成，包含所有 2 的幂。

最小子群定理。 对于群 $G$ 中的任意元素 $a$，集合 $\langle a \rangle = \{ a^k : k \in \mathbb{Z} \}$ 是 $G$ 的一个子群，并且是包含 $a$ 的最小子群。

在使用加法记号时，由 $a$ 生成的循环子群写作 $\{ na : n \in \mathbb{Z} \}$。

循环群：如果一个群 $G$ 可以由单个元素 $a$ 生成，那么 $G$ 称为循环群，$a$ 是 $G$ 的生成元。

元素的阶：元素 $a$ 的阶是满足 $a^n = e$（单位元）的最小正整数 $n$。如果不存在这样的 $n$，则 $a$ 的阶是无限的。

• 这么定义是为了反映这个生成序列的最小周期性。

单位群是循环群

好的，我们先用 $U(9)$ （即模 9 的乘法单位群）作为示范，然后证明对于任意质数 $p$，单位群 $U(p)$ 是一个循环群。

示例：$U(9)$ 的结构

定义： $U(9)$ 表示模 9 的乘法单位群，即所有与 9 互素的整数在模 9 下的乘法群。具体来说：

$$
U(9) = \{1, 2, 4, 5, 7, 8\}
$$

验证 $U(9)$ 是否为循环群：

我们需要找到一个生成元 $g$，使得 $U(9)$ 中的每一个元素都可以表示为 $g$ 的幂。

取 $g = 2$，计算其幂：

$$
\begin{align*}
2^1 &\equiv 2 \mod 9 \\
2^2 &\equiv 4 \mod 9 \\
2^3 &\equiv 8 \mod 9 \\
2^4 &\equiv 16 \equiv 7 \mod 9 \\
2^5 &\equiv 32 \equiv 5 \mod 9 \\
2^6 &\equiv 64 \equiv 1 \mod 9 \\
\end{align*}
$$

经过计算，我们得到：

$$
\{2^1, 2^2, 2^3, 2^4, 2^5, 2^6\} = \{2, 4, 8, 7, 5, 1\} = U(9)
$$

因此，$2$ 是 $U(9)$ 的一个生成元，$U(9)$ 是一个循环群，记作 $C_6$。

定理：每个循环群都是阿贝尔群

每个循环群都是阿贝尔群（即交换群）。

证明。

假设 $G$ 是一个循环群，$\alpha$ 是 $G$ 的生成元。对于 $G$ 中的任意元素 $g$ 和 $h$，它们可以表示为 $\alpha$ 的幂：

• $g = \alpha^r$

• $h = \alpha^s$

为了证明 $G$ 是阿贝尔群，我们需要证明 $gh = hg$。

计算 $gh$ 和 $hg$：

• $gh = \alpha^r \alpha^s = \alpha^{r+s}$

• $hg = \alpha^s \alpha^r = \alpha^{s+r}$

由于加法满足交换律，即 $r+s = s+r$，所以 $\alpha^{r+s} = \alpha^{s+r}$。

因此，$gh = hg$，这表明 $G$ 是阿贝尔群。

定理：循环群的子群是循环群

每个循环群的子群也是循环群。

证明。 假设 $G$ 是由元素 $a$ 生成的循环群，$H$ 是 $G$ 的一个子群。

1. 简单情况：如果 $H = \{e\}$（只包含单位元），那么 $H$ 自然是循环的。

2. 一般情况：

   • 设 $H$ 包含一个不同于单位元的元素 $g$。因此，$g$ 可以表示为 $a^n$。

   • 因为 $H$ 是子群，所以它包含 $a^n$ 的所有正幂（运算封闭性，通过反复生成可得到所有正幂）。

   • 使用良序原理，设 $m$ 是使 $a^m \in H$ 的最小正整数。

3. 生成元：

   • 证明 $h = a^m$ 是 $H$ 的生成元。

   • 对于任意 $h' \in H$，可以表示为 $a^k$。

   • 使用除法原理，将 $k$ 表示为 $k = mq + r$，其中 $0 \leq r < m$。

   • 于是，$a^k = a^{mq+r} = (a^m)^q a^r$。

4. 矛盾推理：

   • 因为 $a^k$ 和 $(a^m)^q$ 都在 $H$，所以 $a^r$ 也在 $H$（封闭性，$(a^m)^{-q} \in H$）。

   • 但 $m$ 是最小的使得 $a^m \in H$ 的正整数，所以 $r = 0$。

   • 这意味着 $h' = a^k = (a^m)^q = h^q$。

因此，$H$ 是由 $h$ 生成的循环群。

结论：$\mathbb{Z}$ 的子群是 $n\mathbb{Z}$

$\mathbb{Z}$ 的子群是 $n\mathbb{Z}$，其中 $n = 0, 1, 2, \ldots$。

命题：能被阶数整除的幂是单位元

设 $G$ 是一个阶为 $n$ 的循环群，$a$ 是其生成元。$a^k = e$ 当且仅当 $n$ 整除 $k$。

证明。

• 设 $G$ 是一个阶为 $n$ 的循环群，生成元为 $a$。这意味着 $G = \{ e, a, a^2, \ldots, a^{n-1} \}$

• 必要性。

  • 根据除法原理，可以将 $k$ 写成 $k = nq + r$，其中 $0 \leq r < n$。

  • 假设 $a^k = e$。其阶为 $n$，即 $a^n = e$。我们有：

  • 
    $$
    $$
    

  • a^k = a^{nq + r} = (a^n)^q \cdot a^r = e^q \cdot a^r = a^r = e

  • 
    $$
    $$
    

  • 因此，$a^r = e$。$r=0$，因此 $k=nq$，因此 $n|k$。

• 充分性。

  • 假设 $k = n \cdot q$，其中 $q$ 是某个整数。

  • 则 $a^k = a^{n \cdot q} = (a^n)^q$。

  • 已知 $a^n = e$，因此 $(a^n)^q = e^q = e$。

  • 所以 $a^k = e$。

定理：群阶整除群阶与元素指数的最大公约数得到元素阶

• 内容：设 $G$ 是一个阶为 $n$ 的循环群，$a$ 是其生成元。如果 $b = a^k$，则 $b$ 的阶为 $n/d$，其中 $d = \gcd(k, n)$。

• 证明：

  • 目标：根据元素阶定义，需要找到最小的整数 $m$ 使得 $a^{km} = e$。

  • 根据上一个命题，$n/d$ 必须整除 $m \cdot (k/d)$。

  • 因为给定 $d = \gcd(k, n)$，意味着 $n/d$ 和 $k/d$ 互质，所以 $n/d$ 必须整除 $m$。

结论：与阶互质者均可生成其乘法循环群

$\mathbb{Z}_n$ 的生成元是满足 $\gcd(r, n) = 1$ 的整数 $r$，其中 $1 \leq r < n$。这意味着质数 $p$ 的单位群 $U(p)$ 都是循环群。

例子 群 $\mathbb{Z}_{16}$。

数字 1, 3, 5, 7, 9, 11, 13, 和 15 是 $\mathbb{Z}_{16}$ 中与 16 互质的元素。每个这样的元素都能生成 $\mathbb{Z}_{16}$。例如：

• $1 \cdot 9 = 9$

• $2 \cdot 9 = 2$

• $3 \cdot 9 = 11$

• $4 \cdot 9 = 4$

• $5 \cdot 9 = 13$

• $6 \cdot 9 = 6$

• $7 \cdot 9 = 15$

• $8 \cdot 9 = 8$

• $9 \cdot 9 = 1$

• $10 \cdot 9 = 10$

• $11 \cdot 9 = 3$

• $12 \cdot 9 = 12$

• $13 \cdot 9 = 5$

• $14 \cdot 9 = 14$

• $15 \cdot 9 = 7$

复数的定义

复数可以被定义为形如 $z = a + bi$ 的数，其中 $a$ 和 $b$ 是实数，$i$ 是虚数单位，满足 $i^2 = -1$。这里，$a$ 被称为复数的实部，$b$ 被称为复数的虚部。

记作：

$$
\mathbb{C} = \{ a + bi \mid a, b \in \mathbb{R},\ i^2 = -1 \}
$$

复数构成一个域

域（Field） 是一个具备加法、减法、乘法和除法（除零外）运算的集合，并满足相应的运算性质。复数集合 $\mathbb{C}$ 在加法和乘法下封闭，且所有非零复数都有乘法逆元，因此 $\mathbb{C}$ 构成一个域。

复数是实数域的扩展

复数域 $\mathbb{C}$ 可以看作是实数域 $\mathbb{R}$ 的一个代数扩展。具体来说，$\mathbb{C}$ 是通过引入虚数单位 $i$，使得 $i^2 = -1$ 的扩展，从而成为一个复二维的向量空间。

复数的代数闭包

根据代数闭域定理（基本代数定理），每个非常数多项式在复数域上都有至少一个根。这意味着复数域 $\mathbb{C}$ 是代数闭的，即任何在 $\mathbb{C}$ 上的多项式都可以因式分解为一次因式的乘积。

复数的基本性质

复数的加法和乘法遵循如下规则：

• 加法：

$$
(a + bi) + (c + di) = (a + c) + (b + d)i
$$

• 乘法：

$$
(a + bi) \cdot (c + di) = (ac - bd) + (ad + bc)i
$$

这些运算满足交换律、结合律以及分配律，使得复数在加法和乘法下形成交换群和交换环。

对于非零复数 $z = a + bi$，其乘法逆元为：

$$
z^{-1} = \frac{a - bi}{a^2 + b^2}
$$

这保证了 $\mathbb{C}$ 中每个非零元素都有乘法逆元，因此 $\mathbb{C}$ 在乘法下构成一个乘法群。

• 共轭复数：对于 $z = a + bi$，其共轭复数为 $\overline{z} = a - bi$。

• 模：复数 $z = a + bi$ 的模定义为：

$$
|z| = \sqrt{a^2 + b^2}
$$

模具有如下性质：

• $|z| \geq 0$，且 $|z| = 0$ 当且仅当 $z = 0$。

• $|z \cdot w| = |z| \cdot |w|$。

• $|z + w| \leq |z| + |w|$（三角不等式）。

复数的表示形式

复数可以通过多种方式表示，包括：

• 代数形式：$z = a + bi$。

• 极坐标形式：$z = r(\cos \theta + i \sin \theta)$，其中 $r = |z|$，$\theta = \arg(z)$。

• 指数形式：利用欧拉公式，可以表示为 $z = re^{i\theta}$。

这些表示形式在不同的计算和理论分析中具有不同的优势。

非零复数的乘法群

$\mathbb{C}^*$ 定义为所有非零复数组成的集合，即

$$
\mathbb{C}^* = \mathbb{C} \setminus \{0\}
$$

在此集合上定义乘法运算，即对于任意 $z_1, z_2 \in \mathbb{C}^*$，运算为

$$
z_1 \cdot z_2 = z_1 z_2
$$

$\mathbb{C}^*$ 在乘法下是一个群.

证明：

1. 封闭性：对于任意 $z_1, z_2 \in \mathbb{C}^*$，由于 $z_1 \neq 0$ 且 $z_2 \neq 0$，则 $z_1 z_2 \neq 0$。因此，$z_1 \cdot z_2 \in \mathbb{C}^*$。

2. 结合律：复数乘法满足结合律，即对于任意 $z_1, z_2, z_3 \in \mathbb{C}^*$，

   
   $$
   (z_1 \cdot z_2) \cdot z_3 = z_1 \cdot (z_2 \cdot z_3)
   $$
   

3. 单位元存在：在 $\mathbb{C}^*$ 中，单位元为 $1$，因为对于任意 $z \in \mathbb{C}^*$，

   
   $$
   1 \cdot z = z \cdot 1 = z
   $$
   

4. 逆元存在：对于任意 $z \in \mathbb{C}^*$，其逆元为 $z^{-1} = \frac{1}{z}$，因为

   
   $$
   z \cdot z^{-1} = z^{-1} \cdot z = 1
   $$
   

   并且 $z^{-1} \in \mathbb{C}^*$，因为 $z \neq 0$。

单位圆群

复数单位模构成的群 $S^1 = \{ z \in \mathbb{C} \mid |z| = 1 \}$ 称为单位圆群 $T$。

单位圆群是 $\mathbb{C}^*$ 的一个子群。

虽然单位圆群的阶是无限的，但它包含许多有趣的有限子群。例如，集合 $H = \{1, -1, i, -i\}$ 是单位圆群的一个子群，满足 $z^4 = 1$ 的复数称为四次单位根。

德莫弗定理

德莫弗定理（De Moivre’s Theorem）是复分析中的一个重要定理，通常表述为：

$$
(\cos \theta + i \sin \theta)^n = \cos(n\theta) + i \sin(n\theta)
$$

可以利用欧拉公式（Euler’s Formula）来证明这个定理。

欧拉公式表明，对于任意实数 $\theta$，有：

$$
e^{i\theta} = \cos \theta + i \sin \theta
$$

两边同时取 $n$ 次幂：

$$
\left(e^{i\theta}\right)^n = \left(\cos \theta + i \sin \theta\right)^n
$$

根据复数的指数运算性质，左边可以简化为：

$$
\left(e^{i\theta}\right)^n = e^{i n \theta}
$$

根据欧拉公式，右边的表达式也可以展开为：

$$
e^{i n \theta} = \cos(n\theta) + i \sin(n\theta)
$$

因此，我们得到：

$$
\left(\cos \theta + i \sin \theta\right)^n = \cos(n\theta) + i \sin(n\theta)
$$

n 次单位根定理

如果 $z^n = 1$，那么 $n$ 次单位根为：

$$
z = e^{\left(\frac{2\pi i k}{n}\right)} 
$$

其中 $k = 0, 1, \ldots, n-1$。这些 $n$ 次单位根形成一个 $n$ 阶的循环群。

此外，$n$ 次单位根的生成元称为原始 $n$ 次单位根。

证明：

步骤一：寻找 $n$ 次单位根

考虑复数 $z$ 满足 $z^n = 1$。由于 $1$ 可以表示为复平面上的单位圆上的点，即 $1 = e^{2\pi i k}$ 对任意整数 $k$ 成立。因此，我们有

$$
z^n = e^{2k\pi i}, \quad k \in \mathbb{Z}.
$$

根据德莫弗定理 $z = e^{2k\pi/n}$

步骤二：构成循环群

考虑这些单位根在复数乘法下的运算。我们需要验证它们满足群的四个公理：

1. 封闭性：任意两个单位根的积仍然是单位根。设 $z_k = e^{\frac{2\pi i k}{n}}$ 和 $z_m = e^{\frac{2\pi i m}{n}}$，则 $z_k \cdot z_m = e^{\frac{2\pi i (k + m)}{n}}$，当 $k + m$ 超过 $n-1$ 时，模 $n$ 后仍然属于上述形式。

2. 结合律：复数乘法天然满足结合律。

3. 单位元：$z_0 = e^{0} = 1$ 是乘法的单位元。

4. 逆元：对于任意 $z_k$，其逆元为 $z_{n-k} = e^{\frac{2\pi i (n - k)}{n}} = e^{- \frac{2\pi i k}{n}}$，满足 $z_k \cdot z_{n-k} = 1$。

因此，这些单位根在乘法下构成一个群。

步骤三：证明是循环群

要证明这是一个循环群，即存在一个生成元，使得群中的所有元素都可以由该生成元的幂得到。

取 $z_1 = e^{\frac{2\pi i}{n}}$，我们可以得到

$$
z_1^k = \left(e^{\frac{2\pi i}{n}}\right)^k = e^{\frac{2\pi i k}{n}} = z_k, \quad k = 0, 1, 2, \ldots, n-1.
$$

因此，$z_1$ 是该群的生成元，群是一个循环群，且阶为 $n$。