Home 数学 离散数学 代数结构

# 群子集的乘积运算

# 定义

设 AA 和 BB 是群 GG 的两个非空子集，称集合：

AB={ab∣a∈A,b∈B}AB = \{ab|a\in A, b\in B \}

为群的子集 AA 与 BB 的乘积 (product)

如果 g∈Gg\in G 为群 GG 的一个元素，A={g}A=\{g\} ，则：

  • ABAB 简记为 gB={gb∣b∈B}gB = \{gb|b\in B\}；
  • BABA 简记为 Bg={bg∣b∈B}Bg = \{bg|b\in B\}；

注意，即使有 AB=BAAB=BA，也不意味着 ∀a∈A,b∈B,ab=ba\forall a\in A, b\in B,\ \ \ ab =ba，正确的结论应该是：∀a∈A,b∈B,∃a′∈A,b′∈B,ab=b′a′\forall a\in A, b\in B,\ \ \ \exist a'\in A, b'\in B,\ \ \ ab = b'a'

# 交换群的交换律

当 GG 是交换群时，对 GG 的任意子集 A,BA,B ，满足交换律，有 AB=BAAB=BA ；但对于非交换群，一般没有 AB=BAAB=BA ，也就是没有交换律成立。

# 满足结合律

群的子集运算满足结合律：A(BC)=(AB)CA(BC) = (AB)C ；

# 对单元素满足消去律

若 gA=gBgA=gB 或 Ag=BgAg=Bg，则 A=BA=B。

但对普遍的

AC=BC⇏A=BAC=BC\not\rArr A=B

证明（不妨考虑 gA=gBgA=gB ）

∀a∈A\forall a\in A，有 ga∈gAga\in gA ；

因为 gA=gBgA=gB ，所以 ga∈gBga\in gB ，所以：

∃b∈B,ga=gb\exist b\in B,\ \ \ ga=gb

由群满足消去律可得：b=ab=a ；

所以 a=b∈Ba=b\in B ，所以有 A⊆BA\sube B ；同理可证 B⊆AB\sube A，从而可得 A=BA=B。

# 幂运算

若 HH 是群 GG 的子群，则 HH=HHH=H。

# 乘积的子群充要条件

如果 A,BA,B 是群 GG 的两个子群，则 ABAB 也是群 GG 的子群当且仅当 AB=BAAB=BA。

必要性: AB≤G⇒AB=BAAB\leq G\rArr AB=BA：

对于 ∀a,b,ab∈AB\forall a,b,\ \ ab\in AB，只需证 ab∈BAab\in BA；

由于 AB≤GAB\leq G ，所以 ∃a′b′∈AB,(ab)−1=a′b′\exist a'b'\in AB,\ \ \ (ab)^{-1}=a'b'

ab=((ab)−1)−1=(a′b′)−1=b′−1a′−1∈BAab=((ab)^{-1})^{-1}=(a'b')^{-1}=b'^{-1}a'^{-1}\in BA

从而可得 AB⊆BAAB\sube BA ；同理可证 BA⊆ABBA\sube AB，从而可得 AB=BAAB=BA。

充分性: AB=BA⇒AB≤GAB=BA\rArr AB\leq G：

对于 ∀a1,b1,a2,b2,a1b1,a2b2∈AB\forall a_1,b_1,a_2,b_2,\ \ \ a_1b_1,a_2b_2\in AB，有：a1b1(a2b2)−1∈ABa_1b_1(a_2b_2)^{-1}\in AB；

a1b1(a2b2)−1=a1b1b2−1a2−1=a1(b1b2−1)a2−1∈ABA=A(BA)=A(AB)=(AA)B=ABa_1b_1(a_2b_2)^{-1}=a_1b_1b_2^{-1}a_2^{-1}=a_1(b_1b_2^{-1})a_2^{-1}\\ \in ABA=A(BA)=A(AB)=(AA)B=AB

从而由子群判定定理二可知 ABAB 是 GG 的子群

# 乘积的子集关系

