| title |
tags |
17. 循环群 |
zk |
abstract algebra |
group theory |
cyclic group |
|
这一讲，我们将介绍循环群，它是由一个元素生成的群结构，性质简单而重要，在密码学和数学中有广泛应用。
最简单的平凡群，也就是只包含单位元的群，比如 $(\set{0}, +)$，它只包含一个元素，并且满足群的 4 个基本性质。那么非平凡群中最简单的群是什么结构呢？假设群 $(G, 🐔)$ 除了单位元 $e$ 之外还包含一个元素 $a$，为了满足群的封闭性， $G$ 还要包含 $a$ 的逆元，以及和自身的运算。也就是说，
$$
G = \set{..., a^{-3}, a^{-2}, a^{-1}, e, a, a^2, a^3, ...}
$$
这就是由 $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. 循环群都是 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}$。
循环群根据元素个数可以分为有限循环群和无限循环群。
有限循环群的元素个数为有限个，比如 $\mathbb{Z}_6$ 和 $\mathbb{Z}^*_5$。
无限循环群的元素个数为无限个，比如 $\mathbb{Z}$ 和 $\mathbb{R}$。
在群论中，"阶"是一个用来描述群中元素的性质的概念。在循环群中，元素的阶和群的阶有着特殊的关系。
元素 $g$ 的阶是指，对于 $g \in G$，满足 $g^n = e$ 的最小正整数 $n$，记为 $\text{ord}(g) = n$。如果不存在这样的 $n$，则称元素 $g$ 为无限阶。元素的阶可以理解为元素到单位元的距离，即元素最少和自身运算多少次可以到达单位元。
群 $G$ 的阶是指其元素个数，记为 $\text{ord}(G) = |G|$。
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$。
这一节，我们介绍循环群的同构。循环群是最简单的一种群，可以通过同构被分为两类，一种同构于 $\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$ 的性质可以转移到任意循环群中。
在数论基础中，我们介绍了欧拉定理，将欧拉函数和整数模 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)} = a^{kq} = (a^k)^q = 1^q = 1 \pmod n
$$
也就是 $a^{\phi(n)} \equiv 1 \pmod n$，证毕。
这一讲，我们介绍了循环群，它的结构简单，可以由一个元素（生成元）生成。所有循环群都是 Abel 群，循环群的子群和商群均是循环群。循环群的阶和元素的阶有着特殊的关系，性质比较多，大家多看几遍，慢慢熟悉。任意无限循环群都与 $Z$ 同构，任意有限循环群都与 $Z_n$ 同构。
