引言

本章将继续探讨群论，重点研究子群（subgroups）和生成元（generators）。最后将介绍本原元（primitive element）的概念。我们假设你已经熟悉群的定义。如果需要复习，请查看this article。

为了建立直观理解，我们从加法群（additive groups）开始，它们非常简单明了，有助于阐明子群和生成元等核心概念。

然后我们将转向模 $n$ 整数乘法群。整数本身在乘法下并不构成群——在 $\mathbb{Z}$ 中只有 $1$ 和 $-1$ 有乘法逆元，因此不满足群公理。为了解决这个问题，我们考虑模 $n$ 的乘法，重点研究小于 $n$ 且与 $n$ 互质（coprime）的整数。这些互质的整数在模 $n$ 下确实具有乘法逆元，它们共同构成了一个良定义的群。这种构造在数论中起着核心作用，也是许多密码学系统的基础。

互质（Coprime）： 如果两个数的最大公约数（GCD）为 1，则这两个数互质。

示例 1： 8 和 15 是互质的，因为
8 的因数：1, 2, 4, 8
15 的因数：1, 3, 5, 15
公因数：1
最大公约数是 1。

示例 2： 12 和 18 不互质，因为
12 的因数：1, 2, 3, 4, 6, 12
18 的因数：1, 2, 3, 6, 9, 18
公因数：1, 2, 3, 6
最大公约数是 6。

最后，我们来研究生成元（generators）——即能够通过重复乘法运算生成整个群或子群的元素。了解生成元可以揭示重要的子群结构，特别是当 $n$ 为素数时，并突显它们在密码学应用中的关键作用。

1. 加法群

加法群使用加法（通常是模某个数的加法）作为运算，单位元为 $0$，元素 $a$ 的逆元为 $-a$，这使得它们的结构相对直观。让我们通过例子来看看它们是如何运作的。

1.1 示例：$(\mathbb{Z}_6, +)$

作为热身，考虑在加法下的 $\mathbb{Z}_6 = \{0, 1, 2, 3, 4, 5\}$。从封闭性（closure）开始：

所有结果都在 $\{0, 1, 2, 3, 4, 5\}$ 内，因此封闭性成立。检查其他性质：

• 结合律（Associativity）： 分组不改变结果：
  • $(2 + 3) + 4 = 5 + 4 = 9 \equiv 3 \pmod{6}$，
  • $2 + (3 + 4) = 2 + (7 \equiv 1) = 3$。
• 单位元（Identity）: $0$ 作为单位元，因为 $3 + 0 = 3$（参见表格的第一行或第一列）。
• 逆元（Inverses）: 每个元素都有一个配对元素，相加之和等于 $0 \pmod{6}$：

因此，$(\mathbb{Z}_6, +)$ 是一个群，其阶（order，即集合中元素的数量）为 $|\mathbb{Z}_6| = 6$。

练习 1.1：检查 $(\mathbb{Z}_{9}, +)$ 是否为一个群。

提示： 尝试像我们对 $\mathbb{Z}_6$ 所做的那样构建加法表。

手动执行此操作可能有些繁琐，因此这里有一个 Python 脚本，它可以为任何 $\mathbb{Z}_n$ 生成完整的加法表：

Copy

def print_addition_table(mod):
    header = ["+ mod " + str(mod)] + list(range(mod))
    print(" | ".join(str(h).rjust(4) for h in header))
    print("-" * (6 * (mod + 1)))
    for row in range(mod):
        line = [str(row).rjust(4)]
        for col in range(mod):
            value = row + col
            result = value % mod
            if value >= mod:
                line.append(f"{value} ≡ {result}".rjust(6))
            else:
                line.append(str(result).rjust(6))
        print(" | ".join(line))


# Try it with Z_9
print_addition_table(9)

后续： 在分析了 $\mathbb{Z}_9$ 之后，尝试生成 $\mathbb{Z}_{10}$ 的表格。你能确定 $(\mathbb{Z}_{10}, +)$ 是否也是一个群吗？

因此，$(\mathbb{Z}_n, +)$ 是一个阶为 $n$ 的群。这类有限群在模算术和密码学中至关重要。接下来，我们将注意力转向群内的特定元素和子集如何揭示更深层次的结构——通过子群和生成元。

2. 子群与生成元

2.1 理解子群

在研究群时，我们经常会遇到一些子集，它们在相同运算下保留了群的结构。这些特殊的子集被称为子群（subgroups），它们就像是父群的微缩版本。不过，并非所有子集都符合条件——让我们通过例子来探讨什么才能构成子群。