设 A,B,CA,B,C 是群 GG 的非空子集（不一定是群），若 B⊆CB⊆C ，则有 AB⊆ACAB⊆AC 和 BA⊆BCBA⊆BC。

证明

对任意 x∈ABx\in AB ，则存在 a∈A,b∈Ba\in A,b\in B，使得 x=abx=ab 。由 b∈Bb\in B ，且 B⊆CB⊆C，因此 b∈Cb\in C，因此 x=ab∈ACx=ab\in AC ，因此 AB⊆BCAB⊆BC 。

对任意 x∈BAx\in BA ，则存在 a∈A,b∈Ba\in A,b\in B ，使得 x=bax=ba 。由 b∈Bb\in B ，且 B⊆CB⊆C ，因此 b∈Cb\in C ，因此 x=ab∈ACx=ab\in AC ，因此 BA⊆CABA⊆CA 。

# 子群的陪集及其性质

# 陪集定义

GG 是群，HH 是 GG 的子群

对任意 a∈Ga\in G，群 GG 的子集 aH={ah∣h∈H}aH=\{ah|h\in H\} 与 Ha={ha∣h∈H}Ha=\{ha|h\in H\} ，分别称为 HH 在 GG 中的左陪集 (left coset) 和右陪集 (right coset)

子群 HH 的所有右陪集构成的集合族 G\HG\backslash H 是 GG 的一个划分

子群 HH 的所有左陪集构成的集合族 G/HG/H 也是 GG 的一个划分

注意陪集不一定是群了

# 陪集举例

对于群 (U(5),⊗5)(U(5),⊗_5)，子群 H={1,4}H=\{1,4\}：

⊗5⊗_51234
11234
22413
33142
44321

1H={1⊗51,1⊗54}={1,4}2H={2⊗51,2⊗54}=2,33H={3⊗51,3⊗54}={3,2}4H={4⊗51,4⊗54}={4,1}1H=\{1⊗_5 1,1⊗_5 4\}=\{1,4\}\\ 2H=\{2⊗_5 1,2⊗_5 4\}={2,3}\\ 3H=\{3⊗_5 1,3⊗_5 4\}=\{3,2\}\\ 4H=\{4⊗_5 1,4⊗_5 4\}=\{4,1\}

HH 有两个不同的陪集 {1,4}\{1, 4\} 和 {2,3}\{2,3\}。

对于下面的置换群 (G,∘)(G,\circ) ，子群 H={f1,f2}H=\{f_1, f_2\}：

∘\circf1f_1f2f_2f3f_3f4f_4f5f_5f6f_6
f1f_1f1f_1f2f_2f3f_3f4f_4f5f_5f6f_6
f2f_2f2f_2f1f_1f6f_6f5f_5f4f_4f3f_3
f3f_3f3f_3f5f_5f1f_1f6f_6f2f_2f4f_4
f4f_4f4f_4f6f_6f5f_5f1f_1f3f_3f2f_2
f5f_5f5f_5f3f_3f4f_4f2f_2f6f_6f1f_1
f6f_6f6f_6f4f_4f2f_2f3f_3f1f_1f5f_5

