readme.md

title	tags
14. 正规子群和商群	zk abstract algebra group theory normal subgroup quotient group

WTF zk教程第14讲：正规子群和商群

在上一讲中，我们讨论了陪集，它是由子群和元素运算生成的集合，但并非群。然而，当子群满足特定的性质时，陪集可以构成一个群。这种满足性质的子群被称为正规子群，而由陪集构成的群则被称为商群。在本讲中，我们将深入学习它们。

1. 正规子群

正规子群是群论中一个特殊的子群类型，它的左陪集和右陪集是相同的集合。

定义：给定群 $G$ 和它的子群 $H$，如果对于任意 $g \in G$，都有 $gH = Hg$（左陪集等于右陪集），则称 $H$ 是 $G$ 的正规子群，记作 $H \trianglelefteq G$。

这个定义有时也会写成 $gHg^{-1} = H$。而形如 $aXa^{-1}$ 的运算也被称为共轭运算，换句话说，正规子群是一个在共轭运算下保持不变的子群。对于正规子群 $H$ 中的元素 $h$ 和任意 $g \in G$，有 $ghg^{-1} \in H$ 成立。

任何群 $G$ 都有两个平凡的正规子群：${e}$ 和 $G$。

密码学中常见群的子群基本都是正规子群。比如整数加法群 $\mathbb{Z}$，它的任意子群 $n\mathbb{Z} = \set{..., -2n, -n, 0, n, 2n, ...}$ 都是正规子群。因为对于任意整数 $k$ 和 $n\mathbb{Z}$ 加法运算产生的左陪集和右陪集相等 $k+n\mathbb{Z} = n\mathbb{Z} + k$。再比如整数模 $5$ 乘法群，由于乘法满足交换律，因此它的左陪集也和右陪集相等，任意子群都是正规子群。

2. 商群

当子群是正规子群的时候，它所构建的陪集能构成一个群，这个群被称为商群。

定义：给定群 $(G,🐔)$ 和它的正规子群 $H$，商群 $(G/H, 🐶)$（读作G模H）。商群的集合由所有的左陪集构成 $G/H = \set{gH \mid g \in G}$，商群的🐶运算定义在两个陪集间，对于 $g_1, g_2 \in G$，有 $(g_1H) 🐶 (g_2H) = (g_1🐔g_2)H$。

商群和我们之前熟悉的群不同，每个元素都是形如 $gH$ 的左陪集，而不是数字。你可以把🐶运算理解为陪集间的🐔运算，$(g_1H) 🐶 (g_2H) = g_1Hg_2H$。当子群是正规子群时，🐶运算才是定义良好的，有 $g_1Hg_2H=g_1(Hg_2)H=g_1g_2HH=g_1g_2H$。为了简单，我们会省略🐶运算，记为 $(g_1H) (g_2H)$。

下面，我们检验商群是否符合群的 4 个基本性质：

1. 封闭性： 根据定义，对于任意 $g_1H, g_2H \in G/H$，有 $(g_1H)(g_2H)=(g_1g_2)H$，由于 $g_1g_2 \in G$，因此 $g_1g_2H \in G/H$，封闭性成立。

2. 结合律： 对于任意 $g_1H, g_2H, g_3H \in G/H$，有 $[(g_1H)(g_2H)] (g_3H)= [(g_1g_2)H] (g_3H) = (g_1g_2g_3)H$，而 $(g_1H)[(g_2H)(g_3H)]=(g_1H)[(g_2g_3)H] = (g_1g_2g_3)H$，因此 $[(g_1H)(g_2H)] (g_3H) = (g_1H) [(g_2H)(g_3H)]$，结合律成立。

3. 单位元： $H$ 为 $G/H$ 的单位元。因为群 $G$ 的单位元为 $e$，有 $eH = H$ 为 $H$ 的陪集，因此 $H \in G/H$。对于任意 $gH \in G/H$，有 $gH H = g H$，因此 $H$ 为 $G/H$ 的单位元。

