前言

 准备学习密码学，想在此之前先学习一下群论、数论和离散数学（这个不一定），在本文中，先学习一下群论。

***注意：***下面的*不是乘法运算，而是一个二元运算符，用'*'表示而已。

  • nemean的油管视频
  • 上述视频的翻译，B站

教程未完待续。。。

第一章 基础

第1节 定义

 什么是一个群，群有着如下四个性质。定义一个非空集合G，与一个运算*，记为(G,*)

  • 封闭性：∀a,b∈G,a∗b∈G\forall a,b \in G, a*b\in G，a与b的运算，也属于G。满足这条，则左单位元=右单位元=单位元
  • 结合律：∀a,b,c∈G,a∗(b∗c)=(a∗b)∗c\forall a,b,c \in G, a*(b*c)=(a*b)*c。满足这条，则左逆元=右逆元=逆元
  • 单位元：∃e∈G,∀a∈G,a∗e=e∗a=a\exist e \in G, \forall a \in G, a*e=e*a=a，如果只有一边满足，则称为左单位元或者右单位元
  • 逆元：∀a∈G,则∃b∈G,a∗b=b∗a=e\forall a \in G, 则\exist b \in G, a*b = b*a =e，e为单元元，如果只有一边满足，则称为左逆元或者右逆元，逆元可以用来做逆运算，如加法减法，乘法除法。记a的逆元为：a−1a^{-1}

下面举一个群论的例子，(Z,+)，整数集和加法运算。

  • 封闭性：∀a,b∈Z,a+b∈Z\forall a, b \in Z, a+b\in Z，显然成立的
  • 结合律：∀a,b,c∈Z,a+(b+c)=(a+b)+c\forall a, b, c \in Z, a+(b+c)=(a+b)+c，也是显然成立的
  • 单位元：0∈Z,∀a∈Z,a+0=0+a=a0\in Z, \forall a \in Z,a+0=0+a=a，加法运算中，0就是单位元
  • 逆元：∀a∈Z,−a∈Z,a+(−a)=(−a)+a=0\forall a \in Z, -a\in Z, a+(-a) = (-a)+a = 0，存在逆元，逆元进行运算就是单位元0。

除此之外，非0有理数和乘法，这个也是一个群。

第2节 分类

  • 有限群：G是有限集，称G里元素个数为群G的“阶”，记为|G|。
  • 无限群：G是无限集，群G的“阶”为无限阶。

第二章 定理

  • 群的单位元是唯一的，证明如下

    假设存在e和e’两个单位元，且e≠e’，那么，e*e’ = e = e’，矛盾

    • 群里只有一个元素，称为“平凡群”。唯一元素只能是单位元

  • 每个元素只有唯一的逆元

    假设b，c为a的两个逆元，那么b=b*e = b*(a*c) = (b*a)*c = e*c = c

  • 消去律：a*b=a*c，那么b=c

    a∗b=a∗c  ⇒  a−1∗a∗b=a−1∗a∗c  ⇒  e∗b=e∗c  ⇒  b=ca*b = a*c\ \ \Rightarrow\ \ a^{-1} *a*b = a^{-1}*a*c\ \ \Rightarrow\ \ e*b=e*c\ \ \Rightarrow\ \ b=c

  • a∗x=ba*x=b，唯一解 x∈Gx\in G

    a∗x=b  ⇒  x=a−1∗b∈Ga*x = b \ \ \Rightarrow \ \ x=a^{-1}*b\in G

  • (a∗b)−1=b−1∗a−1(a*b)^{-1} = b^{-1}*a^{-1}

    (a∗b)∗(b−1∗a−1)  ⇒  a∗(b∗b−1)∗a−1  ⇒  e(a*b)*(b^{-1}*a^{-1}) \ \ \Rightarrow \ \ a*(b*b^{-1})*a^{-1}\ \ \Rightarrow\ \ e

  • (a−1)−1=a(a^{-1})^{-1} = a

    (a−1)−1=a  ⇐  (a−1)−1∗a−1=a∗a−1  ⇐  e=e(a^{-1})^{-1} = a\ \ \Leftarrow\ \ (a^{-1})^{-1} * a^{-1}=a*a^{-1}\ \ \Leftarrow \ \ e=e

  • 一种记法：at=a∗a∗a∗...∗aa^t=a*a*a*...*a，注意，a是元素，t是整数。元素不等于整数，元素是一个抽象概念。

  • 一种记法：a−t=a−1∗a−1∗...∗a−1a^{-t}=a^{-1}*a^{-1}*...*a^{-1}，注意同上

  • (at)m=(a∗a∗...∗a)∗(a∗a∗...∗a)∗...∗(a∗a∗...∗a)=at×m(a^t)^m = (a*a*...*a)*(a*a*...*a)*...*(a*a*...*a) = a^{t\times m}，这里×表示乘法

  • at∗am=a∗a∗...∗a  ∗  a∗a∗a∗...∗a=at+ma^t*a^m = a*a*...*a\ \ *\ \ a*a*a*...*a = a^{t+m} ，这里+表示加法

  • (a−1)t=a−1∗a−1∗...∗a−1=(a∗a∗...∗a)−1=(at)−1=a−t(a^{-1})^t = a^{-1}*a^{-1}*...*a^{-1} = (a*a*...*a)^{-1} = (a^t)^{-1}=a^{-t}