示例 2.1.1：$(\mathbb{Z}, +)$ 中的子群

考虑所有整数在加法下构成的群 $(\mathbb{Z}, +)$，以及两个熟悉的子集：

• 偶数集合：$\{\ldots, -4, -2, 0, 2, 4, \ldots\}$
• 奇数集合：$\{\ldots, -3, -1, 1, 3, 5, \ldots\}$

让我们检查偶数集合：

• 封闭性：两个偶数之和也是偶数（例如，$-2 +4= 2$）。
• 单位元：$0$ 是偶数且包含在集合中。
• 逆元：任何偶数的逆元也是偶数（例如，$2$ 的逆元是 $-2$）。
• 结合律：继承自 $\mathbb{Z}$。

偶数集合满足所有群性质——这是一个有效的子群。

接下来检查奇数集合：

• 封闭性：$1 + 3= 4$，它是偶数——不在集合中。因此封闭性不成立。
• 单位元：$0$ 不是奇数，所以缺少单位元。
• 逆元：对于 $1$，$-1$ 是奇数——但由于封闭性和单位元已经不成立，它不是一个子群。

奇数在加法下不满足子群条件——它们只是一个子集，而不是一个子群。

示例 2.1.2：$(\mathbb{Z}_8, +)$ 中的子群

现在选取 $(\mathbb{Z}_8, +) = \{0, 1, 2, 3, 4, 5, 6, 7\}$ 并测试两个子集：

• 模 8 偶数：$\{0, 2, 4, 6\}$
• 前半部分：$\{0, 1, 2, 3\}$

对于 $\{0, 2, 4, 6\}$：

• 封闭性：$2 +4= 6$，$4 +6= 10 \equiv2\pmod{8}$（都在集合中）。
• 单位元：存在 $0$。
• 逆元：$2 +6= 8 \equiv 0$，$4 +4= 8 \equiv 0$，$0 + 0 = 0$（所有配对均成立）。
• 结合律：继承自 $\mathbb{Z}_8$。

这是一个子群！

对于 $\{0, 1, 2, 3\}$：

• 封闭性：$2+3= 5$（不在集合中）。
• 单位元：存在 $0$。
• 逆元：对于 $1$，${0, 1, 2, 3}$ 中没有元素能使其相加得到 $0$（例如，$1 +3=4\pmod{8}$）。

它无法构成群，所以只是一个子集，而不是子群。

定义：群 $G$ 的子集 $H$ 如果在同一运算下也是一个群，即满足封闭性、包含单位元、其所有元素都有逆元，并且继承了 $G$ 的结合律，则称 $H$ 为 $G$ 的子群（subgroup）。

练习 2.1.1： 找出 $(\mathbb{Z}_{5}, +)$ 的所有子群。

2.2 加法群中的生成元

既然我们已经了解了子群，接下来探讨单个元素是如何生成它们——甚至生成整个群的。我们将回顾 $(\mathbb{Z}_6, +) = \{0, 1, 2, 3, 4, 5\}$，即模 6 加法的加法群，并观察当我们不断将一个元素与自身相加时会发生什么，就像在模 6 的数字上“漫步”一样。

示例 2.2.1：$(\mathbb{Z}_6, +)$ 中的生成元

尝试 1：

• $1$
• $1 + 1 = 2$
• $2 + 1 = 3$
• $3 + 1 = 4$
• $4 + 1 = 5$
• $5 + 1 = 6 \equiv 0 \pmod{6}$

这得到了 $\{0, 1, 2, 3, 4, 5\} = \mathbb{Z}_6$。不断地加上 $1$ 循环遍历了整个群。

尝试 2：

• $2$
• $2 + 2 = 4$
• $4 + 2 = 6 \equiv 0 \pmod{6}$
• $0 + 2 = 2$

这得到了 $\{0, 2, 4\}$——只有群的一半。

尝试 3：

• $3$
• $3 + 3 = 6 \equiv 0 \pmod{6}$
• $0 + 3 = 3$

这得到了 $\{0, 3\}$，范围更小了！

尝试 5：

• $5$
• $5 + 5 = 10 \equiv 4 \pmod{6}$
• $4 + 5 = 9 \equiv 3 \pmod{6}$
• $3 + 5 = 8 \equiv 2 \pmod{6}$
• $2 + 5 = 7 \equiv 1 \pmod{6}$
• $1 + 5 = 6 \equiv 0 \pmod{6}$

