有限循环群的基本定理

Last updated on Nov 1, 2025

循环群基本定理为循环群中循环子群的存在性提供了保证。

在有限域上多项式的数论变换 (NTT) 以及 ZK-STARKs 中的 FRI 操作的上下文中，我们需要阶（元素数量）为 2 的幂的乘法子群。循环群基本定理使我们能够快速确定特定的有限域是否具有该阶的乘法子群。

我们将首先介绍以下预备知识，然后再深入探讨循环群基本定理：

子群的定义
群或子群的阶
乘法群中元素的幂
循环子群、循环群及其生成元

1. 子群的定义

给定一个群 $G$ ，如果 $G$ 的子集 $H$ 相对 $G$ 中的群运算也构成一个群，则 $H$ 是 $G$ 的子群。换句话说，如果我们将范围限制在 $H$ 的元素，但继续使用 $G$ 的群运算，群的所有判定标准仍然成立。最重要的是，运算在 $H$ 中必须是封闭的，因此每当我们对 $H$ 的两个元素应用该运算时，得到的结果必须是 $H$ 中的另一个元素。

子群示例

模 8 整数加法构成一个群 $ℤ_{8} = ({0, 1, 2, 3, 4, 5, 6, 7}, +)$ 。 $H_{1} = ({0, 2, 4, 6}, +)$ 和 $H_{2} = ({0, 4}, +)$ 都是 $ℤ_{8}$ 的子群。另一方面， $H_{3} = ({0, 2}, +)$ 则不是，因为 $(2 + 2) \in̸ H_{3}$ 。

2. 群或子群的阶

群 $G$ 的阶（用 $| G |$ 表示）是指其包含的元素数量。如果一个群不是有限的，则称其阶为无限。

群和子群的阶示例

考虑上例中的群 $ℤ_{8}$ 。 $ℤ_{8}$ 的阶为 8，即 $| ℤ_{8} | = 8$ （因为群中恰好有 8 个元素）。此外，子群 $H = ({0, 2, 4, 6}, +)$ 的阶为 4（即 $| H | = 4$ ）。

3. 乘法群中元素的幂

如果 $g \in G$ ，元素 $g$ 的所有幂（用 $⟨ g ⟩$ 表示）构成集合 ${g^{i} : i \in ℤ}$ 。例如，考虑模 7 的非零整数乘法群 $G = {1, 2, 3, 4, 5, 6}$ 。在 $G$ 中，元素 $3$ 的幂如下：

\begin{matrix} 3 的幂 = ⟨ 3 ⟩ = {3^{0}, 3^{1}, 3^{2}, 3^{3}, 3^{4}, 3^{5}, 3^{6}, \dots} . \end{matrix}

因为：

\begin{matrix} 3^{0} = 1, \\ 3^{1} = 3, \\ 3^{2} = 9 \equiv 2, \\ 3^{3} = 9 * 3 \equiv 2 * 3 \equiv 6, \\ 3^{4} = 9 * 9 \equiv 2 * 2 \equiv 4, \\ 3^{5} = 9 * 9 * 3 \equiv 2 * 2 * 3 \equiv 12 \equiv 5, \\ 3^{6} = 9 * 9 * 9 \equiv 2 * 2 * 2 \equiv 8 \equiv 1. \end{matrix}

$3^{7}$ 又是多少呢？

3^{7} = 3^{6} * 3 \equiv 1 * 3 \equiv 3 (\mod 7) .

因此， $⟨ 3 ⟩ = {1, 2, 3, 4, 5, 6}$ 。对于每一个 $i > 6$ 的幂 $3^{i}$ ，其结果都将是此列表中已存在的元素之一。

练习：找出由元素 $4$ 生成的集合。

任意元素的幂构成一个子群

设 $g$ 是 $G$ 中的任意元素。元素 $g$ 的幂集合构成一个子群。换句话说，

⟨ g ⟩ = {g^{i} : i \in ℤ},

是 $G$ 的一个子群。

证明。 见附录

4. 循环子群、循环群及其生成元