f1H={f1∘f1,f1∘f2}={f1,f2}f2H={f2∘f1,f2∘f2}={f2,f1}f3H={f3∘f1,f3∘f2}={f3,f5}f4H={f4∘f1,f4∘f2}={f4,f6}f5H={f5∘f1,f5∘f2}={f5,f3}f6H={f6∘f1,f6∘f2}={f6,f4}Hf3={f1∘f3,f2∘f3}={f3,f6}Hf4={f1∘f4,f2∘f4}={f4,f5}Hf5={f1∘f5,f2∘f5}={f5,f4}Hf6={f1∘f6,f2∘f6}={f6,f3}f_1 H=\{f_1\circ f_1, f_1\circ f_2\}=\{f_1, f_2\}\\ f_2 H=\{f_2\circ f_1, f_2\circ f_2\}=\{f_2, f_1\}\\ f_3 H=\{f_3\circ f_1, f_3\circ f_2\}=\{f_3, f_5\}\\ f_4 H=\{f_4\circ f_1, f_4\circ f_2\}=\{f_4, f_6\}\\ f_5 H=\{f_5\circ f_1, f_5\circ f_2\}=\{f_5, f_3\}\\ f_6 H=\{f_6\circ f_1, f_6\circ f_2\}=\{f_6, f_4\}\\ Hf_3=\{f_1\circ f_3, f_2\circ f_3\}=\{f_3, f_6\}\\ Hf_4=\{f_1\circ f_4, f_2\circ f_4\}=\{f_4, f_5\}\\ Hf_5=\{f_1\circ f_5, f_2\circ f_5\}=\{f_5, f_4\}\\ Hf_6=\{f_1\circ f_6, f_2\circ f_6\}=\{f_6, f_3\}

HH 有三个不同的陪集，且左右陪集不相等，例如 f3H≠Hf3f_3H≠Hf_3。

# 不同元素陪集相同充要条件

∀a,b∈G\forall a,b\in G，

  • Ha=HbHa=Hb 当且仅当 a∈Hba\in Hb 当且仅当 ab−1∈Hab^{-1}\in H；
  • aH=bHaH=bH 当且仅当 a∈bHa\in bH 当且仅当 b−1a∈Hb^{-1}a\in H；

# 陪集不变的充要条件

设 HH 是群 GG 的子群，对任意的 a∈Ga\in G：

  • Ha＝HHa＝H 的充分必要条件是 a∈Ha\in H；

引理

因 e∈He\in H ，所以 a＝ea∈Haa＝ea\in Ha 。

证明

必要性：若 Ha＝HHa＝H ，则因为 a∈Haa\in Ha ，从而 a∈Ha\in H 。

充分性：反之若 a∈Ha\in H ，则对任意 ha∈Haha\in Ha ，由 HH 对群运算封闭，也有 ha∈Hha\in H ，从而有 Ha⊆HHa\subseteq H；

而这时对任意 h∈Hh\in H ，由 a∈Ha\in H 有 a−1∈Ha^{-1}\in H ，从而 ha−1∈Hha^{-1}\in H ，从而有 h＝ha−1a∈Hah＝ha^{-1}a\in Ha ，即有 H⊆HaH\subseteq Ha 。

于是又 Ha⊆H,H⊆HaHa\subseteq H,H\subseteq Ha 得到 Ha=HHa=H 。

# 陪集的子群充要条件

设 HH 是群 GG 的子群，对任意的 a∈Ga\in G：

  • 右陪集 HaHa 是 GG 的子群当且仅当 Ha=HHa=H 当且仅当 a∈Ha\in H；
  • 左陪集 aHaH 是 GG 的子群当且仅当 aH=HaH=H 当且仅当 a∈Ha\in H；

证明以右陪集为例：

必要性：若 Ha≤GHa\leq G ，所以 e∈Hae\in Ha ，从而存在 h∈Hh\in H 使得 e＝hae＝ha ，从而 a＝h−1e=h−1∈Ha＝h^{-1}e=h^{-1}\in H ；

充分性：若 a∈Ha\in H ，则 Ha＝HHa＝H 是子群。

# 子群陪集运算性质

设 HH 是群 GG 的子群，则 ∀a,b∈G\forall a,b\in G 有：

a∈Hb⟺ab−1∈H⟺Ha=Hba\in Hb\Longleftrightarrow ab^{-1}\in H\Longleftrightarrow Ha=Hb

循环论证：

（1）a∈Hb⟹ab−1∈Ha\in Hb\Longrightarrow ab^{-1}\in H：

若 a∈Hba\in Hb ，即存在 h∈Hh\in H 使得 a=hba=hb 。从而 ab−1＝h∈Hab^{-1}＝h\in H 。

（2）ab−1∈H⟹Ha=Hbab^{-1}\in H\Longrightarrow Ha=Hb：

