13.陪集和拉格朗日定理

文档摘要

title: 13. 陪集和拉格朗日定理 tags: zk basic abstract algebra group theory coset WTF zk 教程第 13 讲：陪集和拉格朗日定理在群论中，陪集是一种描述群中平移或变换的重要概念，理解陪集有助于我们研究群的对称性和结构。本讲将介绍陪集的定义及其性质，以及拉格朗日定理。陪集在群论中，群中的一个子集和元素运算组成的集合被称为陪集。陪集不是群，但可以将群分解为不相交、大小相等的子集，是研究群的基本工具，也是拉格朗日定理的基础。


title: 13. 陪集和拉格朗日定理
tags:
  - zk
  - basic
  - abstract algebra
  - group theory
  - coset

WTF zk 教程第 13 讲：陪集和拉格朗日定理

在群论中，陪集是一种描述群中平移或变换的重要概念，理解陪集有助于我们研究群的对称性和结构。本讲将介绍陪集的定义及其性质，以及拉格朗日定理。

1. 陪集

在群论中，群中的一个子集和元素运算组成的集合被称为陪集。陪集不是群，但可以将群分解为不相交、大小相等的子集，是研究群的基本工具，也是拉格朗日定理的基础。

陪集定义： 给定一个群 (G, ) 和它的一个子群 (H, )，对于 G 中的一个元素 a，我们定义与 H 关于左陪集的运算：aH = \{ah \mid h \in H\}。这表示将 H 中的每个元素 h 与 a 进行运算，得到的新集合 aH 被称为左陪集。为了简单，我们省略符号，将左陪集记为 aH。

注意：运算是群中元素之间的运算，运算结果是元素；而运算是群中元素和子群之间的运算，效果是该元素与子群中每个元素进行运算，运算结果是集合。你可以把理解运算理解为元素和集合之间的运算。

同样，我们可以定义右陪集 Ha = \{ha \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}。

2. 陪集的性质

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. 子群的陪集和子群中的元素一一对应，且元素数量相等（等势性）¹： |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。

3. 同余关系

在数论中，同余关系是一个基本而重要的概念。现在，我们将介绍如何通过陪集的概念将同余关系拓展到群论中。

3.1 定义

在群 G 中，如果元素 a, b 属于子集 H 构造的同一个陪集里，我们称 a 和 b 在模 H 下同余，记为 a \equiv b \pmod{H}。

3.2 同余的充要条件

下面，我们介绍 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

点我展开证明

上一节已经证明了陪集相等的充要条件，和这里是一样的。

3.3 等价关系

同余关系在群论中依然是等价关系，保持着一些重要的性质：

自反性： 对于任意 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 后的余数分为不同的等价类。

4. 拉格朗日定理

拉格朗日定理是群论中的一个基本定理，它指出，如果 G 是一个有限群，H 是 G 的子群，那么 H 的阶（元素个数）一定整除 G 的阶¹，即 |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|。

5. 重温费马小定理

之前我们在数论基础中学过费马小定理，现在我们重温一下：

如果 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}

6. 总结

这一讲，我们介绍了陪集和拉格朗日定理。陪集由子集与元素运算生成的集合，它不是群，却可以将群分解为不相交、大小相等的子集，是研究群的基本工具，咱们要好好的掌握它。

"势"（cardinality）和 "阶"（order）在群论中是相关但稍微不同的概念：1. 势（Cardinality）："势" 指的是群中元素集合的基数，也就是群中元素的个数。它表示了群的大小。
势通常用来描述群的元素数量，而不涉及群的结构或属性。
例如，如果一个群 G 中有 5 个元素，我们可以说 G 的势为 5。2. 阶（Order）："阶" 通常用来描述具有某种特定性质的子群或元素的数量。
阶可以表示子群的大小，例如，如果一个子群 H 有 3 个元素，我们可以说 H 的阶为 3。
也可以用来表示元素的阶，特别是在循环群中，元素的阶表示生成该元素所需的最小次数。
总之，势通常用于描述整个群的大小，而阶可以用于描述子群或元素的大小，通常在特定上下文中使用。这两个概念都是群论中用来描述群及其组成部分的重要术语。 ↩ ↩