设 $g$ 为 $G$ 中的任意元素，则子群 $⟨ g ⟩ = {g^{i} : i \in ℤ}$ 被称为由 $g$ 生成的 $G$ 的循环子群。例如，考虑模 7 的非零整数乘法群 $G = {1, 2, 3, 4, 5, 6}$ 。由元素 $2$ 生成的循环子群为：

⟨ 2 ⟩ = {2^{0} = 1, 2^{1} = 2, 2^{2} = 4, 2^{3} = 1, 2^{4} = 2, 2^{5} = 4, 2^{6} = 1} = {1, 2, 4}

练习：找出由元素 $6$ 生成的子群。

循环群的定义

设 $g$ 是 $G$ 中的任意元素。如果 $G = ⟨ g ⟩$ ，则我们称 $G$ 是一个循环群，且 $g$ 是 $G$ 的一个生成元。换句话说，如果一个群包含至少一个能生成该群中所有元素的元素，那么这个群就是循环群。

循环群与生成元示例

考虑模 7 的非零整数乘法群 $G = {1, 2, 3, 4, 5, 6}$ 。如上所示，由于 $⟨ 3 ⟩ = G$ ，因此 $G$ 是一个循环群，且 $3$ 是 $G$ 的一个生成元。

注意 $⟨ 2 ⟩ = {1, 2, 4} \neq G$ ，这意味着元素 $2$ 不是 $G$ 的生成元，而是 $2$ 生成了 $G$ 的一个子群。

练习：判断 $5$ 是否为 $G$ 的生成元。

循环群的生成元不一定唯一

循环群至少有一个生成元，但生成元不必是唯一的。换句话说，一个循环群可以有多个生成元，其中任何一个都能生成整个群。对于循环子群也是如此。

正如你在上面的示例和练习中所见，元素 $3$ 和 $5$ 都是群 $G = {1, 2, 3, 4, 5, 6}$ 的生成元。

再举个例子，考虑模 5 的非零整数乘法群，即 ${1, 2,3, 4}$ 。元素 $2$ 和 $3$ 都能生成整个群。

\begin{matrix} 2^{0} = 1, 3^{0} = 1, \\ 2^{1} = 2, 3^{1} = 3, \\ 2^{2} = 4, 3^{2} = 4, \\ 2^{3} = 3, 3^{3} = 2. \end{matrix}

有限循环群基本定理

有限循环群基本定理提出了三个断言。设 $G$ 为一个有限循环群， $H$ 为 $G$ 的一个子群。

$H$ 必然是有限的且是循环的（意味着 $H$ 存在生成元）。
$H$ 的阶（其包含的元素数量）是 $G$ 的阶的因子。换言之， $H$ 的阶整除 $G$ 的阶。例如，假设 $G$ 的阶为 6，我们便可知阶为 5 的子群不可能存在，因为 5 不能整除 6。
如果 $G$ 的阶为 $q$ 且 $k$ 能整除 $q$ ，那么大小为 $k$ 的子群必然存在且唯一。事实上，我们可以直接找到它的生成元：如果 $g$ 是 $G$ 的生成元，则 $g^{\frac{q}{k}}$ 就是大小为 $k$ 的子群的生成元。这个大小为 $k$ 的子群等于 $⟨ g^{\frac{q}{k}} ⟩$ 。我们很快会展示相关的例子。

与拉格朗日定理的联系

有限循环群基本定理的断言 (2) 对任何有限群 $G$ 都成立，即使 $G$ 不是循环群。这一更普遍的结果被称为拉格朗日定理 (Lagrange’s Theorem)。

为简便起见，我们将简称为循环群基本定理，并默认我们讨论的是有限群。

使用循环群基本定理的示例

让我们使用模 7 的乘法群 $G = {1,2,3,4,5,6}$ 作为我们的循环群。前面我们已经证明了 $g = 3$ 能够生成整个群。

阶为 1 的子群

根据循环群基本定理，我们知道 $G$ 具有阶为 1 的子群，因为 1 能整除 6。现在让我们寻找该子群的生成元。由于 $k = 1$ ，我们有 $3^{\frac{6}{1}} \equiv 1 (\mod 7)$ 。单位元 $1$ 显然是大小为 1 的子群的生成元。