4. 逆元素： 对于任意 $gH \in G/H$， $gH$ 的逆元为 $g^{-1}H$。因为 $(gH)(g^{-1}H) = (gg^{-1})H = H$。

经检验，商群满足群的4条基本性质，商群是群，很棒。接下来，咱们看一下商群的阶数（元素数量）。由于商群是陪集组成的群，因此它的阶数就是左陪集的数量，根据拉格朗日定理：

$$ |G/H| = [G:H]= [G]/[H] $$

我们可以看到，商群的阶就是母群与子群的阶的商，这也是为什么它被称为“商群”。

2.1 例子

首先，我们以整数加法群 $\mathbb{Z}$ 和正规子群 $n\mathbb{Z}$ 为例，它的商群为 $\mathbb{Z}/n\mathbb{Z}$。

• 在商群中，陪集 $k + n\mathbb{Z}$ 表示所有模 $n$ 下与 $k$ 同余的整数。这个商群的阶为 $n$，元素为 $0 + n\mathbb{Z}, 1 + n\mathbb{Z}, \ldots, (n-1) + n\mathbb{Z}$。这个商群的本质其实就是模 $n$ 下的剩余群。

• 商群的运算定义为 $(a + n\mathbb{Z}) 🐶 (b + n\mathbb{Z}) = (a+b) + n\mathbb{Z}$，依然属于 $\mathbb{Z}/n\mathbb{Z}$。

• 单位元：为 $0 + n\mathbb{Z}$

• 逆元： $k + n\mathbb{Z}$ 的逆元为 $-k + n\mathbb{Z}$。

接下来，我们以模 $5$ 乘法群 $\mathbb{Z}^*_5$ 和正规子群 $H=\set{1,4}$ 为例。

• 商群为 $\mathbb{Z}^*_5/H=\set{\set{1,4}, \set{2,3}}$，阶为 $2 = 4/2$。

• 由于我们的例子是乘法群，商群之间的运算也是陪集之间的模5乘法。

• 单位元：为 $\set{1,4}$，因为 $\set{1,4} 🐶 \set{1,4} = \set{1 \times 1, 1 \times 4, 4 \times 1, 4 \times 4} = {1,4}$，而 $\set{1,4} 🐶 \set{2,3} = \set{2,3}$。

• 逆元： $\set{1,4}$ 的逆元为 $\set{1,4}$， $\set{2,3}$ 的逆元为 $\set{2,3}$。

3. 商群和同余关系

上一讲，我们利用陪集将整数的同余关系拓展到了群，形成了一种特别的等价关系：对于群 $G$ 和它的一个子群 $H$，如果元素 $a$ 和 $b$ 属于同一个 $H$ 的陪集，我们称 $a$ 和 $b$ 在模 $H$ 下同余，记为 $a \equiv b \pmod{H}$。在商群中，这种同余关系更加特殊：

1. 运算封闭 由于商群是正规子群的陪集构成的群，运算是定义明确的。对于群 $G$ 中的元素 $a, b, c, d$ 和正规子群 $H$，如果有 $a \equiv b \pmod{H}$ 和 $c \equiv d \pmod{H}$，则有 $ac \equiv bd \pmod{H}$。

2. 商群中的每个元素都代表了群中的一个等价类 商群 $G/H$ 在结构上式对群 $G$ 的一个简化。商群中的每个元素是陪集，并且保持了群 $G$ 的运算。通过同余关系，商群的每个元素代表了群中的一个等价类。

我们会在下一讲介绍同态和同构时，更深入的介绍商群的良好性质。

4. 总结

这一讲，我们介绍了群论中两个重要的概念：正规子群和商群。正规子群是特殊的一种子群，它生成的左陪集和右陪集相等， $gH=Hg$，密码学中常见群基本都满足这一特性。当子群是正规子群时，本来只是集合的陪集可以构成群，这种群被称为商群。你可以把商群理解为某种剩余群，可以帮助我们更好的理解群的结构，还可以用来构建密码学算法，我们之后还会不断的学习它。