抽象代数之群论基础

为了更好地研究密码学，本着“磨刀不误砍柴工”的想法，对本科时学习的《离散数学》进行一个复习。不一样的是，这次直接对抽象代数（特别是其中的群论、环论、域论）进行再次探索。参考书目为Joseph J. Rotman的《Advanced Modern Algebra》以及丘维声的《抽象代数基础》。对于我认为重要的定理，我会记录下来并附加上主观感受，并不会给上详细证明。

这篇博客先主要复习群论，其余之后再说。

单位根

定义：设$n\ge1$是整数，称满足$\zeta^n=1$的复数$\zeta$为$n$次单位根。

定理：每个$n$次单位根等于：

$$e^{2\pi ik/n}=\cos(\frac{2\pi k}{n})+i\sin(\frac{2\pi k}{n})$$

如果将这些复数根画到平面直角坐标系中，会发现这些根正好将单位元分成了$n$份。

定义：如果$\zeta$是一个$n$次单位根，而$d$是最小的正整数使得$\zeta^d=1$，就称$\zeta$是$d$次单位原根。

定理：如果$n$次单位根$\zeta$是$d$次单元原根，则$d|n$。

定义：$d$阶分圆多项式为：

$$\Phi_d(x) = \prod_{1\le i\le d}(x-\zeta_i)$$

这里$\zeta_i$表示$i$次单元原根。

定理：对于每个整数$n\ge1$，

$$x^n-1 = \prod_{d|n}\Phi_d(x)$$

其中$d$遍历$n$的所有因数（特别地，$\Phi_1(x),\Phi_n(x)$也在其中）。

定义：欧拉$\phi$-函数为$n$阶分圆多项式的次数：

$$\phi(n) = \deg(\Phi_n(x))$$

群 基本概念

定义：群是指配置了二元运算$*$的集合$G$，且满足：

1. 结合律成立，即对任何$x,y,z\in G$，有$x*(y*z)=(x*y)*z$。
2. 存在幺元。
3. 每个元素都存在逆元。

如果一个群$G$还满足交换律，那么称$G$为阿贝尔群。

定理：群有如下性质：

1. 消去律成立，如果$x*a=x*b$或$a*x=b*x$，那么$a=b$。
2. 幺元唯一。
3. 每个元素的逆元唯一。
4. 一个元素逆元的逆元，就是它自己。
5. $\forall a,b\in G, \ (ab)^-1=b^{-1}a^{-1}$。

定义：$a$是群$G$中的任意元素，如果对于$k\ge1$有$a^k=e$，那么这样的最小指数成为$a$的阶，如果没有这样的幂存在，称$a$的阶无限。

定理：如果$a\in G$是$n$阶元素，那么$a^m=1$当且仅当$n|m$。

定理：如果一个群是有限的，那么所有元素的阶都有限。

子群和拉格朗日定理

子群

定义：称群$G$的子集$H$为子群，如果

1. 运算在$H$上满足封闭性；
2. $e \in H$；
3. 如果$x\in H$，那么$x^{-1}\in H$。

不难证明，实际上只要满足上述条件的（1）和（3）即可，而对于有限群，只需要满足封闭性即是子群。

子群给我们的启示是，如果一个在集合上的运算很难证明结合律，那么可以考虑证明这个集合是某个群的子群。

一个更简洁的证明子群的的方法：

定理：群$G$ 的子集$H$是子群当且仅当$H$非空，且当$x,y\in H$时，$xy^{-1}\in H$。

定理：若干个子群的交集也是$G$的子群。

循环群，阶

定义：如果$G$是群，且$a\in G$，记：

$$\left<a\right>=\{a^n|n\in \Z\}$$

为$G$的由$a$生成的循环子群。如果存在$a\in G$使得$\left< a\right>=G$，则称$G$为循环群，$a$为$G$的生成元。

特别地，$\left<\varnothing\right>={1}$。

定理：如果$G=\left<a\right>$是$n$阶循环群，那么$a^k$是$G$的生成元当且仅当$gcd(k,n)=1$；并且根据欧拉函数的定义，$G$的生成元个数为$\phi(n)$。

定理：如果$G$是有限群，那么$a\in G$的阶为 $|\left<a\right>|$。

定理：素数阶的群均为循环群。

定理：如果$X$是群$G$的子集，则存在包含$X$的最小子群，记作$\left<X\right>$（由$X$生成的子群），最小指的是对于每个子群，$X$都为其子群。

拉格朗日定理

定义：如果$H$是$G$的子群且$a\in G$，则$G$的子集$aH$称作陪集，这里

$$aH = \{ah|h\in H\}$$

上述所记的是左陪集，如果使用右乘，则为右陪集，左陪集和右陪集一般是不同的。另外，在一般情况下陪集不是子群。