阶为 2 的子群

现在让我们找出大小为 2 的子群。我们知道它存在，因为 2 能整除 6。在这里，我们有 $g = 3$ 、 $q = 6$ 和 $k = 2$ 。代入公式得到 $g^{\frac{q}{k}} = 3^{\frac{6}{2}} = 3^{3} \equiv 6 (\mod 7)$ 。元素 $6$ 生成了阶为 2 的子群，其元素为 ${1, 6}$ 。

阶为 3 的子群

由于 3 能整除 6，因此存在一个阶为 3 的子群。此外，元素 $3^{\frac{q}{k}} = 3^{\frac{6}{3}} = 3^{2} \equiv 2 (\mod 7)$ 是该子群的生成元， $⟨ 2 ⟩ = {2^{0}, 2^{1}, 2^{2}} = {1, 2, 4}$ 。

阶为 4 和 5 的子群

不存在阶为 4 和 5 的子群，因为这些数字不能整除 6。

阶为 6 的子群

由于 6 能整除 6，因此存在一个阶为 6 的子群。此外， $3^{\frac{q}{k}} = 3^{\frac{6}{6}} = 3^{1} = 3$ 是该子群的生成元：

⟨ 3 ⟩ = {1, 2, 3, 4, 5, 6} = G .

练习：考虑模 11 的乘法群，其元素为 $G = {1,2,3,4,5,6,7,8,9,10}$ 。

找出该群的一个生成元。
该群有一个阶为 5 的子群，因为 5 能整除 $G$ 的阶（即 10）。找出该子群的一个生成元并计算其生成的子群。

有限域中阶为 $k$ 的乘法子群

我们可以在有限域中找到特定阶的乘法子群。首先，让我们看看有限域的定义：

根据定义，一个域 $(𝔽, +, *)$ 由两个阿贝尔群（二元运算满足交换律）组成：

加法群： $(𝔽, +)$ ，在有限域中是阿贝尔的且是有限的。
乘法群： $(𝔽^{*}, *)$ （其中 $𝔽^{*} = 𝔽 ∖ {0}$ ），在有限域中也是阿贝尔的且是有限的。

请注意， $𝔽_{q}$ 表示一个拥有 $q$ 个元素的域，而 $𝔽_{q}^{*}$ （ $𝔽_{q}$ 的乘法群）拥有 $q - 1$ 个元素。

在接下来的定理中，我们将会看到每个有限域必定包含一个阶为 $q - 1$ 的乘法子群（省略了 $0$ ）。

定理 1：乘法群 $𝔽_{q}^{*}$ 是阶为 $q - 1$ 的循环群。

如果 $𝔽_{q}$ 是阶为 $q$ 的有限域，那么其乘法群 $𝔽_{q}^{*}$ 是阶为 $q - 1$ 的循环群。

从有限域的定义可以直接得出 $𝔽_{q}^{*}$ 构成了一个阶为 $q - 1$ 的群。

由于证明乘法群的循环性将超出本文的范围，我们将以此作为已知事实。

循环群存在生成元，因此我们知道存在某个 $g \in 𝔽_{q}^{*}$ ，使得

𝔽_{q}^{*} = {1, g^{1}, g^{2}, \dots, g^{q - 2}} = ⟨ g ⟩ .

有限域中的本原元（生成元）

在域论中，有限域 $𝔽_{q}$ 的本原元（primitive element）就是该域乘法群的生成元。定理 1 中的元素 $g$ 即为 $𝔽_{q}$ 中的本原元。

下面的 Python 代码使用了 galois 库来识别 $𝔽_{7}$ 中的本原元（生成元）。

import galois

GF = galois.GF(7)

primitive_elements = GF.primitive_elements
print("Primitive elements:", primitive_elements)
# Primitive elements: [3 5]

# Alternatively, find a single primitive element
# suitable when there are a lot of primitive elements
primitive_element = GF.primitive_element
print("A primitive element:", primitive_element)
# A primitive element: 3

练习：使用 Python 找出域 $𝔽_{11}$ 的乘法群中的所有本原元。