这得到了 $\{0, 1, 2, 3, 4, 5\} = \mathbb{Z}_6$，覆盖了所有元素，就像 $1$ 一样。

练习 2.2.1：在 $(\mathbb{Z}_9, +)$ 中，哪些元素生成整个 $\mathbb{Z}_9$？哪些元素生成真子群？

2.2.2 由元素生成的子群

现在考虑任意带有二元运算（如加法或乘法）的群 $G$，设 $g$ 是 $G$ 中的一个元素。通过重复对 $g$ 应用群运算，我们可以构成由它生成的元素集合。这个集合记为 $\langle g \rangle$，被称为由 $g$ 生成的循环子群（cyclic subgroup generated by $g$）。

例如在加法群中：

对于许多元素来说，$\langle g \rangle$ 是一个真子群（proper subgroup）。但是当 $\langle g \rangle = G$ 时，我们称 $g$ 是 $G$ 的一个生成元（generator），并且称 $G$ 是一个循环群（cyclic group）。
如示例 2.2.1 所示，我们计算了在模 6 加法下 $(\mathbb{Z}_6, +) = \{0, 1, 2, 3, 4, 5\}$ 中各个元素生成的子群。每个元素生成的子群如下：

• $\langle 0 \rangle = \{0\}$（真子群）
• $\langle 1 \rangle = \{0, 1, 2, 3, 4, 5\} = \mathbb{Z}_6$
• $\langle 2 \rangle = \{0, 2, 4\}$（真子群）
• $\langle 3 \rangle = \{0, 3\}$（真子群）
• $\langle 4 \rangle = \{0, 4, 2\}$（真子群）
• $\langle 5 \rangle = \{0, 1, 2, 3, 4, 5\} = \mathbb{Z}_6$

元素 $1$ 和 $5$ 生成整个群 $\mathbb{Z}_6$，使它们成为生成元，而 $0$、$2$、$3$ 和 $4$ 则生成真子群。

示例 2.2.3：$(\mathbb{Z}_5, +)$ 中的生成元

现在测试在模 5 加法下的 $\mathbb{Z}_5 = \{0, 1, 2, 3, 4\}$：

• $\langle1\rangle = \{0, 1, 2, 3, 4\}=\mathbb{Z}_5$
• $\langle2\rangle =\{2, 4, 6 \equiv 1 \pmod 5 , 8 \equiv 3 \pmod 5\} =\{1,2,3,4\}=\mathbb{Z}_5$
• $\langle3\rangle= \{3, 6 \equiv 1 \pmod 5, 9 \equiv 4\pmod 5 , 7 \equiv 2\pmod 5 \}=\{1,2,3,4\}=\mathbb{Z}_5$
• $\langle4\rangle =\{4, 8 \equiv 3 \pmod 5, 12 \equiv 2\pmod 5 , 16 \equiv 1\pmod 5 \}=\{1,2,3,4\}=\mathbb{Z}_5$

每个非零元素都是生成元。

这是因为对于所有 $g \neq 0$，$\gcd(g, 5) = 1$，且 $5$ 是素数。

结论：在 $(\mathbb{Z}_n, +)$ 中，一个元素 $g$ 生成整个群当且仅当 $\gcd(g, n) = 1$。对于素数 $n$，所有非零元素都是生成元。对于合数 $n$，只有部分元素符合条件。

2.3 代码：探索 $(\mathbb{Z}_n, +)$ 中的加法生成元

Copy
def additive_closure(a, n):
    """Generates {0, a, 2a, 3a, ...} mod n until it repeats."""
    result = []
    current = 0
    while current not in result:
        result.append(current)
        current = (current + a) % n
    return sorted(result)  # Sorted for readability

# Show generated sets in (Z_6 , +)
print("Z_6:")
for a in range(6):
    print(f"Generated by {a}: {additive_closure(a, 6)}")

# Show generated sets in (Z_5, +)
print("\nZ_5:")
for a in range(5):
    print(f"Generated by {a}: {additive_closure(a, 5)}")

输出：

Copy
(Z_6, +):
Generated by 0: [0]
Generated by 1: [0, 1, 2, 3, 4, 5]
Generated by 2: [0, 2, 4]
Generated by 3: [0, 3]
Generated by 4: [0, 2, 4]
Generated by 5: [0, 1, 2, 3, 4, 5]