第三章 阿贝尔群

第1节 定义

除了第一章第1节之外的定义，阿贝尔群还需要满足交换律

  • ∀a,b∈G,a∗b=b∗a\forall a,b\in G, a*b=b*a

第2节 定理

  • 群G是阿贝尔群，当且仅当∀a,b∈G,有(a∗b)2=a2∗b2\forall a,b\in G, 有 (a*b)^2=a^2*b^2
  • (a∗b)t=a∗b∗a∗b∗...∗a∗b=a∗a∗a...∗a∗b∗b∗...∗b=at∗bt(a*b)^t = a*b*a*b*...*a*b = a*a*a...*a * b*b*...*b = a^t*b^t

第四章 子群

第1节 定义

设(G, *)为一个群，H是G的非空子集，如果(H,*)是一个群，则称(H,*)为(G,*)的子群。

第2节 定理

假设群H是群G的子群

  • 两群的单位元相等

    对于 a∈Ha\in H，那么有e′∗a=a=e∗a  ⇒  e′=ee'*a=a=e*a\ \ \Rightarrow\ \ e'=e，两群单位元相等。

  • a∈H,则a−1∈Ha\in H,则 a^{-1}\in H

第3节 判断子群

一、H是G的非空子集，∀a,b∈H,则a∗b−1∈H\forall a, b\in H, 则 a*b^{-1} \in H，则H是G的子群。如何证明呢？

a,b∈H,b−1∈H⇒a∗b−1∈Ha,b\in H, b^{-1}\in H\Rightarrow a*b^{-1}\in H

（1）证明单位元，b=a,a∗b−1=a∗a−1=eb=a,a*b^{-1} = a*a^{-1}=e，存在单位元

（2）证明封闭性，a,c∈H,则c−1∈H,那么a∗c=a∗(c−1)−1∈H，其中把c−1看作b就知道了a,c\in H,则c^{-1}\in H,那么a*c = a*(c^{-1})^{-1}\in H，其中把c^{-1}看作b就知道了

（3）剩下的性质，由于群G是一个群，则可以证明

二、H是G的非空子集，如果H是有限集，而其G的运算*在H上满足封闭性，则H是G的子群。（H是有限集、封闭，则是子群）

第五章 陪集及扩展

第1节 陪集

H是群G的子群，a∈Ga\in G，则aH:={a∗h∣h∈H}aH := \{a*h|h\in H \}，称为H关于a在G中的左陪集。同理，Ha:={h∗a∣h∈H}Ha:=\{h*a | h \in H\}，称为右陪集。对于运算符合交换律，则左右陪集应该是相等的，下面只讨论陪集。由群G中元素a与子群H中每个元素进行二元运算*之后构成的陪集记为[a]H[a]_H。下面是一个陪集的例子。

例子：

 所有偶数和加法可以构成一个群，记为O，但是所有奇数和加法没法构成群（可以由集合四大性质去证明看）。但是将O中所有元素加1，构成集合 [O]1[O]_1，也就是奇数集合。那么这个集合称为陪集。

第2节 陪集的性质