推论 1：测试阶为 $k$ 的子群 — 通过有限域中的约数判断其存在性

一个有用的推论是，通过列出 $q - 1$ 的所有约数，我们就能快速检查特定大小的子群是否存在。例如，考虑域 $𝔽_{41}$ ，它有一个阶为 40 的乘法群 $𝔽_{41}^{*}$ 。我们可以快速确认 $𝔽_{41}^{*}$ 具有一个大小为 8 的子群，因为 8 能整除 40。

再举个例子，考虑域 $𝔽_{17}$ ，其乘法群 $𝔽_{17}^{*}$ 的阶为 16。因为 8 能整除 16，所以 $𝔽_{17}^{*}$ 具有大小为 8 的子群。类似地，它也具有大小为 4 的子群，因为 4 能整除 16，并且正如你可能猜到的那样， $𝔽_{17}$ 同样具有大小为 2 的子群。

要找到给定大小乘法子群的生成元，我们可以利用上述基本定理的断言 (3)。 $𝔽_{q}^{*}$ 的大小为 $q - 1$ ，因此，如果我们有一个本原元 $g$ 并且想要得到一个阶为 $k$ 的乘法子群，我们可以针对任意本原元 $g$ 计算 $g^{\frac{q - 1}{k}}$ 。

综合示例

考虑有限域 $𝔽_{17} = {0, 1, 2, \dots, 16}$ 。对于给定的 $k$ ，我们希望利用有限循环群基本定理在 $𝔽_{17}$ 中找出一个阶为 $k$ 的乘法子群。

由于乘法子群 $𝔽_{17}^{*}$ 的阶为 $q - 1 = 17 - 1 = 16$ ，根据循环群基本定理的断言 (2)，我们可知它存在阶为 1、2、4、8 和 16 的子群，其中最后一个就是该群本身。

这些子群都是循环的，因此每个子群至少有一个生成元。根据定理的断言 (3)，我们知道每个子群的生成元由 $g^{\frac{q - 1}{k}}$ 给出，其中 $g$ 是整个乘法群的生成元， $k$ 是我们所求子群的大小。

因此，为了生成这些子群，第一步是找出 $𝔽_{17}^{*}$ 的生成元，也就是 $𝔽_{17}$ 的本原元。

$𝔽_{17}^{*}$ 的生成元

回顾定理 1， $𝔽_{17}^{*}$ 是一个循环群。为了证明 $𝔽_{17}^{*}$ 可以由元素 $3$ 生成，我们可以按如下方式计算 $3$ 的所有幂：

\begin{matrix} 3^{0} = 1, \\ 3^{1} = 3, \\ 3^{2} = 9, \\ 3^{3} \equiv 9 * 3 \equiv 10, (27 - 17 = 10) \\ 3^{4} \equiv 10 * 3 \equiv 13, (30 - 17 = 13) \\ 3^{5} \equiv 13 * 3 \equiv 5, (39 - 2 * 17 = 5) \\ 3^{6} \equiv 5 * 3 \equiv 15, \\ 3^{7} \equiv 15 * 3 \equiv 11, (45 - 2 * 17 = 11) \\ 3^{8} \equiv 11 * 3 \equiv 16, (33 - 17 = 16) \\ 3^{9} \equiv 16 * 3 \equiv 14, (48 - 2 * 17 = 14) \\ 3^{10} \equiv 14 * 3 \equiv 8, (42 - 2 * 17 = 8) \\ 3^{11} \equiv 8 * 3 \equiv 7, (24 - 17 = 7) \\ 3^{12} \equiv 7 * 3 \equiv 4, (21 - 17 = 4) \\ 3^{13} \equiv 4 * 3 \equiv 12, \\ 3^{14} \equiv 12 * 3 \equiv 2, (36 - 2 * 17 = 2) \\ 3^{15} \equiv 2 * 3 \equiv 6, \\ 3^{16} = 6 * 3 \equiv 1, (18 - 17 = 1) . \end{matrix}

$3^{17}$ 又是多少呢？

3^{17} = 3^{16} * 3 \equiv 1 * 3 = 3.