(Z_5, +):
Generated by 0: [0]
Generated by 1: [0, 1, 2, 3, 4]
Generated by 2: [0, 1, 2, 3, 4]
Generated by 3: [0, 1, 2, 3, 4]
Generated by 4: [0, 1, 2, 3, 4]

在探讨了加法群之后，我们现在转向它们对应的乘法群。

3. 乘法群

乘法群在乘法（通常是模某个数的乘法）下运算，单位元为 $1$，不过寻找逆元可能会更加微妙，尤其是在有限集合中。为了说明这一点，我们将使用模 7 乘法作为一个具体例子来探讨。

3.1 示例：

考虑 $\mathbb{Z}_7 = \{0, 1, 2, 3, 4, 5, 6\}$：

• 封闭性成立，例如，$2 \times5= 10 \equiv 3$，在集合中。
• 单位元：单位元是 $1$，但这对于 $0$ 不成立，$0$ 没有逆元；
• 逆元：每个非零元素都有一个逆元：
  • $1 \times1= 1$
  • $2 \times4= 8 \equiv1\pmod{7}$
  • $3 \times5= 15 \equiv1\pmod{7}$
  • $4 \times2= 8 \equiv1\pmod{7}$
  • $5 \times3= 15 \equiv1\pmod{7}$
  • $6 \times6= 36 \equiv1\pmod{7}$

由于 $0$ 没有逆元，$(\mathbb{Z}_7, \times)$ 不是一个群。但如果我们去掉 $0$，只考虑非零元素——即 $\mathbb{Z}_7 \setminus \{0\} = \{1, 2, 3, 4, 5, 6\}$——我们就确实得到了一个在乘法下的群。这个集合通常记为 $\mathbb{Z}_7^*$，是一个阶为 6 的群。

你可以使用以下代码生成任何模数 $n$ 的乘法表：

Copy
def print_multiplication_table(mod):
    header = ["× mod " + str(mod)] + list(range(mod))
    print(" | ".join(str(h).rjust(4) for h in header))
    print("-" * (6 * (mod + 1)))

    for row in range(mod):
        line = [str(row).rjust(4)]
        for col in range(mod):
            value = row * col
            result = value % mod
            if value >= mod:
                line.append(f"{value} ≡ {result}".rjust(6))
            else:
                line.append(str(result).rjust(6))
        print(" | ".join(line))

print_multiplication_table(5)

3.2 示例：$(\mathbb{Z}_6\setminus \{0\}, \times)$ 不是一个群

现在让我们测试集合 $\{1, 2, 3, 4, 5\}$ 在模 6 乘法下的情况。

现在我们遇到了一个更根本的问题：一些乘法运算结果为 0，而 0 并不属于该集合。因此，这个集合与二元运算符不满足封闭性，所以它不是一个群。

3.3 示例：$(\mathbb{Z}_8\setminus\{0\}, \times)$

作为另一个例子，现在我们考虑 $\mathbb{Z}_8\setminus\{0\} = \{1, 2, 3, 4, 5, 6, 7\}$ 中的乘法：

只有元素 $\{1, 3, 5, 7\}$——那些与 8 互质的元素——具有模 8 的乘法逆元：

• $1 \times1= 1 \pmod 8$
• $3 \times3= 9 \equiv 1 \pmod 8$
• $5 \times5= 25 \equiv 1 \pmod 8$
• $7 \times7= 49 \equiv 1 \pmod 8$

剩下的元素 $\{2, 4, 6\}$ 都与 8 有公因数，因此没有逆元。所以，$\mathbb{Z}_8 \setminus \{0\}$ 在乘法下不是一个群。

3.4. 什么是 $\mathbb{Z}_n^*$？

集合 $\mathbb{Z}_n^*$ 正式定义为：

也就是说，$\mathbb{Z}_n^*$ 由 $\mathbb{Z}_n$ 中所有具有模 $n$ 乘法逆元的元素组成。

• 当 $n$ 为素数时，每个非零元素都是可逆的，因此：
  

  $$\mathbb{Z}_n^* = \mathbb{Z}_n \setminus \{0\}$$

• 当 $n$ 为合数时，只有与 $n$ 互质的元素是可逆的。例如：

  • $\mathbb{Z}_6^* = \{1, 5\}$
  • $\mathbb{Z}_8^* = \{1, 3, 5, 7\}$

在这两种情况下，$\mathbb{Z}_n^*$ 都在乘法下构成一个群。然而，完整集合 $\mathbb{Z}_n \setminus \{0\}$ 并不总是能构成群——除非 $n$ 是素数。

