前言

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

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

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

教程未完待续。。。

第一章 基础

第1节 定义

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

  • 封闭性:a,bG,abG\forall a,b \in G, a*b\in G,a与b的运算,也属于G。满足这条,则左单位元=右单位元=单位元
  • 结合律:a,b,cG,a(bc)=(ab)c\forall a,b,c \in G, a*(b*c)=(a*b)*c。满足这条,则左逆元=右逆元=逆元
  • 单位元:eG,aG,ae=ea=a\exist e \in G, \forall a \in G, a*e=e*a=a,如果只有一边满足,则称为左单位元或者右单位元
  • 逆元:aG,bG,ab=ba=e\forall a \in G, 则\exist b \in G, a*b = b*a =e,e为单元元,如果只有一边满足,则称为左逆元或者右逆元,逆元可以用来做逆运算,如加法减法,乘法除法。记a的逆元为:a1a^{-1}

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

  • 封闭性:a,bZ,a+bZ\forall a, b \in Z, a+b\in Z,显然成立的
  • 结合律:a,b,cZ,a+(b+c)=(a+b)+c\forall a, b, c \in Z, a+(b+c)=(a+b)+c,也是显然成立的
  • 单位元:0Z,aZ,a+0=0+a=a0\in Z, \forall a \in Z,a+0=0+a=a,加法运算中,0就是单位元
  • 逆元:aZ,aZ,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

    ab=ac    a1ab=a1ac    eb=ec    b=ca*b = a*c\ \ \Rightarrow\ \ a^{-1} *a*b = a^{-1}*a*c\ \ \Rightarrow\ \ e*b=e*c\ \ \Rightarrow\ \ b=c

  • ax=ba*x=b,唯一解 xGx\in G

    ax=b    x=a1bGa*x = b \ \ \Rightarrow \ \ x=a^{-1}*b\in G

  • (ab)1=b1a1(a*b)^{-1} = b^{-1}*a^{-1}

    (ab)(b1a1)    a(bb1)a1    e(a*b)*(b^{-1}*a^{-1}) \ \ \Rightarrow \ \ a*(b*b^{-1})*a^{-1}\ \ \Rightarrow\ \ e

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

    (a1)1=a    (a1)1a1=aa1    e=e(a^{-1})^{-1} = a\ \ \Leftarrow\ \ (a^{-1})^{-1} * a^{-1}=a*a^{-1}\ \ \Leftarrow \ \ e=e

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

  • 一种记法:at=a1a1...a1a^{-t}=a^{-1}*a^{-1}*...*a^{-1},注意同上

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

  • atam=aa...a    aaa...a=at+ma^t*a^m = a*a*...*a\ \ *\ \ a*a*a*...*a = a^{t+m} ,这里+表示加法

  • (a1)t=a1a1...a1=(aa...a)1=(at)1=at(a^{-1})^t = a^{-1}*a^{-1}*...*a^{-1} = (a*a*...*a)^{-1} = (a^t)^{-1}=a^{-t}

第三章 阿贝尔群

第1节 定义

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

  • a,bG,ab=ba\forall a,b\in G, a*b=b*a

第2节 定理

  • 群G是阿贝尔群,当且仅当a,bG,(ab)2=a2b2\forall a,b\in G, 有 (a*b)^2=a^2*b^2
  • (ab)t=abab...ab=aaa...abb...b=atbt(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的子群

  • 两群的单位元相等

    对于 aHa\in H,那么有ea=a=ea    e=ee'*a=a=e*a\ \ \Rightarrow\ \ e'=e,两群单位元相等。

  • aH,a1Ha\in H,则 a^{-1}\in H

第3节 判断子群

一、H是G的非空子集,a,bH,ab1H\forall a, b\in H, 则 a*b^{-1} \in H,则H是G的子群。如何证明呢?

a,bH,b1Hab1Ha,b\in H, b^{-1}\in H\Rightarrow a*b^{-1}\in H

(1)证明单位元,b=a,ab1=aa1=eb=a,a*b^{-1} = a*a^{-1}=e,存在单位元

(2)证明封闭性,a,cH,c1H,那么ac=a(c1)1H,其中把c1看作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的子群,aGa\in G,则aH:={ahhH}aH := \{a*h|h\in H \},称为H关于a在G中的左陪集。同理,Ha:={hahH}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;证明:eHeaHaHe \in H \Rightarrow e*a\in H\Rightarrow a\in H。这是因为对子群H中的单位元与a做一次运算还是a,陪集的定义也是子群中的所有元素与a做一次运算的集合。

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

  • aH[a]H=Ha\in H \Leftrightarrow [a]_H = H

    必要性:ae[a]H=HaHa*e\in [a]_H=H\quad\Rightarrow\quad a\in H

    充分性:

    第一,bH,aHabH[a]HH\forall b \in H, a\in H\quad\Rightarrow\quad a*b\in H\quad\Rightarrow\quad [a]_H \subseteq H,其中,由于b的任意性有ab=[a]Ha*b = [a]_H

    第二,bH,aHa1H,  a1bHa(a1b)[a]Hb[a]HH[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(a1b)a*(a^{-1}*b)是陪集的定义,由于b的任意性,b=H。

  • [a]H=[b]Ha1bH(b1aH)[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,ah1,ah2,...,ahn,...}[a]_H = \{a, a*h_1,a*h_2,...,a*h_n,...\}[b]H={b,bh1,bh2,...,bhn,...}[b]_H = \{b, b*h_1,b*h_2,...,b*h_n,...\}

    [a]H=[b]Hb=ahma1b=hmH[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,h2H,ah1=bh2b1a=h2h11H[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的正规子群,那么有 nN,gG,gng1N\forall n \in N, \forall g \in G, gng^{-1} \in N。下面介绍正规子群的等价条件

  • gNg1=N(gN=Ng)gNg^{-1} = N(gN = Ng)
  • gNg1=NgNg^{-1} = N
  • g,hG,ghNhgN\forall g,h\in G, gh\in N \Leftrightarrow hg\in N

商群

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

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