Skip to content

Latest commit

 

History

History
236 lines (124 loc) · 14.7 KB

readme.md

File metadata and controls

236 lines (124 loc) · 14.7 KB
title tags
17. 循环群
zk
abstract algebra
group theory
cyclic group

WTF zk 教程第 17 讲:循环群

这一讲,我们将介绍循环群,它是由一个元素生成的群结构,性质简单而重要,在密码学和数学中有广泛应用。

1. 循环群

最简单的平凡群,也就是只包含单位元的群,比如 $(\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.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)} = a^{kq} = (a^k)^q = 1^q = 1 \pmod n $$

也就是 $a^{\phi(n)} \equiv 1 \pmod n$,证毕。

5. 总结

这一讲,我们介绍了循环群,它的结构简单,可以由一个元素(生成元)生成。所有循环群都是 Abel 群,循环群的子群和商群均是循环群。循环群的阶和元素的阶有着特殊的关系,性质比较多,大家多看几遍,慢慢熟悉。任意无限循环群都与 $Z$ 同构,任意有限循环群都与 $Z_n$ 同构。