前面我们用 $\mathbb{Z}_n \setminus \{0\}$ 来论证当 $n$ 为合数时，逆元的缺失（以及零因子的存在）会破坏群结构。这种区别不仅仅是技术上的：它在理解模算术、密码学算法和数论中起着核心作用。

在下一节中，我们将探讨当 $n$ 为素数时，$\mathbb{Z}_n^*$ 的结构会如何变化。

3.5 为什么素数模数可行

这些失效情况促使我们使用素数模数（prime moduli）。在 $\{1,2,\ldots, p-1\}$（其中 $p$ 为素数）中，每个元素都有逆元。事实上，这由数论中的一个经典结果所保证。

考虑模 $n$ 下 $\{1, 2, \ldots, n-1\}$ 的规律：

• 如果 $n$ 不是素数，由于零因子和缺失逆元，它不是一个群（例如，$n = 6, 8$）。
• 如果 $n$ 是素数，它就是一个群。

3.6 计算逆元的 Python 代码

最简单、最高效的方法之一是使用 Python 内置的
pow(a, -1, p) 来计算模逆元。在底层，这之所以有效是因为一个名为费马小定理（Fermat’s Little Theorem）的著名数论结果，它保证了逆元的存在并告诉我们：

当模数 $p$ 为素数且 $a$ 不被 $p$ 整除时。

以下是一个示例：

Copy
def mod_inverse(a, p):  
    return pow(a, -1, p)

# Test for Z_7^*
def test_inverses(p):
    print(f"Testing inverses modulo {p}:")
    for a in range(1, p):
        inv = mod_inverse(a, p)
        print(f"Inverse of {a} mod {p} is {inv} (check: {a} * {inv} = {a * inv % p})")

if __name__ == "__main__":
    p = 7
    test_inverses(p)

输出：

Copy
Testing inverses modulo 7:
Inverse of 1 mod 7 is 1 (check: 1 * 1 = 1)
Inverse of 2 mod 7 is 4 (check: 2 * 4 = 1)
Inverse of 3 mod 7 is 5 (check: 3 * 5 = 1)
Inverse of 4 mod 7 is 2 (check: 4 * 2 = 1)
Inverse of 5 mod 7 is 3 (check: 5 * 3 = 1)
Inverse of 6 mod 7 is 6 (check: 6 * 6 = 1)

3.7 练习

数学练习：

1. 使用 Python 的 pow(a, -1, n) 函数或计算器，找出下列的模逆元（如果存在的话）。对于素数模数，你可以选择使用费马小定理：

   • $3^{-1} \mod 11$
   • $7^{-1} \mod 26$
   • $4^{-1} \mod 15$

2. 在 $\mathbb{Z}_{12}^*$ 中，$a$ 取哪些值时存在模逆元？

编程练习：

1. 编写一个函数 list_all_inverses(n)，返回一个包含 $\mathbb{Z}_n^*$ 中所有元素及其逆元（如果存在）的字典。

2. 编写一个程序，接收用户输入的 a 和 n，并检查模逆元是否存在。如果存在，打印该逆元。用不同的值进行尝试，看看你会有什么发现。

3. 挑战： 挑选几个较小的素数 p，编写一个程序检查对于 {1, 2, ..., p - 1} 中的所有 a，是否都满足
   pow(a, p - 1, p) == 1。
   这对于每个 a 都成立吗？如果 p 不是素数会发生什么？

4. 乘法群中的生成元

我们现在将注意力转向乘法群中的生成元。为了建立直观理解，我们从 $\mathbb{Z}_7^* = \{1, 2, 3, 4, 5, 6\}$ 中的具体示例开始，探索单个元素如何通过重复乘法生成整个群——或仅仅是群的一部分。

示例 4.1：$(\mathbb{Z}_7^*, \times)$

尝试 3：

• $3^1 = 3$
• $3^2 = 9 \equiv 2 \pmod{7}$
• $3^3 = 27 \equiv 6 \pmod{7}$
• $3^4 = 81 \equiv 4 \pmod{7}$
• $3^5 = 243 \equiv 5 \pmod{7}$
• $3^6 = 729 \equiv 1 \pmod{7}$

$\langle 3 \rangle = \{1, 2, 3, 4, 5, 6\} = \mathbb{Z}_7^*$。元素 $3$ 是一个生成元。

尝试 2：

• $2^1 = 2$
• $2^2 = 4$
• $2^3 = 8 \equiv 1 \pmod{7}$