定理：如果$H$是$G$的子群，并设$a,b\in G$，则有

1. $aH=bH$当且仅当$b^{-1}a\in H$，特别地，$aH=H$当且仅当$a\in H$;
2. 如果$aH\cap bH\neq\varnothing$，则$aH=bH$;
3. 对一切$a\in G$，$|aH|=|H|$。

作为（1）的对偶，$Ha=Hb$当且仅当$ab^{-1}\in H$。

这个定理告诉我们，陪集要么相等，要么没有交集，更进一步说，陪集就是$G$上定义的等价关系$R:aRb\Leftrightarrow b^{-1}a\in H$所诱导出的等价类。

定理（拉格朗日定理）：如果$H$是有限群$G$的子群，则$|H|$是$|G|$的因数。

反之不一定成立，并不是对于所有$|G|$的因数，都存在一个子群阶数与其相等。

定理：如果 $G$是有限群，那么$a\in G$的阶是$|G|$的因数。

因为$a$的阶为$|\left< a\right>|$。回顾上一节的定理：“如果$G$是有限群，那么$a\in G$的阶为 $|\left<a\right>|$。”

定理：如果 $G$是有限群，那么对于$a\in G$，$a^{|G|}=1$。

利用这个定理可以证明费马小定理。

定义：$G$中子群$H$的指数是指$G$中$H$的左（右）陪集个数，记作$[G:H]$：

$$[G:H]=|G|/|H|$$

定义：对于模 $m$剩余类$I_m$，定义$U(I_m)$为：

$$U(I_m) = \{[r]\in I_m|\gcd(r,m)=1\}$$

它是阶为$\phi(m)$的乘法群。特别地，如果$p$是素数，则$U(I_p)=I_p^\times$是阶为$p-1$的乘法群，$I_p^{\times}$为$I_p$的非零元素的集合。

定理（费马小定理）：

$$a^p\equiv a\mod p\\ a^{p-1}\equiv 1 \mod p$$

把$I_m^{\times}$看成一个乘法群，套用拉格朗日定理即可。

定理（欧拉定理）：如果$\gcd(r,m)=1$，则

$$r^{\phi(m)}\equiv 1 \mod m$$

欧拉定理是对费马小定理的推广，实质上，是在$U(I_m)$上套用拉格朗日定理得到的。

同态

定义：如果$(G,*),(H,\circ)$是群，且满足下式，则函数$f:G\rarr H$称为同态：

$$f(x*y) = f(x)\circ f(y)$$

如果这个函数是双射，则称为同构，记为$G\cong H$。这里同态和同构都是指$f$这个函数，而$f$的定义域和值域又与$G,H$有关。

定理：群同态下，幺元、逆元、阶都可以保持。

定义：$f:G\rarr H$是同态，则

$$\ker f = \{x\in G|f(x)=1\}\\ \textrm{im} \ f=\{h\in H|\exist x\in G\rarr h=f(x)\}$$

$\ker f$ 称作$f$的核，$\textrm{im}\ f$称为$f$的象。

定理：设$f:G\rarr H$是同态，

1. $\ker f$是$G$的子群，$im \ f$是$H$的子群；
2. 如果$x\in \ker f,a\in G$，则$axa^{-1}\in \ker f$；
3. $f$是单射当且仅当$\ker f={1}$。

定义：如果$\forall k\in K,g\in G\rarr gkg^{-1}\in K$，这称$G$的子群$K$为正规子群，记为$K\triangleleft G$。

显然，同态的核恒为正规子群。

又不难发现，阿贝尔群的每个子群都是正规子群，因为$\forall k\in K,g\in G, gkg^{-1}=kgg^{-1}=k\in K$。反之不一定成立。

定义：如果$G$是群，$a\in G$，则形如

$$gag^{-1}$$

的$G$中任一元素称为$a$的一个共轭元素。

在线性代数中，两个相似的矩阵互为共轭元素，即$B = PAP^{-1}$。

定义：如果$G$是群，$g\in G$，则定义共轭$\gamma_g: G\rarr G$为对一切$a\in G$：

$$\gamma_g (a)= gag^{-1}$$

定理：共轭$\gamma_a(g)$是同构。

这个比较显而易见，如果你已经理解“群的每次运算实际上都是一次置换（从运算表理解）”

定理：共轭元素有相同的阶。

定理：如果$H$是群$G$中指数为2的子群，则对每个$g\in G,g^2\in H$。

定理：如果$H$是群$G$中指数为2的子群，则$H$是$G$的正规子群。

定义：GL(2,\C)中下列元素