对于任意的 ha∈Haha\in Ha ，这里 h∈Hh\in H ，因此 hab−1∈Hhab^{-1}\in H，从而：

ha=hab−1b∈Hbha=hab^{-1}b\in Hb

这表明 Ha⊆HbHa\subseteq Hb 。类似地，对任意的 hb∈Hahb\in Ha ，这里 h∈Hh\in H 。由于 ab−1∈Hab^{-1}\in H ，则也有：

ba−1=(b−1)−1a−1=(ab−1)−1∈Hba^{-1}=(b^{-1})^{-1}a^{-1}=(ab^{-1})^{-1}\in H

因此 ha=hba−1a∈Haha=hba^{-1}a\in Ha ，这表明 Hb⊆HaHb\subseteq Ha 。综合起来就有 Ha=BbHa=Bb 。

（3）Ha=Hb⟹a∈HbHa=Hb\Longrightarrow a\in Hb：

若 Ha=HbHa=Hb ，则由 a∈Haa\in Ha （HH 是子群）可得 a∈Hba\in Hb 。

# 子群陪集构成等价关系

设 HH 是群 GG 的子群，在 GG 上定义二元关系 R∈G×GR\in G\times G：

∀a,b∈G,aRb⟺ab−1∈H\forall a,b\in G,\ \ \ a\text{R}b\Longleftrightarrow ab^{-1}\in H

则 RR 是 GG 上的等价关系，且 [a]R=Ha[a]_R=Ha 。

证明

上面已经证明了 ab−1∈H⟺Ha=Hbab^{-1}\in H\Longleftrightarrow Ha=Hb，因此 aRb⟺Ha=Hba\text{R}b\Longleftrightarrow Ha= Hb 。

从而 RR 确实是自反、对称和传递的，即 RR 是等价关系。

对任意 b∈Gb\in G ，我们有：

b∈Ha⟺Hb=Ha⟺bRa⟺b∈[a]Rb\in Ha\Longleftrightarrow Hb=Ha\Longleftrightarrow b\text{R}a\Longleftrightarrow b\in[a]_R

这就表明 Ha=[a]RHa=[a]_R 。

# 子群陪集构成划分

设 H≤GH≤G，则：

  • （i）∀a,b∈G\forall a,b\in G ,
    • Ha=HbHa=Hb ；
    • 或 Ha∩Hb=∅Ha\cap Hb=\varnothing；
  • （ii）U{Ha∣a∈G}=G\mathbb U\{Ha|a\in G\}=G。

证明 —— 由等价类的性质立即可得。

# 正规子群

若对任意元素 a∈Ga\in G 都有 aH=HaaH=Ha，即左右陪集相等，则称 HH 是 GG 的正规子群，

# 左右陪集关系

一个子群的左陪集的所有元素的逆元素组成这个子群的一个右陪集

符号化描述：

H≤GH\leq G，a∈Ga\in G，

S={x−1∣x∈aH}S=\{x^{-1}|x\in{aH}\}

# 拉格朗日定理

# 引理

HH 是 GG 的子群，对任意 a∈Ga\in G ，有 ∣H∣=∣aH∣=∣Ha∣|H|=|aH|=|Ha|，即这三个集合等势

集合等势：若两个集合前存在双函数，即称它们等势。对于有限集，就是这两个集合有相同元素个数

证明

定义 φ:H→Ha\varphi:H\to Ha 为：

∀h∈H,φ(h)=ha∈Ha\forall h\in H,\ \ \ \varphi(h)=ha\in Ha

由群的消去律我们有：∀h1,h2∈H\forall h_1,h_2\in H

φ(h1)=φ(h2)⟹h1a=h2a⟹h1=h2\varphi(h_1)=\varphi(h_2)\Longrightarrow h_1a=h_2a\Longrightarrow h_1=h_2

从而 φ\varphi 是双函数，即 ∣Ha∣=∣H∣|Ha|=|H|。

类似定义 φ′:H→a\varphi':H\to a 为