接下来，讨论一下陪集有些什么性质。

  • a∈[a]Ha\in [a]_H；证明：e∈H⇒e∗a∈H⇒a∈He \in H \Rightarrow e*a\in H\Rightarrow a\in H。这是因为对子群H中的单位元与a做一次运算还是a，陪集的定义也是子群中的所有元素与a做一次运算的集合。

  • [e]H[e]_H称为平凡陪集，子群本身也是陪集，是子群H中的所有元素与群G中的e做一次运算得到的集合，其就是子群H的集合。（e为单位元）。

  • a∈H⇔[a]H=Ha\in H \Leftrightarrow [a]_H = H。

    必要性：a∗e∈[a]H=H⇒a∈Ha*e\in [a]_H=H\quad\Rightarrow\quad a\in H

    充分性：

    第一，∀b∈H,a∈H⇒a∗b∈H⇒[a]H⊆H\forall b \in H, a\in H\quad\Rightarrow\quad a*b\in H\quad\Rightarrow\quad [a]_H \subseteq H，其中，由于b的任意性有a∗b=[a]Ha*b = [a]_H。

    第二，∀b∈H,a∈H⇒a−1∈H,  a−1∗b∈H⇒a∗(a−1∗b)∈[a]H⇒b∈[a]H⇒H⊆[a]H\forall b \in H, a\in H\quad\Rightarrow\quad a^{-1}\in H ,\ \ a^{-1}*b\in H \quad\Rightarrow\quad a*(a^{-1}*b)\in [a]_H\quad\Rightarrow\quad b\in[a]_H \quad\Rightarrow\quad H\subseteq[a]_H，其中，a∗(a−1∗b)a*(a^{-1}*b)是陪集的定义，由于b的任意性，b=H。

  • [a]H=[b]H⇔a−1∗b∈H(b−1∗a∈H)[a]_H = [b]_H \Leftrightarrow a^{-1}*b \in H(b^{-1}*a\in H)

    H={e,h1,h2,...,hn,...}H = \{e, h_1,h_2,...,h_n,...\}，[a]H={a,a∗h1,a∗h2,...,a∗hn,...}[a]_H = \{a, a*h_1,a*h_2,...,a*h_n,...\}，[b]H={b,b∗h1,b∗h2,...,b∗hn,...}[b]_H = \{b, b*h_1,b*h_2,...,b*h_n,...\}。

    [a]H=[b]H⇒b=a∗hm⇒a−1∗b=hm∈H[a]_H = [b]_H\quad\Rightarrow\quad b=a*h_m \quad\Rightarrow\quad a^{-1}*b = h_m\in H。这是因为必定有aH里面必定有一个元素等于b

    推论：两个陪集要么相等，要么相交为空

    假如 [a]H∩[b]H≠∅[a]_H \cap [b]_H \neq \varnothing，那么必然有，h1,h2∈H,a∗h1=b∗h2⇒b−1∗a=h2∗h1−1∈H⇒[a]H=[b]Hh_1,h_2\in H,a*h_1 = b*h_2 \quad\Rightarrow\quad b^{-1}*a = h_2*h_1^{-1}\in H\quad\Rightarrow\quad [a]_H = [b]_H。

第3节 拉格朗日定理

不要跟高等数学中学的拉格朗日中值定理搞混，拉格朗日有好多定理。

 若H是有限群G的子群，则H的阶可以整除G的阶。

给出简单的证明：

1.对于子群H，使用有限群中的a1,a2,a3…与子群H构成陪集，对于任意陪集，其都含于G。

2.现在考虑，a1与a2生成的陪集可能重叠吗？答案是不可能的。证明如下：a1≠a2，因为是不同元素。由上一节推论有，[a1]H=[a2]H或者[a1]H∩[a2]H=∅[a1]_H = [a2]_H或者 [a1]_H \cap[a2]_H = \varnothing。

3.由于陪集的阶等于子群的阶，所以最终所有陪集阶与子群阶的和只能为子群的倍数。所有子群与子群的所有陪集可以覆盖群G，那么群G的阶肯定是子群H与其所有陪集阶的和。

第4节 商群

正规子群

如果子群N是群G的正规子群，那么有 ∀n∈N,∀g∈G,gng−1∈N\forall n \in N, \forall g \in G, gng^{-1} \in N。下面介绍正规子群的等价条件

  • gNg−1=N(gN=Ng)gNg^{-1} = N(gN = Ng)
  • gNg−1=NgNg^{-1} = N
  • ∀g,h∈G,gh∈N⇔hg∈N\forall g,h\in G, gh\in N \Leftrightarrow hg\in N

商群

设N是群G的正规子群，定义集合G/N是N在G中所有左陪集的集合，也就是G/N={aN:a∈G}G/N = \{ aN: a\in G\}。对于G/N中的任意两个元素，aN与bN，得到下列乘法关系。

(aN)(bN) = a(Nb)N = abNN = (ab)N