你可以看到，对于所有的 $i \geq 17$ ，元素 $3^{i}$ 等同于 $3^{0}, 3^{1}, 3^{2}, \dots, 3^{16}$ 中的某一项。你还可以发现，{1,2,…,16} 中的每一个值都会在 3 的幂次列表中出现。那么， $⟨ 3 ⟩ = {1, 2, \dots, 16} = 𝔽_{17}^{*}$ 。

这个生成元可以通过 Python 代码中的 galois.primitive_elements 找到。

import galois

GF = galois.GF(17)

primitive_element = GF.primitive_element
print("A primitive element:", primitive_element)
# A primitive element: 3

在 $𝔽_{17}^{*}$ 中寻找阶为 $k$ 的子群

假设我们想确定在有限域 $𝔽_{q} = 𝔽_{17}$ 中是否存在一个阶为 $k = 4$ 的乘法子群。请注意， $𝔽_{q}$ 乘法群的大小为 $q - 1$ 。对于 $𝔽_{17}$ ，其乘法群 $𝔽_{17}^{*}$ 有 $q - 1 = 17 - 1 = 16$ 个元素。

回顾有限循环群基本定理，因为 $k$ 能整除 $q - 1$ （具体来说，4 能整除 16），那么 $g^{\frac{q - 1}{k}}$ 即为生成元，并且 $⟨ g^{\frac{q - 1}{k}} ⟩$ 是一个大小为 4 的子群。

g^{\frac{q - 1}{k}} = 3^{\frac{16}{4}} = 3^{4} \equiv 13 (\mod 17) .

因此，13 是 $𝔽_{17}^{*}$ 中大小为 4 的子群的生成元，并且

⟨ 13 ⟩ = {13^{0} = 1, 13^{1} = 13, 13^{2} \equiv 16, 13^{3} \equiv 4, 13^{4} \equiv 1, 13^{5} \equiv 13, \dots} .

明确地说，该子群为 ${1, 13, 16, 4}$ 。

练习： 计算阶为 $2$ 和 $8$ 的乘法子群。

总结

目标是在域 $𝔽_{q}$ 中找出大小为 $k$ 的乘法子群。
如果 $G = ⟨ g ⟩ = {g^{i} : i \in ℤ}$ ，则 $G$ 是一个循环群，且 $g$ 是 $G$ 的生成元。
如果 $𝔽_{q}$ 是阶为 $q$ 的有限域，则 $(𝔽_{q}^{*}, .)$ 是一个阶为 $q - 1$ 的循环群。
循环群基本定理指出，有限域 $𝔽_{q}$ 具有大小为 $k$ 的子群当且仅当 $k$ 能整除 $q - 1$ 。此外，该子群的生成元为 $g^{\frac{q - 1}{k}}$ ，其中 $g$ 是乘法群 $𝔽_{q}^{*}$ 的生成元。

附录

我们将验证 $⟨ g ⟩$ 成为 $G$ 的子群所需的三个条件。

单位元：因为 $1 = g^{0}$ ，所以 $1 \in ⟨ g ⟩$ 。

封闭性： 假设 $a, b \in ⟨ g ⟩$ 。那么对于某些 $n, m$ ，我们已知 $a = g^{n}$ 且 $b = g^{m}$ 。应用群运算可得：

a b = g^{n} g^{m} = g^{n + m} .

因为 $n + m \in ℤ$ ，所以 $a b \in ⟨ g ⟩$ 。

逆元： 假设 $a \in ⟨ g ⟩$ 。对于某个 $m$ ，那么有 $a = g^{m}$ ，

a^{- 1} = {(g^{m})}^{- 1} = g^{- m} .

因为 $- m \in ℤ$ ，所以 $a^{- 1} \in ⟨ g ⟩$ 。

练习

$𝔽_{31}$ 的乘法子群的所有可能的阶是什么？每个子群的生成元是什么？

$𝔽_{5}$ 的乘法子群的所有可能的阶是什么？每个子群的生成元是什么？

$𝔽_{51}$ 的乘法子群的所有可能的阶是什么？每个子群的生成元是什么？