∀h∈H,φ′(h)=ah∈aH\forall h\in H,\ \ \ \varphi'(h)=ah\in aH

不难证明 ∣aH∣=∣H∣|aH|=|H|。

# 指标

设 HH 是群 GG 的子群。称子群 HH 在群 GG 中的左陪集或右陪集的个数（有限或无限）为 HH 在 GG 中的指标 (index)，记为 [G:H][G:H] 。

也称 [G:H][G:H]：GG 关于 HH 的陪集个数。

# 拉格朗日定理

HH 是有限群 GG 的子群，则：

∣G∣=∣H∣⋅[G:H]|G|=|H|\cdot[G:H]

证明

设 [G:H]=r[G:H]=r ，则子群 HH​ 有 rr 个不同的右陪集，设为 Ha1,Ha2,⋯,HarH_{a_1},H_{a_2},\cdots,H_{a_r} 。由于 G=U{Ha∣a∈G}G=U\{Ha|a\in G\} ，且对任意的 a,b∈Ga,b\in G ，Ha=HbHa=Hb 或者 Ha∩Hb=∅Ha\cap Hb=\varnothing ，因此：

G=Ha1∪Ha2∪⋯∪Har∣G∣=∣Ha1∣+∣Ha2∣+⋯+∣Har∣G=H_{a_1}\cup H_{a_2}\cup \cdots\cup H_{a_r}\\ |G|=|H_{a_1}|+|H_{a_2}|+\cdots+|H_{a_r}|

而对任意的 a∈Ga\in G ，∣Ha∣=∣H∣|Ha|=|H| ，因此 ∣G∣=r∣H∣=∣H∣⋅[G:E]|G|=r|H|=|H|\cdot[G:E] 。

# 推论 1 (元素阶与群阶的关系)

设 GG 是 nn 阶有限群，单位元是 ee ，则对 GG 的任意元素 aa ，aa 的阶 ∣a∣|a| 是 nn 的因子，且 an=ea^{n}=e 。

证明

对任意的 a∈Ga\in G ，<a><a> 是 GG 的子群，因此由拉格朗日定理 ∣<a>∣|<a>| 是 nn 的因子；

但另一方面，若 ∣a∣=r|a|=r ，则因 <a><a> 是 aa 生成的子群，于是

<a>={a0=e,a1,⋯,ar−1}<a>=\{a^{0}=e,a^{1},\cdots,a^{r-1}\}

即 ∣<a>∣=∣a∣=r|<a>|=|a|=r ，从而 ∣a∣|a| 是群 G 的阶 n 的因子，进而由 == 定理 1.6?== 有 an=ea^{n}=e ，因为对任意的 m∈Zm\in \mathbb{Z} , am=ea^{m}=e 当且仅当 r∣mr|m 。

元素的阶是群的阶的因子；

但并不是群的阶的每个因子，群都存在元素的阶恰好等于这个因子！

# 推论 2 (费马小定理)

设 pp 是素数，aa 是与 pp 互素的整数，则有：

ap−1≡1(modp)a^{p-1}\equiv1(\bmod p)

证明

因为在群 U(p)U(p) ，即群 Zp∗\mathbb{Z}_p^* 中，由于 aa 与 pp 互素，aa（准确地说，aa 整除 pp 的余数）属于 Zp∗\mathbb{Z}_p^* ，

而 Zp∗\mathbb{Z}_p^* 的阶是 p−1p-1 ，因此 ap−1a^{p-1} 等于单位元 1 ，对于 U(p)U(p) 的模 pp 乘运算而言，就是 ap−1≡1(modp)a^{p-1}\equiv 1(\bmod p) 。

# 推论 3

H,KH,K 都是 GG 的有限子群，证明：

  • （1） 记 S={hK∣h∈H}S=\{hK|h\in H\}，则 SS 是 HH 的划分，从而 ∣HK∣=∣S∣⋅∣K∣|HK|=|S|\cdot|K|
  • （2）∣HK∣=∣H∣⋅∣K∣∣H∩K∣|HK|=\frac{|H|\cdot|K|}{|H\cap K|}；