$$Q = \{I,A,A^2,A^3,B,BA,BA^2,BA^3\}\\ A = \begin{bmatrix} 0 & 1\\ -1 & 0 \end{bmatrix}, B=\begin{bmatrix} 0 & i\\ -i & 0 \end{bmatrix}$$

组成的8阶群$Q$称为四元数群，其中$I$是单位矩阵。

定义：每个子群都是正规子群的非阿贝尔有限群叫做哈密顿群。

定理：每个哈密顿群形为$Q\times A$，其中$A$是一个没有四阶元素的阿贝尔群。

商群

定义：群G的非空子集的集合上的一种运算：

$$XY = \{xy|x\in X, y\in Y\}$$

定理：群$G$的子群$K$是正规子群，当且仅当对于每个$g\in G$，

$$gK=Kg$$

由此，正规子群的左陪集也是右陪集。

说服一下自己，元素和子群的乘积也可以用消去律，这个定理即可得证。

定理：

1. 通过$H$和$K$都是群$G$的子群，且其中之一是正规子群，则$HK$是$G$的子群，且$HK=KH$。
2. 如果$H$和$K$都是群$G$的正规子群，则$HK$也是正规子群。

同上面一样，把子群之间的乘积也看成一种群运算，满足消去律，则这个定理可以被接受。

定义：商群$G/K$的定义如下：

$$G/K = \{gK|g\in G\}$$

也即所有左陪集所组成的集合。

其阶$|G/K|=[G:K]=|G|/|K|$。

定理：如果$K$是正规子群，则对一切$a,b\in G$，

$$aKbK = abK$$

且$G/K$在此运算下是群。

此定理可以用子群之间乘法“结合律”以及“左右陪集相等”来证明。

直观地看，正规子群的运算有传递性。另外，陪集之间的运算并不依赖代表元。

定理：每个正规子群$K\triangleleft G$都是某个同态的核。

定义：自然映射$\pi:G\rarr G/K$为$\pi(a)=aK$。

用此公式可以把上上条定理写为：$\pi(a)\pi(b)=\pi(ab)$，不难得知$\pi$是满同态。

定理（第一同构定理）：如果$f:G\rarr H$是同态，则

$$\ker f\triangleleft G\\ G/\ker f \cong \textrm{im}\ f$$

这个定理讲了两件事，一是每个同态的核都是一个正规子群（这个在之前就提到过）；二是$G$对这个正规子群的商群与$f$的象同构。更具体地说，$G/\ker f$与$\textrm{im} f$的同构是$\phi:aK\mapsto f(a)$，而下图中的$\pi：G\rarr G/K$为$\pi:a\mapsto aK$。

商群$R/Z$是什么，根据第一同构定理稍加证明，可以得到 $R/Z\cong S^1$，这里$S^1$是圆群。

定理（乘积公式）：如果$H,K$都是有限群$G$的子群，则：

$$|HK||H\cap K| = |H||K|$$

定理（第二同构定理）：如果$H,K$是群$G$的子群且满足$H\triangleleft G$，则$HK$是子群，$H\cap K\triangleleft K$，且

$$K/(H\cap K)\cong HK/H$$

定理（第三同构定理）：如果$H,K$是群$G$的正规子群且$K\le H$，则$H/K\triangleleft G/K$且

$$(G/K)(H/K) \cong G/H$$

定理：如果$G$是有限阿贝尔群，且$d$是$|G|$的因数，则$G$含有$d$阶子群。

之前提到过对于一般的群来说，"$d$是$|G|$的因数，则$G$含有$d$阶子群"命题不成立，但是对于有限阿贝尔群是成立的。

定义：定义群之间的直积运算为

$$H\times K =\{(hh\prime,kk\prime)|h,h' \in H,k,k' \in K\}$$

容易验证直积是群。

定理：如果$m$和$n$互素，则

$$I_{mn}\cong I_m\times I_n$$

定理：如果$G$是群，且$a,b$可交换，它们的阶分别为$m,n$，如果$(m,n)=1$，则$ab$的阶为$mn$。

定理：

1. 如果$(m,n)=1$，则$\phi(mn)=\phi(m)\phi(n)$。
2. 如果$p$是素数，则$\phi(p^e)=p^e-p^{e-1}=p^e(1-\frac{1}{p})$。
3. 如果$n=p_1^{e_1}\cdots p_t^{e_t}$是质因数分解，则$\phi(n)=n(1-\frac{1}{p_1})\cdots(1-\frac{1}{p_t})$。

其他结论

剩余内容有些过于深入了，这里就只摘取可能与密码学有关的内容（有限群等）。

• （柯西定理）如果$G$是有限群，它的阶被素数$p$整除，则$G$含有$p$阶元素。
• 若$p$为素数，则每个阶为$p^2$的群都是阿贝尔群。