$\langle 2 \rangle = \{1, 2, 4\}$，是一个子群，而不是整个群。

尝试其他元素：

• $4$：$4, 16 \equiv 2, 8 \equiv 1$ $\Rightarrow \{1, 2, 4\}$
• $5$：$5, 25 \equiv 4, 20 \equiv 6, 30 \equiv 2, 10 \equiv 3, 15 \equiv 1$ $\Rightarrow \mathbb{Z}_7^*$
• $6$：$6, 36 \equiv 1$ $\Rightarrow \{1, 6\}$

总结：

4.1 本原元

正如我们所见，在加法群 $(\mathbb{Z}_p, +)$ 中，当 $p$ 为素数时，保证每个非零元素都是生成元。也就是说，重复地将任何非零元素与自身相加，最终将循环遍历群中的所有元素。然而，在乘法群 $(\mathbb{Z}_p^*, \times)$ 中，只有部分元素是生成元——这些被称为本原元（primitive elements）。这种对比突出了一种根本的区别：基于素数的加法群始终是循环的，且所有非零元素均为生成元；而基于素数的乘法群也是循环的，但只有部分元素能作为生成元。

定义：如果在 $\mathbb{Z}_p^*$ 中的一个元素 $g$ 满足

$$\langle g \rangle = \{g^1, g^2, \ldots, g^{p-1}\} \pmod{p} = \mathbb{Z}_p^*.$$

则称其为本原元（primitive element）。

以 $\mathbb{Z}_7^*$ 为例：$3$ 和 $5$ 是本原元，而 $2$、$4$ 和 $6$ 不是。

数论中的一个基本结论保证了对于任何素数 $p$，群 $\mathbb{Z}_p^*$ 都是循环群（cyclic），这意味着它始终至少包含一个本原元。这与加法群 $(\mathbb{Z}_p, +)$ 形成鲜明对比，在加法群中，每个非零元素都能生成整个群。

示例 4.1.1：$\mathbb{Z}_5^* = \{1, 2, 3, 4\}$

• 元素 2：
  

  $$\begin{align*} 2^1 &= 2 \pmod{5}, \\ 2^2 &= 4 \pmod{5}, \\ 2^3 &= 8 \equiv 3 \pmod{5}, \\ 2^4 &= 16 \equiv 1 \pmod{5} \end{align*}$$
  
  $\langle 2 \rangle = \{1, 2, 3, 4\} = \mathbb{Z}_5^*$，因此 $2$ 是一个本原元。

• 元素 3：
  

  $$\begin{align*} 3^1 &= 3 \pmod{5}, \\ 3^2 &= 9 \equiv 4 \pmod{5}, \\ 3^3 &= 27 \equiv 2 \pmod{5}, \\ 3^4 &= 81 \equiv 1 \pmod{5} \end{align*}$$
  
  $\langle 3 \rangle = \{1, 2, 3, 4\} = \mathbb{Z}_5^*$，因此 $3$ 也是一个本原元。

示例 4.1.2：$\mathbb{Z}_{11}^* = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$

• 元素 2：
  

  $$\begin{align*} 2^1 &= 2 \pmod{11}, \\ 2^2 &= 4 \pmod{11}, \\ 2^3 &= 8 \pmod{11}, \\ 2^4 &= 16 \equiv 5 \pmod{11}, \\ 2^5 &= 10 \pmod{11}, \\ 2^6 &= 20 \equiv 9 \pmod{11}, \\ 2^7 &= 18 \equiv 7 \pmod{11}, \\ 2^8 &= 14 \equiv 3 \pmod{11}, \\ 2^9 &= 6 \pmod{11}, \\ 2^{10} &= 12 \equiv 1 \pmod{11} \end{align*}$$
  
  $\langle 2 \rangle = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\} = \mathbb{Z}_{11}^*$，因此 $2$ 是一个本原元。

• 元素 3：
  

  $$\begin{align*} 3^1 &= 3 \pmod{11}, \\ 3^2 &= 9 \pmod{11}, \\ 3^3 &= 27 \equiv 5 \pmod{11}, \\ 3^4 &= 15 \equiv 4 \pmod{11}, \\ 3^5 &= 12 \equiv 1 \pmod{11} \end{align*}$$
  
  $\langle 3 \rangle = \{1, 3, 4, 5, 9\}$，是一个子群，不是整个群。

示例 4.1.3：$\mathbb{Z}_{17}^*$