（1）证明

即证 h1Kh_1K ，h2Kh_2K 要么相等，要么不相交

h1K=h2K⇔h1−1h2∈Kh1K∩h2K=∅h_1K=h_2K\lrArr h_1^{-1}h_2\in K\\ h_1K\cap h_2K=\varnothing

（2）证明

为方便起见，记 M=H∩KM=H\cap K ，由于 HH 和 KK 都是 GG 的子群，因此 MM 也是 GG 的子群且也是 HH 的子群。

定义函数 φ:H/M→S\varphi:H/M\to S，对任意 h∈Hh\in H ，φ(hM)=hK\varphi(hM)=hK

下面证明 φ\varphi 的定义是合适的，且是双函数，从而结合拉格朗日定理有 ∣S∣=∣H/M∣=∣H∣/∣M∣|S|=|H/M|=|H|/|M| ，从而得到 ∣HK∣=∣H∣⋅∣K∣∣M∣|HK|=\frac{|H|\cdot|K|}{|M|} 。

(a) 证明 φ\varphi 的定义是合适的：

对任意 h1,h2∈Hh_1,h_2\in H ，若 h1M=h2Mh_1M=h_2M ，则 h1−1h2∈M⊆Kh_1^{-1}h_2\in M\subseteq K ，从而 φ(h1M)=φ(h2M)\varphi(h_1M)=\varphi(h_2M)，这说明 φ(hM)\varphi(hM) 的值不会因为选取的代表 hh 不同面不同，即 φ\varphi 的定义是合适的。

(b) 证明 φ\varphi 是单函数：

对任意 h1,h2∈Hh_1,h_2\in H，若 φ(h1M)=φ(h2M)\varphi(h_1M)=\varphi(h_2M)，即 h1K=h2Kh_1K=h_2K ，从而 h1−1h2∈Kh_1^{-1}h_2\in K ，

但 h1,h2∈Hh_1,h_2\in H ，因此也有 h1−1h2∈Hh_1^{-1}h_2\in H ，

从而 h1−1h2∈H∩K=Mh_1^{-1}h_2\in H\cap K=M ，

从而 h1M=h2Mh_1M=h_2M ，这就表明 φ\varphi 是单函数。

(c) 显然 φ\varphi 是满函数，对任意 hK∈ShK\in S ，都有 φ(hM)=hk\varphi(hM)=hk。

因此 ∣S∣=∣H/M∣|S|=|H/M| ，由拉格朗日定理有 ∣S∣=∣H/M∣=∣H∣/∣M∣|S|=|H/M|=|H|/|M| ，最后得到:

∣HK∣=∣H∣∣M∣∣K∣=∣H∣⋅∣K∣∣H∩K∣|HK|=\frac{|H|}{|M|}|K|=\frac{|H|\cdot|K|}{|H\cap K|}

# 举例

不容易找到两个子群的交不等于 {e}\{e\} 的例子，利用计算机程序可找到如下的例子：U(33)={1,2,4,5,7,8,10,13,14,16,17,19,20,23,25,26,28,29,31,32}U(33)=\{1,2,4,5,7,8,10,13,14,16,17,19,20,23,25,26,28,29,31,32\}。

  • 子群 {1,2,4,8,16,17,25,29,31,32}\{1,2,4,8,16,17,25,29,31,32\} 是循环子群，生成元为：2,8,17,292,8,17,29 ；
  • 子群 {1,4,5,14,16,20,23,25,26,31}\{1,4,5,14,16,20,23,25,26,31\} 是循环子群，生成元为：5,14,20,265,14,20,26 ；

上述两个子群交集为 {1,4,16,25,31}\{1,4,16,25,31\} ；

# 西罗定理

可了解，不考

GG 是 nn 阶循环群，aa 是生成元。对于 nn 的每个正因子 kk , 有且仅有一个 kk 阶循环子群。并且由 anka^{\frac{n}{k}} 生成.