17.循环群
文档摘要
title: 17. 循环群 tags: zk abstract algebra group theory cyclic group WTF zk 教程第 17 讲：循环群 这一讲，我们将介绍循环群，它是由一个元素生成的群结构，性质简单而重要，在密码学和数学中有广泛应用。 循环群 最简单的平凡群，也就是只包含单位元的群，比如 $(\set{0}, +)$，它只包含一个元素，并且满足群的 4 个基本性质。那么非平凡群中最简单的群是什么结构呢？假设群 $(G, )$ 除了单位元 $e$ 之外还包含一个元素 $a$，为了满足群的封闭性， $G$ 还要包含 $a$ 的逆元，以及和自身的运算。也就是说， $$ G = \set{...
title: 17. 循环群 tags: - zk - abstract algebra - group theory - cyclic group
WTF zk 教程第 17 讲：循环群
这一讲，我们将介绍循环群，它是由一个元素生成的群结构，性质简单而重要，在密码学和数学中有广泛应用。
1. 循环群
最简单的平凡群，也就是只包含单位元的群，比如 (\set{0}, +)，它只包含一个元素，并且满足群的 4 个基本性质。那么非平凡群中最简单的群是什么结构呢？假设群 (G, ) 除了单位元 e 之外还包含一个元素 a，为了满足群的封闭性， G 还要包含 a 的逆元，以及和自身的运算。也就是说，
这就是由 a 生成的群，也被称为循环群。
定义： 循环群是由一个单一元素生成的群。设 (G, ) 是一个群，若存在一个元素 g \in G，使得通过对 g 的不断群运算得到的所有元素构成的集合，即 G = \left \langle \, g \, \right \rangle = \{g^n \mid n \in \mathbb{Z}\}，则 (G, ) 形成一个循环群。其中 g 被称为生成元。
整数加法群 (\mathbb{Z}, +) 就是一个循环群，它的生成元是 1 或 -1，任何整数都可以由它们生成，比如 5 = 1^5 = 1 + 1 + 1 + 1 +1。
对于任意 m \in \mathbb{Z}， (m\mathbb{Z}, +) 也是循环群，因为 m\mathbb{Z} = (m^z | z \in \mathbb{Z}) = (mz | z \in \mathbb{Z}) = \left \langle \, m \, \right \rangle，它的生成元为 m。
整数模 6 加法群 (\mathbb{Z}_6, +) 也是循环群，生成元是 1。其中的元素 {0, 1,2,3,4,5} 都可以用 1 循环相加得到，比如 1^6 \equiv 1 + 1 + 1 + 1 + 1 + 1 \equiv 0 \pmod 6，而 1^7 \equiv 7 \equiv 1 \pmod 6，就陷入循环了。
整数模 5 乘法群 (\mathbb{Z}^*_5, \times) 也是循环群，生成元是 2 或 3。对于 2: 2^1 = 2, 2^2 = 4, 2^3 = 3, 2^4 = 1, 而 2^5 = 2，陷入循环。对于 3: 3^1 = 3, 3^2 = 4, 3^3 = 2, 3^4 = 1, 而 3^5 = 3，陷入循环。
1.1 循环群性质
下面介绍循环群的一些基本性质：
1. 循环群都是 Abel 群。
点我展开证明
群 (G, ) = \left \langle \, g \, \right \rangle 为循环群，对于任意 a,b \in G，设 a = g^x， b = g^y。那么有 a b = g^xg^y=g^{x+y}=g^{y+x} = g^yg^x = b a。因此群 (G, ) = \left \langle \, g \, \right \rangle 满足交换律，为 Abel 群。证毕。
2. 循环群的子群都是循环群。
点我展开证明
群 (G, ) = \left \langle \, g \, \right \rangle 为循环群， H 是群 G 的子群。设 d 是满足 g^d \in H 的最小正整数，那么任意其他元素 g^s \in H 有 s > d，根据欧几里得除法，有 s = qd + r 其中 0 \leq r < d。根据封闭性 g^r \in H，又因为 d 是 g^d \in H 的最小正整数，因此 r = 0。也就是说， d 整除 s， H 中任何元素都能由 g^d 生成，即 g^s = (g^d)^q。因此，子群 H 是循环群， g^d 是生成元。证毕。
3. 循环群的商群也是循环群
点我展开证明
群 (G, ) = \left \langle \, g \, \right \rangle 为循环群， H 是群 G 的子群。根据性质 1 和 2，群 G 和 H 为 Abel 群， H 为正规子，可以构建商群 G/H = \set{gH \mid g \in G}。对于群 G 中的元素 g^k，有陪集 g^kH = g^k H^k = (gH)^k，因此商群中的任意元素都可以表示为 (gH)^k，因此 G/H 为循环群，生成元为 gH。
下面我们看两个例子。首先，我们以整数模 6 加法群 \mathbb{Z}_6 和它的正规子群 2\mathbb{Z}_6 = \set{0, 2, 4} 为例。 \mathbb{Z}_6 是循环群，生成元是 1 和 5 （ 5^1 = 5, 5^2 = 5 +5 = 4, 5^3 = 3, 5^4 = 2, 5^5 = 1, 5^6 = 0）。正规子群 2\mathbb{Z}_6 也是循环群，生成元为 2 或 4，请自行验证。商群 \mathbb{Z}_6/2\mathbb{Z}_6 = \set{\set{0, 2, 4}, \set{1,3,5}} 也是循环群，它的生成元为 1 + 2\mathbb{Z}_6 = 5+ 2\mathbb{Z}_6 = \set{1,3,5}，因为 \set{1,3,5}^2 = 2\set{1,3,5} = \set{2,4,6}
接下来，我们以整数模 5 乘法群 `\mathbb{Z}^*_5` 和它的正规子群 `H=\set{1,4}` 为例。 `\mathbb{Z}^*_5` 是循环群，生成元是 2 或 3；正规子群 H=\set{1,4} 也是循环群，生成元为 4，因为 4^1 = 4 且 4^2 = 1；商群 \mathbb{Z}^*_5/H = \set{\set{1,4}, \set{2,3}} 也是循环群，它的生成元为 2H = 3H = \set{2,3}，因为 \set{2,3}^2 = \set{4, 1}。
1.2 循环群分类
循环群根据元素个数可以分为有限循环群和无限循环群。
有限循环群的元素个数为有限个，比如 \mathbb{Z}_6 和 \mathbb{Z}^*_5。
无限循环群的元素个数为无限个，比如 \mathbb{Z} 和 \mathbb{R}。
2. 元素的阶和群的阶
在群论中，"阶"是一个用来描述群中元素的性质的概念。在循环群中，元素的阶和群的阶有着特殊的关系。
2.1 阶的定义
元素 g 的阶是指，对于 g \in G，满足 g^n = e 的最小正整数 n，记为 \text{ord}(g) = n。如果不存在这样的 n，则称元素 g 为无限阶。元素的阶可以理解为元素到单位元的距离，即元素最少和自身运算多少次可以到达单位元。
群 G 的阶是指其元素个数，记为 \text{ord}(G) = |G|。
2.2 阶的性质
1. a^m = e，当且仅当 a 的阶 n 可以整除 m。
点我展开证明
充分性
根据欧几里得除法，有 m = qn+r，其中 0 \leq r < n，而 a^m = a^{qn+r} = a^{qn}a^r=(a^n)^qa^r = e a^r = a^r。又因为 0 \leq r < n 且 n 是使得 a^n = e 的最小正整数，因此 a^r = e 时 r = 0， n 可以整除 m。证毕。
必要性
若 n 可以整除 m，有 m = qn，因此 a^m = a^{qn} = (a^n)^q = e^q = e。证毕。
整数模 5 乘法群 (\mathbb{Z}^*_5, \times) 中， 2^4 \equiv 16 \equiv 1 \pmod{5}，而 2^8 \equiv 256 \equiv 1 \pmod{5}.
2. 循环群的阶等于生成元的阶： G 为有限循环群，群的阶 |G| = n 当且仅当它的生成元的阶 \text{ord}(g)=n。
点我展开证明
充分性
根据定义，循环群 G 由 g 生成。若 G 的阶为 n，群 G = \left \langle \, g \, \right \rangle = \set{e, g, ..., g^{n-1}} 包含 n 个不同的元素，因此元素 g 的阶为 n。
必要性
根据定义，循环群 G 由 g 生成。若 g 的阶为 n，群 G = \left \langle \, g \, \right \rangle = \set{e, g, ..., g^{n-1}} 包含 n 个不同的元素，因此群 G 的阶为 n。
整数模 5 乘法群 (\mathbb{Z}^*_5, \times) 中，生成元 2 或 3 的阶为 4，而群的阶也是 4。
3. 循环群的阶 |G| = n，正整数 d|n，那么 G 有唯一的 d 阶子群。
点我展开证明
首先我们证明 d 阶子群存在。因为循环群的阶 |G| = n，正整数 d|n，因此我们可以用 g^{n/d} 作为生成元，生成循环群 \left \langle \, g^{n/d} \, \right \rangle = \set{e, g^{n/d}, g^{2n/d},..., g^{n-n/d}}，它的阶为 d。因此存在 d 阶子群。
接下来我们证明 d 阶子群唯一。使用反证法，假设群 G 存在另一个 d 阶循环子群 \left \langle \, g^{k} \, \right \rangle，其中 k \in \mathbb{Z}。根据阶的定义，有 (g^{k})^d = g^{kd}= e。根据阶的性质一，有 n|kd，也就是 \frac{n}{d} |k。因此，根据 Abel 群性质， \left \langle \, g^{k} \, \right \rangle 是 \left \langle \, g^{n/d} \, \right \rangle 的子群。又因为它们的阶都是 d，因此它们是同样的循环群 \left \langle \, g^{n/d} \, \right \rangle。因此， d 阶子群唯一。
整数模 6 加法群 \mathbb{Z}_6 的阶为 6，因此它有 4 个子群，阶分别为 1, 2, 3, 6，它们分别是 \set{0}, \set{0,3}, \set{0,2,4}, \set{0,1,2,3,4,5}。
整数模 5 乘法群 \mathbb{Z}^*_5 的阶为 4，因此它有 3 个子群，阶分别为 1, 2, 4，它们分别是 \set{1}, \set{1, 4}, \set{1,2,3,4}。
4. n 阶循环群 \left \langle \, g \, \right \rangle 的元素 g^k 的阶为 \frac{n}{\gcd(n,k)}。
点我展开证明
假设元素 g^k 的阶为 m，根据阶的定义， m 为使得 g^{km} = e 的最小正整数。根据阶的性质一，有 n|km。也就是 km \equiv 0 \pmod{n}，可以简化为 m \equiv 0 \pmod{\frac{n}{\gcd(n,k)}}，满足此式的最小正整数 m = \frac{n}{\gcd(n,k)}。因此，元素 g^k 的阶为 \frac{n}{\gcd(n,k)}。证毕。
整数模 6 加法群 \mathbb{Z}_6 的阶为 6，其中元素 2 = 1 + 1 = 1^2 的阶为 3，元素 3 = 1 + 1 +1 = 1^3 的阶为 2，元素 4 = 1^4 的阶为 3，元素 5 = 1^5 的阶为 6。
整数模 5 乘法群 \mathbb{Z}^*_5 的阶为 4，其中元素 2 = 2^1 的阶为 4，元素 3 = 2^3 的阶为 4，元素 4 = 2^2 的阶为 2，元素 1 = 2^4 的阶为 1。
5. n 阶循环群有 \phi(n) 个生成元。
点我展开证明
根据上一个性质，仅有 \gcd(n, k) =1 时，元素 g^k 的阶为 n，为生成元。根据欧拉函数，小于 n 且与 n 互素的整数共有 \phi(n) 个。也就是说，有 \phi(n) 个 k 可以使得 g^k 为生成元。因此，n 阶循环群有 \phi(n) 个生成元。证毕。
整数模 6 加法群 \mathbb{Z}_6 的阶为 6，共有 \phi(6) = \phi(2) \cdot \phi(3) = 1 \cdot 2 = 2 个生成元，他们是 1 和 5。
整数模 5 乘法群 \mathbb{Z}^*_5 的阶为 4，共有 \phi(4) = \phi(2^2) = 2^2 - 2 = 2 个生成元，他们是 2 和 3。
6. n 阶有限群 G 中元素的阶是 n 的因子。
点我展开证明
设元素 a \in G，有 \left \langle \, g \, \right \rangle \subseteq G。根据拉格朗日定理，子群的阶整除元素的阶，因此 |\left \langle \, g \, \right \rangle| 整除 |G|。又因为 |G| = n 和 |a| = |\left \langle \, g \, \right \rangle|，因此元素的阶是 n 的因子。证毕
整数模 6 加法群 \mathbb{Z}_6 的阶为 6，元素 2 的阶为 3，是 6 的因子。
整数模 5 乘法群 \mathbb{Z}^*_5 的阶为 4，元素 4 的阶为 2，是 4 的因子。
7. 若 p 为素数，那么整数模 p 乘法群 Z^*_p 有 \phi(p-1) 个生成元。
点我展开证明
首先，我们先要确定 Z^* _p 的阶，它包含 \phi(p) 个元素，又因为 p 是质数， \phi(p) = p-1，因此 Z^* _p 的阶为 p-1。根据性质 5，它有 \phi(p-1) 个生成元。证毕
5 是质数，那么 Z^*_5 有 \phi(4) = \phi(2^2) = 2^2 - 2^1 = 2 个生成元，它们是 2 和 3。
3. 循环群的同构
这一节，我们介绍循环群的同构。循环群是最简单的一种群，可以通过同构被分为两类，一种同构于 \mathbb{Z}，另一种同构于 \mathbb{Z}_n。因此，当我们研究循环群的性质时，可以转而研究更简单的 \mathbb{Z} 或 \mathbb{Z}_n。
1. 任意无限循环群都同构于整数加法群 \mathbb{Z}。
点我展开证明
设无限循环群 G = \left \langle \, g \, \right \rangle。设映射 f: \mathbb{Z} \to G 有以下形式 f(x) = g^x。
群同态： 对于任意 a, b \in \mathbb{Z}，有 f(a +b) = g^{a+b} = g^ag^b = f(a)f(b)。因此 f 是群同态。
满同态： 同态像 \set{f(a) | a \in Z} = \set{g^a | a \in Z} = \left \langle \, g \, \right \rangle，因此同态像等于群 G， f 为满同态。
单同态： 无限循环群为无限阶，因此仅有 g^0 = e_G，因此同态核 \text{ker}(f)=0，根据单同态的充要条件， f 为单同态。
群同态 f 既是满同态又是单同态，因此无限循环群 G 和整数加法群 \mathbb{Z} 同构。证毕。
2. 任意 n 阶有限循环群都同构于整数模 n 加法群 \mathbb{Z}_n。
点我展开证明
设 n 阶有限循环群 G = \left \langle \, g \, \right \rangle = \set{g^a | a \in Z_n}。设映射 f: Z_n \to G 有以下形式 f(x) = g^x。
群同态： 对于任意 a, b \in \mathbb{Z}，有 f(a +b) = g^{a+b} = g^ag^b = f(a)f(b)。因此 f 是群同态。
满同态： 同态像 \set{f(a) | a \in Z_n} = \set{g^a | a \in Z_n} = \left \langle \, g \, \right \rangle，因此同态像等于群 G， f 为满同态。
单同态： 群 G 生成元 g 的阶为 n，因此有 g^{kn} = e_G，其中 k 为整数。因此同态核 \text{ker}(f)= \set{kn \mod n| k \in Z}=\set{0}，也就是 Z_n 的单位元。根据单同态的充要条件， f 为单同态。
群同态 f 既是满同态又是单同态，因此任意 n 阶有限循环群 G 和整数模 n 加法群 Z_n 同构。证毕。
因此，对于任意循环群 G，它要么跟整数模 n 群 Z_n 同构，要么跟整数群 Z 同构。同构代表两个群结构相同，也就是说，我们之前介绍的 Z_n 或 Z 的性质可以转移到任意循环群中。
4. 重温欧拉定理
在数论基础中，我们介绍了欧拉定理，将欧拉函数和整数模 n 乘法群的循环性质联系起来。
欧拉定理： 如果整数 a 和正整数 n 互质（即 \gcd(a,n)=1），那么 a^{\phi(n)} \equiv 1 \pmod{n}。
现在我们利用循环群的性质证明它。
首先考虑整数模 n 乘法群 Z^* _n，它的阶是 \phi(n)。设整数 a 与 n 互质，即 \gcd(a,n)= 1，有 a \equiv 1 \mod n， 因此 a \in Z^* _n。我们可以以 a 为生成元构建循环群 A，则 A 为 Z^* _n 的子群。设群 A 的阶为 k，有 a^k \equiv 1 \pmod n。根据拉格朗日定理，有子群 A 的阶整除 Z^* _n 的阶，即 k | \phi(n)。也就是说有整数 q 使得 \phi(n) = kq。我们得到：
也就是 a^{\phi(n)} \equiv 1 \pmod n，证毕。
5. 总结
这一讲，我们介绍了循环群，它的结构简单，可以由一个元素（生成元）生成。所有循环群都是 Abel 群，循环群的子群和商群均是循环群。循环群的阶和元素的阶有着特殊的关系，性质比较多，大家多看几遍，慢慢熟悉。任意无限循环群都与 Z 同构，任意有限循环群都与 Z_n 同构。