title
tags
13. 陪集和拉格朗日定理
zk
basic
abstract algebra
group theory
coset
WTF zk 教程第 13 讲：陪集和拉格朗日定理 在群论中，陪集是一种描述群中平移或变换的重要概念，理解陪集有助于我们研究群的对称性和结构。本讲将介绍陪集的定义及其性质，以及拉格朗日定理。
在群论中，群中的一个子集和元素运算组成的集合被称为陪集。陪集不是群，但可以将群分解为不相交、大小相等的子集，是研究群的基本工具，也是拉格朗日定理的基础。
陪集定义： 给定一个群 $(G, 🐔)$ 和它的一个子群 $(H, 🐔)$ ，对于 $G$ 中的一个元素 $a$ ，我们定义与 $H$ 关于左陪集的 🦆 运算：$a🦆H = {a🐔h \mid h \in H}$ $H$ 中的每个元素 $h$ 与 $a$ 进行 🐔 运算，得到的新集合 $a🦆H$ 被称为左陪集。为了简单，我们省略 🦆 符号，将左陪集记为 $aH$ 。
注意 ：🐔 运算是群中元素之间 的运算，运算结果是元素；而 🦆 运算是群中元素和子群 之间的运算，效果是该元素与子群中每个元素进行 🐔 运算，运算结果是集合。你可以把理解 🦆 运算理解为元素和集合之间的 🐔 运算。
同样，我们可以定义右陪集 $Ha = {h🐔a \mid h \in H}$ 。
由于群不一定满足交换律，因此左右陪集不一定相等。但由于大部分密码学使用的群都满足交换律，因此我们在教程中就不分左右，统称为陪集。
举个例子，整数加法群的子群 $3\mathbb{Z}=\set{...,-6,-3,0,3,6,...}$ 和元素 $1$ 做加法，得到陪集 $1+3\mathbb{Z} =\set{...,-5,-2,1,4,7,...}$ 。也可以用元素 $2$ 做加法，得到陪集 $2+3\mathbb{Z} =\set{...,-4,-1,2,5,8,...}$ 。也可以用元素 $3$ 做加法，得到陪集 $3+3\mathbb{Z} =\set{...,-6,-3,0,3,6,...}$ ，也就是子集 $3\mathbb{Z}$ 本身，也等于 $0 + 3\mathbb{Z}$ 得到的陪集。也可以用元素 $4$ 做加法，得到陪集 $4+3\mathbb{Z} =\set{...,-5,-2,1,4,7,...}$ ，可以看到和 $1+3\mathbb{Z}$ 相等。你可以继续尝试，但是得到的陪集会和之前的陪集重复，陷入循环。
再举个例子， $Z_6$ 加法群的子群 $\set{0,2,4}$ 和元素 $0$ 做加法，得到陪集 $\set{0,2,4}$ （和元素 2 或 4 做运算也会得到这个陪集）；和元素 $1$ 做加法，得到陪集 $\set{1,3,5}$ （和元素 3 或 5 做运算也会得到这个陪集）。
最后一个例子， $Z^*_5 = \set{1,2,3,4}$ 乘法群的子群 $H = \set{1,4}$ 和元素 $1$ 做乘法，得到陪集 $\set{1,4}$ ；和 $2$ 运算得到 $\set{2, 3}$ ；和 $3$ 运算得到 $\set{2, 3}$ ；和 $4$ 运算得到 $\set{1,4}$ 。
1. 陪集划分了整个群，每个元素都属于某个陪集： 如果 $H$ 是 $G$ 的子群，$a \in G$ $a \in aH$ 。证明很简单，因为子群 $H$ 必然包含单位元 $e$ ，那么 $aH$ 必然包含 $ae = a$ ，那么 $a$ 属于这个陪集。证毕。
2. 子群和子群中元素运算产生的陪集，等于子群本身： 如果 $H$ 是 $G$ 的子群，元素 $a \in G$ ，当且仅当 $a \in H$ 时，有 $aH = H$ 。这也意味着子群 $H$ 本身也是自己的陪集。
点我展开证明👀
充分性： 因为 $a \in H$ ，根据群的封闭性，$aH$ $H$ ，因此 $aH \subseteq H$ 。另一方面，设任意 $b \in H$ ，根据子群性质，则有 $a^{-1}b \in H$ ，两边同时运算 $a$ ，则有 $aa^{-1}b \in aH$ ，即 $b \in aH$ 。也就是说任意 $b \in H$ ，都有 $b \in aH$ ，因此 $H \subseteq aH$ 。因此， $H = aH$ ，充分性证明完毕。
必要性： 因为 $a \in G$ ，有 $aH = H$ 成立。因为单位元 $e$ 也在群 $H$ 中，因此存在 $b \in H$ 使得 $ab = e$ ，则 $a = b ^{-1}$ 。根据群的逆元素存在定理， $a = b^{-1} \in H$ ，也就是 $a \in H$ 。证毕。
3. 陪集相等的充要条件： $H$ 是群 $G$ 的子群，元素 $a, b \in G$ ，那么陪集 $aH = bH$ ，当且仅当 $a^{-1}b \in H$ 。
点我展开证明👀
充分性： 由于 $aH = bH$ ，且 $b \in bH$ ，因此存在 $h \in H$ 使得 $ah = b$ 。又因为 $a, b \in G$ ，所以 $a$ 的逆元存在，两边同乘以 $a^{-1}$ ，有 $h = a^{-1}b$ ，因此 $a^{-1}b \in H$ 。证毕。
必要性： 给定 $a^{-1}b \in H$ ，存在 $h \in H$ 使得 $a^{-1}b = h$ 成立。等式两边同乘 $a$ ，得到 $b = ah$ ，两边同时乘以 $H$ ，有 $bH = ahH$ ，又因为 $h \in H$ ，有 $hH = H$ ，所以 $bH = aH$ 。证毕。
4. 陪集不相交性质： 一个子群 $H$ 的两个陪集要么相同，要么不相交，即交集为空集。 $H$ 是群 $G$ 的子群，元素 $a, b \in G$ ，如果陪集 $aH \neq bH$ ，则 $aH \cap bH = \varnothing$ 。
点我展开证明👀
我们使用反证法，假设陪集 $aH \neq bH$ ，但是 $aH$ 和 $bH$ 有公共元素 $h$ 。那么有 $h_1, h_2 \in H$ 使得 $h = ah_1 = bh_2$ ，得到 $ah_1 = bh_2$ 。我们在等式两边同时乘以 $H$ ，有 $ah_1H = bh_2H$ 。又因为 $h_1, h_2 \in H$ ，因此 $h_1H = h_2H = H$ ，因此有 $aH = bH$ ，两个陪集相等，与假设矛盾。因此如果 $aH \neq bH$ ，则 $aH$ 和 $bH$ 没有公共元素，即 $aH \cap bH = \varnothing$ 。证毕
5. 子群的陪集和子群中的元素一一对应，且元素数量相等（等势性）1 $|H|=|aH|$ 。
点我展开证明👀
对于子群 $H$ 和陪集 $aH$ ，我们想要证明它们是等势的，即存在一个双射 $f: H \to aH$ 。
考虑定义在 $H$ 上的映射 $f: H \to bH$ ，其中 $f(h) = ah$ 。我们需要验证 $f$ 是一个双射，即它是一一对应的。
单射性（Injection）： 对于任意 $x_1, x_2 \in H$ ，如果 $f(x_1) = f(x_2)$ ，则 $x_1 = x_2$ 。
假设 $f(x_1) = f(x_2)$ ，即 $ax_1 = a x_2$ 。由于 $a$ 是群元素，存在逆元素，可以等式两边左乘逆元素得到 $x_1 = x_2$ 。证毕。
满射性（Surjection）： 对于任意 $y \in aH$ ，存在 $x \in H$ ，使得 $f(x) = y$ 。
由于 $y \in aH$ ，因此存在 $h \in H$ 使得 $y = ah$ 。令 $x = a^{-1} y$ ，则 $f(x) = a a^{-1} y = y$ 。因此，$f$
由单射性和满射性可知，$f$ $H$ 和 $aH$ 是等势的，他们的元素一一对应，且元素数量相等。
我们用 $Z^*_5$ 乘法群的子群 $H=\set{1,4}$ 作为例子，检验这些性质。根据之前的计算，我们知道它的陪集有 $1H = 4H = \set{1,4}$ ， $2H = 3H = \set{2,3}$ 。
性质 1： 元素 1 和 4 属于陪集 $\set{1,4}$ ，元素 2 和 3 属于陪集 $\set{2,3}$ ，陪集划分了整个群，每个元素都属于某个陪集。
性质 2： 子群中元素 1 和 4 产生的陪集等于子集本身 $H=\set{1,4}$ 。
性质 3： $1H = 4H = \set{1,4}$ ，有 $1^{-1} \times 4 = 4 \in H$ 。$2H = 3H = \set{2,3}$ $2^{-1} \times 3 = 4 \in H$
性质 4： 一个子群 $H$ 的两个陪集要么相同，要么不相交。
性质 5： 子群和陪集中的元素数量相等，都是 2。
在数论中，同余关系是一个基本而重要的概念。现在，我们将介绍如何通过陪集的概念将同余关系拓展到群论中。
在群 $G$ 中，如果元素 $a, b$ 属于子集 $H$ 构造的同一个陪集里，我们称 $a$ 和 $b$ 在模 $H$ 下同余，记为 $a \equiv b \pmod{H}$ 。
下面，我们介绍 $a \equiv b \pmod{H}$ 的充要条件。
1. 存在 $h \in H$ ，使得 $a=bh$ 成立，也可以写为 $b^{-1}a = h$
点我展开证明👀
充分性
根据 $a \equiv b \pmod{H}$ ，因此存在 $h \in H$ 使得 $b^{-1}a = h$ ，两边同乘以 $b$ ，得到 $a = bh$ 。证毕。
必要性
存在 $h \in H$ ，使得 $a=bh$ 成立，两边同时乘以 $b^{-1}$ ，有 $b^{-1}a = h$ ，因此 $aH = bH$ 。又因为 $a \in aH$ ， $b \in bH$ ，因此它们属于同一个陪集。证毕。
2. $b \in aH$
点我展开证明👀
充分性
根据上一条证明，有 $aH = bH$ ，又因为 $b \in bH$ ，所以 $b \in aH$ 。
必要性
根据 $b \in aH$ ，又因为 $b \in bH$ ，因此 $aH$ 和 $bH$ 的交集不为空，因此 $aH = bH$ 。又因为 $a \in aH$ ， $b \in bH$ ，因此它们属于同一个陪集。证毕。
3. $bH = aH$
点我展开证明👀
上一节已经证明了陪集相等的充要条件，和这里是一样的。
同余关系在群论中依然是等价关系，保持着一些重要的性质：
自反性： 对于任意 $a \in G$ ，都有 $a \equiv a \pmod{H}$ 。
对称性： 如果 $a \equiv b \pmod{H}$ ，那么必有 $b \equiv a \pmod{H}$ 。
传递性： 如果 $a \equiv b \pmod{H}$ 且 $b \equiv c \pmod{H}$ ，那么必有 $a \equiv c \pmod{H}$ 。
因此，陪集就类似于模运算中的剩余类，可以将群中的元素分到不同的等价类中。
我们用 $Z^*_5$ 乘法群的子群 $H=\set{1,4}$ 为例，它的陪集将群分为 $\set{1,4}$ 和 $\set{2,3}$ 两类。
再举个整数加法群的子群 $3\mathbb{Z}=\set{...,-6,-3,0,3,6,...}$ 的例子，它的陪集将群分为：
$$
0+3\mathbb{Z} =\set{...,-6,-3,0,3,6,...}
$$
$$
1+3\mathbb{Z} =\set{...,-5,-2,1,4,7,...}
$$
$$
2+3\mathbb{Z} =\set{...,-4,-1,2,5,8,...}
$$
这 3 个陪集正好对应模 3 下的剩余群，将所有整数根据除 3 后的余数分为不同的等价类。
拉格朗日定理是群论中的一个基本定理，它指出，如果 $G$ 是一个有限群，$H$ $G$ 的子群，那么 $H$ 的阶（元素个数）一定整除 $G$ 的阶1 $|G| = |H| \cdot |G:H|$ ，其中 $G:H$ 为正整数，被称为 $H$ 对 $G$ 的指数。
点我展开证明👀
$G$ 是一个有限群，子群 $H$ 构造的陪集互不相交，并且划分了整个群。
我们可以构造一组不相交的 $n$ 个陪集 $g_1H, g_2H, ... , g_nH$ 划分整个群。那么 $|G| = |g_1H| +|g_2H|+ ... + |g_nH|$ 。又因为每个陪集的阶都与子群数量相等，因此有 $|G| = |H| +|H|+ ... + |H| = n|H|$ 。我们把正整数 $n$ 记为 $G:H$ ，称为 $H$ 对 $G$ 的指数。证毕
拉格朗日定理可以帮助我们缩小子群的范围，因为子群的阶必须能整除母群的阶，那些不能整除的一定不是子群。还是以 $Z^*_5$ 乘法群为例，它的阶为 $4$ ，那么 $\set{1,2,3}$ 一定不是子群，因为它的阶为 $3$ ，不能整除 $4$ 。而子群 $\set{1,4}$ 的阶为 $2$ ，可以整除 $4$ ，满足条件。
要注意，拉格朗日定理的逆定理不一定成立：
即使 $H$ 的阶整除 $G$ 的阶， $H$ 也不一定是 $G$ 的子集，仍需要验证子群的性质。
$d$ 是 $|G|$ 的约数，不一定存在子群 $H$ ，使得 $|H| = |d|$ 。
之前我们在数论基础中学过费马小定理，现在我们重温一下：
如果 $p$ 是一个质数，则对于任意整数 $a$ 是，有
$$
a^{p-1} \equiv 1 \pmod{p}
$$
现在我们用陪群的等势性证明费马小定理。由于 $p$ 是质数， $\mathbb{Z}_p^*=\set{1,2,...,p-1}$ 和乘法构成整数模 $p$ 乘法群。
对于任意整数 $a$ ，有 $a \mod{p} \in \mathbb{Z}^* _p$ 。我们用它与 $\mathbb{Z}^* _p$ 运算生成陪集 $a\mathbb{Z}^* _p = \set{a,2a,...,(p-1)a}$ 。由于 ${a \mod{p}} \in \mathbb{Z}^* _p$ ，所以 $a\mathbb{Z}^* _p = \mathbb{Z}^* _p$ 。
我们将它们中的所有元素相乘，得到：
$$
a \cdot 2a \cdot ... \cdot (p-1)a \equiv 1 \cdot 2 \cdot ... \cdot (p-1) \pmod{p}
$$
整理得到：
$$
a^{p-1} (p-1)! \equiv (p-1)! \pmod{p}
$$
两边同时消去 $(p-1)!$ ，得到费马小定理：
$$
a^{p-1} \equiv 1 \pmod{p}
$$
这一讲，我们介绍了陪集和拉格朗日定理。陪集由子集与元素运算生成的集合，它不是群，却可以将群分解为不相交、大小相等的子集，是研究群的基本工具，咱们要好好的掌握它。