Skip to content

Latest commit

 

History

History
235 lines (132 loc) · 13.1 KB

readme.md

File metadata and controls

235 lines (132 loc) · 13.1 KB
title tags
13. 陪集和拉格朗日定理
zk
basic
abstract algebra
group theory
coset

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

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

1. 陪集

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

陪集定义: 给定一个群 $(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}$

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. 子群的陪集和子群中的元素一一对应,且元素数量相等(等势性)1 $|H|=|aH|$

点我展开证明👀

对于子群 $H$ 和陪集 $aH$,我们想要证明它们是等势的,即存在一个双射 $f: H \to aH$

考虑定义在 $H$ 上的映射 $f: H \to bH$,其中 $f(h) = ah$。我们需要验证 $f$ 是一个双射,即它是一一对应的。

  1. 单射性(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$。证毕。

  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$ 的阶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$,满足条件。

要注意,拉格朗日定理的逆定理不一定成立:

  1. 即使 $H$ 的阶整除 $G$ 的阶, $H$ 也不一定是 $G$ 的子集,仍需要验证子群的性质。

  2. $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. 总结

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

Footnotes

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