二元运算和群

二元运算

在一个集合S上的二元运算是一个函数
::: align-center
S*S\to S

:::
对x,y\in S，我们把*(x,y)记作x*y，它在集合S上封闭，例如对整数集\mathbb{Z}，加法是二元运算，但对自然数集，减法就不是二元运算（因为结果有可能不在自然数集内），所以(\mathbb{Z}, +)是二元运算，(\mathbb{N},-)不是

结合律和交换律

在S上的一个二元运算*

1. 若对任意的a,b,c\in S，a*(bc)=(ab)*c，则其是可结合的
2. 若对任意的a,b\in S，ab=ba，则其是可交换的

例如(\mathbb{Z}, +)是既可结合又可交换的，而矩阵乘法可结合但不可交换

再举例x\circ y=(1+x)(1+y)-1对于x,y实数，轮换x,y结果不变，而计算(x\circ y)\circ z和x\circ (y\circ z)其结果均是相同的，因此(\mathbb{R},\circ)可交换可结合

单位元和逆元的直觉

现在可以引入单位元的逆元的粗略定义

先找是否有一个e，使得a\circ e=e\circ a=a——这就是单位元，也就是说，对每一个元素a，都可以把e放在左边或右边，结果都不变的

再问在存在单位元的前提下，是否每个元素a都有元素b使得a\circ b=b\circ a=e——这就是逆元

幺半群

非空集合M对于二元运算*是一个幺半群（Monoid），如果：

1. *结合
2. 存在元素e\in M使得对所有a\in M,a*e=e*a=a，则这个e叫做单位元（Identity Element），而且此单位元唯一

证明唯一性：假设有两个个单位元e_1,e_2，对e_2作为元素aa带入单位元e_1的定义，有e_2\circ e_1=e_1\circ e_2=e_1，再将e_1作为a带入单位元e_2的定义，有e_1\circ e_2=e_2\circ e_1=e_2，选择第一个式子的e_1\circ e_2=e_1和第二个式子的e_1\circ e_2=e_2，可立即得e_1=e_2

例如(\mathbb{Z},+)是一个幺半群，因为整数集上的加法结合，且整数集存在单位元0；(\mathbb{Z},\cdot)是幺半群，它存在单位元1；2x2的实矩阵乘法也是幺半群，单位元是单位矩阵

群

对一个幺半群(G, *)，当对每个a\in G，存在b\in G使得a*b=b*a=e时，它称为群（Group），这个b叫做a的逆元。结合二元运算和幺半群的定义，得到(G,*)是群的条件为：

1. *对集合S封闭（继承自二元运算）
2. *在集合S内结合（继承自幺半群）
3. 集合S对*有单位元e（继承自幺半群）
4. 集合S的每个元素对*均有逆元（群特有）

这就是群公理

交不交换并不影响是不是群，但是如果能交换则称为阿贝尔群

举个例子：(\mathbb{Z},+)是群，因为：

1. 加法对整数集封闭
2. 加法对于整数集结合
3. 对于整数加法，有单位元0（不是1），因为a+0=0+a=a
4. 对于一个整数a，总有其逆元-a，使得a+(-a)=(-a)+a等于单位元0

因为还可交换，这还是一个阿贝尔群

而(\mathbb{Z}, \cdot)并不是群，因为

1. 乘法对整数集封闭
2. 乘法对整数集结合
3. 对于整数乘法，有单位元1，因为a\cdot 1 = 1\cdot a = a
4. 对于一个整数a，要使得经过乘法运算后得到单位元1，其逆元就不一定还在整数集内了（事实上，只有\pm 1的逆元存在，其他整数的逆元全部是分数）
5. 故整数集对于乘法并不是一个群，但若扩展到非零有理数集上的乘法就可以了

同理，2x2可逆矩阵对于矩阵乘法运算也是一个群，但不是一个阿贝尔群，因为矩阵乘法不交换

同余和环

模下的同余

给定正整数n，对整数a,b，我们说
::: align-center
a \equiv b\pmod{n}

:::
当且仅当n\mid(a-b)，也就是a-b正好是n的倍数

举个例子，14和2在模12下是同余的，因为14-2\mid 12\Rightarrow14\equiv 2\pmod{12}，-4和2在模6下是同余的，因为-4-2\mid 6\Rightarrow-4\equiv 2\pmod{6}

同余类[a]

模n的同余把整数分成了一个个“类”，在同一个类里的数它们的模n同余都是相等的，所以我们把包含所有与a同余的整数的那一类都记为
::: align-center
[a]=\{a+kn|k\in\mathbb{Z}\}

:::

举个例子，在模6下[2]=\{\cdots,-10,-4,2,8,14,\cdots\}
一句话：在模的世界里，我们不再区分类里的具体哪个数，我们只记这一类本身

整数模n集合

把这些所有的不同的同余“类”收集起来，就是
::: align-center
\mathbb{Z}_n=\{[0],[1],\cdots,[n-1]\}

:::
在\mathbb{Z}_n上，我们这样定义加法和乘法二元运算
::: align-center
\begin{aligned}&[a]+[b]\coloneqq [a+b]\\&[a]\cdot[b]\coloneqq [ab]\end{aligned}

:::
注意右边[]内的加法和乘法是普通整数运算，然后再套一层[]变为同余类，可以证明这是良定义的，这里不证

通常我们会偷懒，去掉[]，但严格来说，这里的每一个元素和上面说的一样，是一“类”

两个重要命题

命题1：整数模n环上的加法是一个群

(\mathbb{Z}_n,+)（模n加法）是一个群

1. 封闭：[a]+[b]依然是一个整数，模n后依然在\mathbb{Z}_n内
2. 结合：([a]+[b])+c\equiv [a]+([b]+[c])\pmod{n}，因为整数加法本就是结合的，故模n加法“继承了”整数加法的结合性
3. 单位元：有单位元0，[a]+0=0+[a]\equiv [a]\pmod{n}
4. 逆元：对[a]\in\mathbb{Z}_n，[n-a]也是\mathbb{Z}_n里的元素，且总有[a]+[(n-a)]=[n]\equiv 0\pmod{n}

注意：准确的说，这里的a，b都得套上[]
所以\mathbb{Z}_n对于模n加法是群，而且是阿贝尔群

类似地也可以得到此集合上的乘法是一个有单位元1的幺半群，而且满足对加法的分配律，自此我们称它是一个环（Ring）
::: align-center
环（粗略定义）：一个集合上同时给出加法和乘法，其中对加法形成阿贝尔群，对乘法是有单位元的幺半群，且满足分配律

:::

命题2：模n整数环的单位群在模n乘法下是群

首先介绍集合U_n，在一个有单位元1的环里，我们关心哪些元素“在乘法下可逆”，定义
::: align-center
若环R中有元素u，存在v\in R满足u\cdot v=v\cdot u=1

:::
那么u叫做一个单位（Unit），v是它的乘法逆元，所有单位组成的集合记作U(R)，叫做单位群（Unit Group），特别地，在R=\mathbb{Z}_n时，我们把这个集合叫做U_n
::: align-center
U_n=\{[a]\in \mathbb{Z}_n, \gcd(a,n)=1\}

:::
相信看到这里的读者可能会疑问为何“单位”和gcd为1有关？因为我们关心的是哪一些[a]有乘法逆元，如此

1. [a]在\mathbb{Z}_n里有单位
2. 等价于存在整数x使得ax=1\pmod{n}
3. 由模n同余定义等价于n\mid ax-1
4. 整理得ax+ny=1对于整数x,y
5. 由贝祖恒等式得到gcd(a,n)=1，然后由贝祖形式还能得到a,n互素

现在证明U_n对模n乘法是一个群，按照群公理，需要证明：封闭、结合、有单位元，有逆元。这里我们再加一个U_n非空的证明
（1）非空：因为gcd(1,n)=1，所以[1]\in U_n，U_n至少有一个元素，故不是空集
（2）模n乘法封闭：即证明[a],[b]\in U_n\Rightarrow [a\cdot b]\in U_n，这等价于证明gcd(a,n)=1,gcd(b,n)=1\Rightarrow gcd(ab,n)=1
我们假设gcd(ab,n)\ne 1，那么由贝祖形式得到ab和n不是互素的，那么由算术基本定理，当gcd(ab,n)>1即二者不互素时那就肯定存在一个素数p，有p\mid ab且p\mid n，而由欧几里得引理知，若p为素数且p\mid ab，则p\mid a或p\mid b，所以

1. p\mid a，而又有p\mid n，这说明p是a和n的公因子，gcd(a,n)> 1，与我们的假设gcd(a,n)=1矛盾
2. 同理对于b也可得gcd(b,n)> 1，矛盾

故gcd(ab,n)=1，模n乘法在U_n上封闭
（3）结合，因为整数乘法本就是封闭的，取模后依然继承了这个性质，故在U_n上的模乘法依然结合
（4）单位元：在整数里1是乘法单位元，在\mathbb{Z}_n里，对任意[a]，有
::: align-center
[a]\cdot [1]=[a\cdot 1]=[a], [1]\cdot [a] = [1\cdot a] = [a]

:::
故存在单位元[1]
（5）逆元
我们取任意[a]\in U_n，即任意的[a]\in U_n,gcd(a,n)=1，由贝祖恒等式得到xa+yn=1这等价于ax=1\pmod{n}，同时也可以由这条等式看到gcd(x,n)=1，即[x]\in U_n，所以对于任意的[a]\in U_n均有逆元[x]

综上，可证明(U_n,\times \bmod n)是一个群，同时读者可能也注意到了U_n上的模n乘法是可交换的，故其还是一个阿贝尔群

什么时候整数模n环对于模n乘法是群？

现在我们来探讨什么时候\mathbb{Z}_n在模n乘法下是群，即n满足什么条件的时候\mathbb{Z}_n=U_n，事实上当\mathbb{Z}_n去掉0，即\mathbb{Z}_n^*，且当n为素数时该条件满足

首先证明充分性，若(\mathbb{Z}_n^*, \times\bmod{n})是群，如果n不是素数，则n要么是1要么是合数，若n=1，任何整数模n均为0，而0不在\mathbb{Z}_n^*里，故实际上现在\mathbb{Z}_n是空集，因为缺少单位元和逆元它什么都不是；若n是合数，那么有n=st且1，s,t是整数所以肯定属于\mathbb{Z}_n^*，但st=0\pmod{n}，0却不在\mathbb{Z}_n^*里（是的，我们之所以去掉0，就是为了在这里用的），所以模n乘法在\mathbb{Z}_n上压根不封闭，更别说群了，与题干矛盾，故推出n只能是素数

再证必要性，若n是素数，1,\cdots, n-1都与n互素，即满足此时任意的[a]\in\mathbb{Z}_n^*，总有gcd(a,n)=1，由U_n的定义这时候\mathbb{Z}_n=U_n，而我们已经在前面证明了U_n在模n乘法下是群了

需要注意的是，我们把0从\mathbb{Z}_n里面去掉得到了\mathbb{Z}_n^*并证明了其对于模n乘法是一个群（还是个阿贝尔群），但是\mathbb{Z}_n^*上的模n加法却退化到不是一个群了，甚至连幺半群都不是，因为我们失去了“存在单位元0”这个条件

群的一般性质

消去律与逆元唯一

在群G里，若ba=ca（即右边同乘一个a），则b=c；同理若ab=ac，也有b=c

证明：
在群里因为a有逆元a'（也常写为a^{-1}），满足aa'=a'a=e，若ba=ca，两边同右乘a'，又因为群内的二元运算均满足结合律，有b(aa')=c(aa')\Rightarrow b=c即可。

因为ab=e=ac，左乘a'可消去a得b=c，故也可以得一个元素不可能有两个不同的逆元

群中乘法的双射性质

设群是(G,*)，固定一个元素g\in G，看函数
::: align-center
L(G):G\to G,\quad L_g(x)=g*x

:::
这叫做“左乘g”，在群里，L_g是双射

• 单射：如果g*x=g*y，用左消去律得到x=y，所以不同的x不会映射到同一个结果上
• 满射：给定任意h\in G，因为群中元素的逆元均存在，故令x=g^{-1}*h，就有gx=g(g^{-1}h)=(gg^{-1})h=h，所以每个元素都能被某个x映到

同理得右乘也是双射

乘积的逆元公式

对任意a,b\in G，有(ab)^{-1}=b^{-1}a^{-1}

证明：
只需要证b^{-1}a^{-1}同时是ab的左逆和右逆即可，易得

幂与循环群

幂

先定义幂

• g^n(n\in\mathbb{N})表示g连乘n次
• 约定g^0=e
• 对负整数n，定义g^n=(g^{-n})^{-1}

定义对任意g\in G，m,n\in\mathbb{Z}，有：
::: align-center
g^mg^n=g^{m+n}

:::
因为群内保证了结合律和逆元的存在，所以负指数也能一致的运算，同底数幂相乘指数相加在群里仍成立

群的阶与Cayley表

定义

群的阶|G|（或o(G)）就是当群G为有限群时元素的个数（或类的个数，还记得\mathbb{Z}_n吗？）

群的元素g的阶o(g)定义为使得
::: align-center
g^n=e

:::
的最小正整数n

Cayle表就是把所有g*h的结果列成乘法表，行列标g,h，格子填g*h

三元群的Cayley表

给出问题：
::: align-center
群只有三个元素e,a,b，要写出Cayley表

:::
由于e是单位元，所以表的第一行第一列立即确定

*	e	a	b
e	e	a	b
a	a
b	b

剩下的要填a*a,a*b,b*a,b*b，但群只有三个元素，且每行每列都必须是一个排列（因为群的乘法是双射，x\to g*x是一一对应，每个元素出现一次，不会重复），同理每一列也不能重复

下面看a的这一行，a*a不可能是a，否则与第一列重复，也不能是e否则第三列只能填b与上面的另一个b重复，故a*a=b，a*b=e

同理第三行填b,e,a，于是得

*	e	a	b
e	e	a	b
a	a	b	e
b	b	e	a

检验：每一行每一列均不重复，Cayley表正确，而且唯一

同时查表得到aa=b,ba=e，于是a^3=e，bb=a,ab=e，于是b^3=e，这个三阶群内每个非单位元都是三阶的

非单位元自逆的四元群的Cayley表

设G=\{a,b,c,e\}是群，e为单位元，且有：
::: align-center
a^2=b^2=c^2=e

:::
这意味着a^{-1}=a,b^{-1}=b,c^{-1}=c，即每个元素都是自逆的，现在考虑它的Cayley表

先考虑ab是谁

• 若ab=e，我们右乘b得到abb=eb\Rightarrow abb^{-1}=eb\Rightarrow a=b矛盾，左乘a也行
• 若ab=a，左乘a得到aab=e\Rightarrow b=e矛盾
• 若ab=b，右乘b得到abb=e\Rightarrow a=e矛盾
• 故只有可能是ab=c

类似地可得ac=b，并对称的得ba=c,bc=a;ca=b,cb=a，于是得到

*	e	a	b	c
e	e	a	b	c
a	a	e	c	b
b	b	c	e	a
c	c	b	a	e

检查通过，同时由题干可知a^2=b^2=c^2=e，那么这个四阶群的每个非单位元都是二阶的

补充一下：在群的阶为4的情形下，本质只有两类群

1. Klein四元群V_4（即三个非单位元全是二阶）
2. 循环群\mathbb{Z}_4，见下

群的同态与同构

群的同态（Homomorphism）

设(G,\circ)、(H,*)是两个群。一个函数\psi:G\to H称为同态，如果对任意a,b\in G都有：
::: align-center
\psi(a\circ b)=\psi(a)*\psi(b)

:::
直觉：现在G里算再映射=先映射再在H里算

群的同构（Isomorphism）

如果一个同态\psi同时还是一个双射，那么它就叫做一个同构，记作：
::: align-center
G\cong H

:::
直觉：俩群“结构”完全一样，只是元素名字不同

同态和同构的性质

设\psi: G\to H是同构，则有

1. \psi(e_G)=e_H
2. 对任意n\in\mathbb{Z},a\in G有\psi(a^n)=\psi^n(a)
3. \psi(a)\psi(b)=\psi(b)\psi(a)当且仅当ab=ba
4. G为阿贝尔群等价于H为阿贝尔群（3的整体版本）
5. \psi^{-1}:H\to G也是同构（同构的逆依然是同构）
6. 若G有限，则H有限且两群的阶|G|=|H|

证：
（1）由于G是群，假设G上的二元运算是\cdot，故有e_G\cdot e_G=e_G，两边套上\psi得到
::: align-center
\psi(e_G\cdot e_G)=\psi(e_G)

:::
此时对左边使用同态的性质，假设H上的运算也是\cdot得到：
::: align-center
\psi(e_G)\psi(e_G)=\psi(e_G)

:::
因为H是群，所以H内的\psi(e_G)必然有逆元\psi^{-1}(e_G)，等式两边左乘即可得证
（2）
先做n\ge 0的归纳

1. n=0时，a^0=e_G，所以显然有\psi(a^0)=\psi(e_G)=e_H=(\psi(a))^0
2. n=1时显然成立
3. 若\psi(a^n)=(\psi(a))^n成立，则\psi(a^{n+1})=\psi(a^na)=\psi(a^n)\psi(a)，由归纳假设得到结果

再证负整数时的情况，首先证明\psi(a^{-1})=\psi(a)^{-1}，考虑到等式右侧有一个\psi(a)^{-1}，我们考虑两式同时左（或右）运算\psi(a)得到\psi(a)\psi(a^{-1})=e_H，所以只要证等式左边的结果为e_H即可，而由于同态的性质\psi(a)\psi(a^{-1})=\psi(aa^{-1})=\psi(e_G)=e_H，得证

之后开始证明，若n<0，我们令n=-k，那么此时k>0，再加上我们刚才上面证明的结论之后的过程就和非负整数时没有区别了

（1）（2）两条结论只需要\psi是同态就够了

（3）
若ab=ba，则两边套\psi得到
::: align-center
\begin{aligned}&\psi(ab)=\psi(a)\psi(b)\\&\psi(ba)=\psi(b)\psi(a)\end{aligned}

:::
可知等式左侧在ab=ba时是相等的，带入函数\psi值依然相等的结论此时由\psi是同构保证（准确的说，是同构中双射条件中的单射保证），那么右侧相等，反之亦然
（4）
h_1h_2=\psi(g_1)\psi(g_2)=\psi(g_1g_2)，h_1和h_2一定对应着某个\psi(g_1)和\psi(g_2)由\psi是同构保证（准确的说，是同构中双射条件中的满射保证）此时\psi内套着的部分属于群G，如果群G是阿贝尔群，则g_1g_2=g_2g_1，再使用同态的性质拆开即可得到：
::: align-center
\psi(g_1g_2)=\psi(g_2g_1)=\psi(g_2)\psi(g_1)=h_2h_1

:::
得证

需要注意的是，此条件是充分不必要的，反之若H阿贝尔，则G并不一定阿贝尔
（5）
若\psi同构，则其一定是双射，那么它就存在反函数\psi^{-1}，且\psi^{-1}一定也是双射。要证明\psi^{-1}同构，只需要证其同态

任取h_1,h_2\in H，因为\psi^{-1}满射，故一定存在g_1,g_2\in G使得g_1=\psi^{-1}(h_1),g_2=\psi^{-1}(h_2)，则有
::: align-center
\psi^{-1}(h_1h_2)=\psi^{-1}(\psi(g_1)\psi(g_2))=\psi^{-1}(\psi(g_1g_2))=g_1g_2=\psi^{-1}(h_1)\psi^{-1}(h_2)

:::
得证
（6）
可直接由\psi是双射（一一对应）说明

子群和中心

为什么需要子群

如果我们随便在群里删元素，剩下的元素在原来该群的二元运算上不一定是群，例如(\mathbb{Z}_6,+)，若删去1,4，则现在群内的元素变为\{0,2,3,5\}，计算2+2\equiv 4\pmod{6}，而4并不在元素内，于是不封闭，现在不是群

子群的定义

H是G的子群（记为H\le G），如果

• H非空
• 在G的同一个运算下，(H,*)本身是群

判断H是否是G的子群，需要重新根据群公理判断封闭+单位元+逆元，运算的结合律不需要判别因为子群自动继承母群的结合律

子群的判别推论

（1）封闭+逆元
设G是群，H是G的非空子集，则H\le G当且仅当对所有x,y\in H有

• x*y\in H
• x^{-1}\in H

说明：
已知H非空，取任意x\in H，若其逆也存在在H理，则单位元e_G=x*x^{-1}也在H里，所以H满足群公理

用法：

1. 确认H非空
2. 证明任意x,y\in H，x*y\in H
3. 证明任意x\in H，x^{-1}\in H

（2）一步法
设G是群，H是G的非空子集，则H\le G当且仅当对所有x,y\in H，x^{-1}y\in H

说明：
取任意x\in H，令y=x可推出单位元是否在H内，令y=e_G可推出逆元是否在H
最后令x为x^{-1}可得到(x^{-1})^{-1}*y=x*y\in H即封闭的条件

举个特例：在加法群内，判据变为
::: align-center
非空且对任意x,y\in H，有y-x\in H，则H是子群

:::

中心

设(G,*)是群，中心定义为
::: align-center
Z(G)=\{a\in G|\forall g\in G,ag=ga\}

:::
也就是与群里所有元素都可交换的元素组成的群

下面证Z(G)是G的子群，使用推论1，首先e_G\in Z(G)，Z(G)非空，再证封闭，若a,b\in Z(G)，要证a*b\in Z(G)，对任意g\in G

考虑a(bg)，考虑b在Z(G)内，故bg=gb，于是有a(bg)=a(gb)=(ag)b，再由a在Z(G)内得到(ag)b=(ga)b=g(ab)

再证存在逆元且封闭，若a\in Z(G)，要证a^{-1}\in Z(G)，有a^{-1}g=(g^{-1}a)^{-1}=(ag^{-1})^{-1}=ga^{-1}
得证

中心化子

给定一个固定元素g\in G，它的中心化子（Centraliser）定义为：
::: align-center
C_G(g)=\{h\in G|gh=hg\}

:::
也就是与这个特定的元素可交换的所有元素的集合组成的群

下面证C_G(g)是G的子群，使用推论1，任取C_G(g)内的两个元素h,k，对G内的元素g，有
::: align-center
(hk)g=h(kg)=h(gk)=(hg)k=(gh)k=g(hk)

:::
于是封闭性得证，再证逆元封闭
::: align-center
gh^{-1}=(hg^{-1})^{-1}=(g^{-1}h)^{-1}=h^{-1}g

:::
或者
::: align-center
gh^{-1}=h^{-1}hgh^{-1}=h^{-1}(gh)h^{-1}=h^{-1}g

:::
得证

中心和中心化子的关系

由于Z(G)是与所有元素都交换的集合，C_G(g)是与某个固定g可交换的集合，所以一定有
::: align-center
C_G(g)\le Z(G)

:::

且如果G是阿贝尔群，则任意元素都可交换，此时C_G(g)=G=Z(G)

在一般情况下Z(G)=\cap_{g\in G} C_G(g)

元素的阶、生成子群和循环群的正式引入

元素的阶

如果存在最小的正整数n使g^n=e_G，我们就把这个最小的n叫做g的阶，记为o(g)或|g|，如果不存在这样的正整数，就说g有无限阶

直观的来说，就是不断乘g，第一次回到单位元e_G的步数

生成子群

定义\langle g\rangle=\{g^n| n\in\mathbb{Z}\}
这叫做g生成的循环子群（Cyclic Subgroup）

证明\langle g\rangle是子群：

• 非空：e=g^0\in\langle g\rangle
• 用一步法判定：a*b^{-1}=g^{n}g^{-m}=g^{n-m}\in\langle g\rangle

故\langle g\rangle\le G

群元素的阶与生成子群的形状

（1）若g是无限阶的，则其生成子群中的所有幂都不同，即
::: align-center
g^n\ne g^m\quad(n\ne m)

:::

证：假若g^n=g^m，则g^{n-m}=e，这正好是元素的阶的定义，说明这个元素的阶位n-m，与g是无限阶矛盾
（2）若o(g)=n，则\langle g\rangle恰好有n个元素，即
::: align-center
\langle g\rangle =\{e_G,g,g^2,\cdots,g^{n-1}\}

:::
证：首先显然\{e_G,g,g^2,\cdots,g^{n-1}\}\subseteq \langle g\rangle，因为g取前n次幂会得到这个集合。取群内的任意一个元素g^r并令r=np+q(0\le q，则有g^r=g^{np}g^{q}=(g^{n})^pg^q=g^q，可以得到\langle g\rangle\subseteq \{e_G,g,g^2,\cdots,g^{n-1}\}，还需要证明集合内的元素的确两两不相同，若g^i=g^j(0\le i，右乘g^{-i}得到g^{j-i}=e_G，但0\le j-i，这与o(g)=n这个阶的定义（使得g^n=e_G的最小正整数）矛盾，故集合里恰好有n个不同的元素

后有两个推论：
（1）|\langle g\rangle|=o(g)，上面已经证明
（2）g^k=e_G\iff o(g)\mid k
证明：
充分性：假设o(g)=n，令k=pn+q(0\le q，则有
::: align-center
g^{pn+q}=(g^n)^pg^q=e_Gg^q=g^q

:::
则g^q=e_G，又因为0\le q，为了让g^q=e_G，q只能取0，则k=pn\Rightarrow o(g)\mid k

必要性：若o(g)\mid k，则k=po(g)，那么
::: align-center
g^k=g^{po(g)}=(g^{o(g)})^p=e_G

:::

循环群

循环群的定义

群G称为循环群，如果存在某个元素g\in G使得
::: align-center
\langle g\rangle = G

:::
这样的g称作生成元，也就是说，G里所有元素都能写成g的幂

循环群的同构性

假设循环群由生成元g生成

（1）若g是无限阶的，则G\simeq \mathbb{Z}
（2）若g是有限阶的，设为n，则G\simeq \mathbb{Z}_n
定义映射：
::: align-center
\psi:\mathbb{Z}\to G,\quad\psi(k)=g^k

:::
验证同态：
::: align-center
\psi(k+l)=g^{k+l}=g^kg^l=\psi(k)\psi(l)

:::
之后验证双射：
满射：即对于任意的h\in G均存在k\in\mathbb{Z}使得\psi(k)=g^k=h，而因为群G是g生成的，一定有G=\langle g\rangle，结合\langle g \rangle的定义得到函数一定是满射的
单射：即对于\psi(k)=\psi(l)一定可得到k=l。由\psi(k)=\psi(l)得到g^k=g^l
（1）若g是无限阶的，此时有g^{k-l}=e_G，只能得出k=l
（2）若g是有限阶的，那么g^{k-l}=e_G\Rightarrow o(g)|k-l\Rightarrow k\equiv l\pmod{n}

循环群生成元的幂是否还是生成元？

在有限群的情况下，g^k是G的生成元当且仅当gcd(k,n)=1，无限群下当且仅当k=\pm 1

证：即要证存在某个整数x，使得(g^k)^x=g，即g^{kx-1}=e，若g是无限阶的则kx-1=0，因为x必须是整数，k只可能是\pm 1。若g是有限阶，设为n，那么有n\mid kx-1\Rightarrow kx-1=l'n\Rightarrow kx+ln=1，由贝祖形式得到k,n互素，即gcd(k,n)=1

循环群的子群结构

设G是循环群，G=\langle g\rangle，且|G|=n（即G是有限阶），有

1. 每个子群H\le G都是循环群
2. 任何子群的阶都整除n
3. 对每个n的的正因子d，都有且只有一个阶为d的子群，它由g^{\frac{n}{d}}生成

::: align-center
H_d=\langle g^{\frac{n}{d}}\rangle,\quad |H_d|=d

:::
证：
（1）取任意子群H\le G，若H=\{e\}，显然循环。因为G是循环群，又由g生成，故所有G中的元素实际上都是g的幂，令d>0是使得g^d\in H的最小正整数。现在证明H=\langle g^d\rangle

首先证明\langle g^d\rangle\subseteq H，因为g^d\in H且H是子群，子群的一个重要性质便是子群内的运算均封闭，所以由g^d进行生成得到的集合\langle g^d\rangle必然是H的子集。而反过来，取任意的g^f\in H，令f=qd+r(0\le r，则g^{r}=g^{f-qd}=g^fg^{-qd}\in H（封闭），如果r>0，那么那就就会与d的最小性矛盾，所以r=0，那么f=qd\Rightarrow d\mid f即这个g^f是g^d的某个幂，那么H\subseteq \langle g^d\rangle

故H=\langle g^d\rangle
（2）H=\langle g^d\rangle，设|H|=e，则(g^d)^e=e_G，又因为G是循环群且|G|=n，所以o(g)=n，那么就有n\mid de，现在要证e\mid n

令s=gcd(n,d)，记n=sn_1,d=sd_1，同时得到n_1=\frac{n}{s},d_1=\frac{d}{s}，由数论的结论得到gcd(n_1,d_1)=1。现在n\mid de变为sn_1\mid sd_1e\Rightarrow n_1\mid d_1e，又因为n_1,d_1互素，由欧几里得引理得到n_1\mid e。而另一方面，(g^d)^{n_1}=(g)^{dn_1}=(g)^{sd_1n_1}=(g)^{nd_1}=(g^n)^{d_1}=e_G，这说明n_1也是使得(g^{d})^x=e_G的解x之一，而e也是且是最小正整数解，所以有e\le n_1，再加上之前的n_1\mid e得到e=n_1，所以n=se，得到e\mid n

并且，由n=se还能得到e=\frac{n}{s}=\frac{n}{gcd(n,d)}，而e是子群H的阶数，而我们已证|\langle g\rangle|=o(g)，即由g生成的循环子群的阶（子群的阶）等于g这个在群G里的元素的阶，故我们最终得到
::: align-center
o(g^d)=\frac{n}{gcd(n,d)}

:::
故我们得到了一个可以方便的在循环群中求元素阶的方法

1. 确定循环群的阶，也就是循环群的元素个数n
2. 把要求阶数的元素写为g^d，特别地，当群是(\mathbb{Z}_n,+)时，此时g^d在加法下实际为dg，若选择生成元g为1，则g^d正好代表群的第d个元素，也就是群的第d个元素的阶o(d)=o(g^d)=\frac{n}{gcd(n,d)}

寻找循环群子群的通法

1. 计算群的阶数d=|G|
2. 找出d的所有正因子，由循环群子群的结论我们可以得到G的任何子群的阶数均不可能为除这些正因子以外的数
3. 计算群内元素的阶数，并写出它们的生成循环子群
4. 将这些子群的阶数与2.中计算出的正因子个数进行比对

将在下方拉格朗日定理的推论中再次提到

置换群

置换与两行记号

所谓置换，指的是集合A上的一个双射\pi: A\to A，用[x]\pi表示\pi(x)，我们是考虑A=\{1,\cdots,m\}的置换。

用两行记号表示，可以使用一个2\times n的矩阵，上面一行写置换前的下面一行写置换后的

循环与循环分解

一个循环(a_1a_2\cdots a_k)表示a_1\rightarrow a_2\rightarrow\cdots \rightarrow a_k\rightarrow a_1，其余元素不动

任何置换都能写成若干个两两不相交的循环乘积

对称群与逆元

\{1,\cdots,n\}的全体置换，在复合这种运算下构成对称群S_n，如果\phi可以写成不交循环，那么
::: align-center
\pi=(a_{1,1}\cdots a_{1,k_1})\cdots(a_{r,1}\cdots a_{r,k_r})

:::
则
::: align-center
\pi^{-1}=(a_{1,k_1}\cdots a_{1,1})\cdots(a_{r,k_r}\cdots a_{r,1})

:::
即每个循环反向

置换的阶

若\pi的不交循环分解里各循环长度分别是n_1,\cdots,n_k，则
::: align-center
o(\pi)=lcm(n_1,\cdots,n_k)=\frac{\prod_{i=1}^k n_i}{gcd(n1,\cdots,n_k)}

:::

陪集与拉格朗日定理

左陪集/右陪集

设G是群，H\le G,a\in G

左陪集：aH=\{ah|h\in H\}
右陪集：Ha=\{ha|h\in H\}

直觉上，就是把子群H整体左乘/右乘一个元素a得到一个同样大小的平移副本

陪集的基本引理

1. a\in aH
2. aH=H\Leftrightarrow a\in H
3. 两个左陪集要么相等，要么不交：aH=bH或aH\cap bH=\emptyset（右陪集同样成立）
4. 判等条件：aH=bH\Leftrightarrow a^{-1}b\in H（右陪集变为ab^{-1}）
5. 若H有限，则每个陪集大小都等于|H|：|aH|=|H|（用双射h\to ah）
6. aH=Ha\Leftrightarrow aHa^{-1}=H

证：
（1）
因为子群一定含单位元e_G，所以a=a e_G\in aH
（2）
充分性：若aH=H，则由1.知a一定在aH内，故a在H内
必要性：若a\in H，取任意ah\in aH，其中h\in H，因a,h\in H且H封闭，得ah\in H，故aH\subseteq H。反之，取任意h\in H，因a\in H\Rightarrow a^{-1}\in H，于是a^{-1}h\in H，令h'=a^{-1}h，则h=ah'\in aH，故得到aH=H
（3）
只需要证明如果左右陪集有交点则必然相等，假设aH\cap bH\ne \emptyset，则存在h,g\in H使得
::: align-center
ah=bg

:::
于是
::: align-center
b=ahg^{-1}

:::
因为h,g^{-1}\in H，从而b\in aH。现在证bH\subseteq aH，取任意x\in bH,x=bh'(h'\in H)，代入b=ahg^{-1}得
::: align-center
x=(ahg^{-1})h'=a(hg^{-1}h')

:::
由于H内运算封闭，所以x\in aH，因此bH\subseteq aH，同理也可证aH\subseteq bH，于是aH=bH，所以得到结论两个陪集要么不交要么相等
（4）
充分性：假设aH=bH，因为b\in bH=aH，所以存在h\in H使b=ah，两边左乘a^{-1}得
::: align-center
a^{-1}b=h\in H

:::
必要性：假设a^{-1}b\in H，要证aH=bH，任取x\in aH，则x=ah(h\in H)，写
::: align-center
h=(a^{-1}b)g

:::
其中g=(b^{-1}a)h，因为a^{-1}b\in H,h\in H于是有g\in H，于是
::: align-center
x=ah=a(a^{-1}b)g=bg\in bH

:::
所以aH\subseteq bH，同理对称地得bH\subseteq aH，因此aH=bH
（5）
构造一个从H到aH的函数
::: align-center
\varphi: H\to aH\quad\varphi(h)=ah

:::
满射：按定义，aH中每个元素都形如ah
单射：若ah_1=ah_2，左消去a得到h_1=h_2
所以\varphi是双射，|aH|=|bH|
（6）
充分性：假设aH=Ha，取任意h\in H，因为ah\in aH=Ha，存在g\in H使ah=ga，右乘a^{-1}得
::: align-center
aha^{-1}=g\in H

:::
所以aHa^{-1}\subseteq H，反过来取任意h\in H，因为aH=Ha也等价于H=a^{-1}Ha（把等式左右乘a^{-1}）可推出每个h也属于aHa^{-1}，从而H\subseteq aHa^{-1}，因此aHa^{-1}=H
必要性：假设aHa^{-1}=H，证明aH=Ha。取x\in Ha,x=ha(h\in H)，由aHa^{-1}=H知存在g\in H使得h=aga^{-1}，于是
::: align-center
x=ha=aga^{-1}a=ag\in aH

:::
所以Ha\subseteq aH，反向同理得aH=Ha

拉格朗日定理

若G是有限群，H\le G，则

1. |H|整除|G|
2. H的左陪集个数等于\frac{|G|}{|H|}

证：
取|H|的所有不同的左陪集a_1H\cdots,a_kH，由陪集的引理（3）得到这些陪集两两不相交，而每个群内元素g都属于某个左陪集，所以这些陪集是整个群的一个划分
::: align-center
G=\cup_{i=1}^k a_iH

:::
由陪集的引理（5）得到每个陪集的大小都为|H|，于是
::: align-center
|G|=\sum_{i=1}^k|a_iH|=k|H|

:::
因此|H|\mid |G|，且k=\frac{|G|}{|H|}就是左陪集的个数

拉格朗日定理的推论

（1）元素的阶整除群的阶
对任意a\in G，循环子群是G的子群，且已有推论证得||=o(a)，由拉格朗日定理又有||\mid |G|，所以o(a)\mid |G|

此条推论可以用于判别子群的可能阶数，因为其一定是群阶数的一个正因子
（2）a^{|G|}=e
设o(a)=m，又知m\mid |G|，写|G|=qm，则
::: align-center
a^{|G|}=a^{qm}=(a^m)^q=e^q=e

:::
（3）素数阶的群必循环
若|G|=p是素数，取任意非单位元a\ne e，则o(a)\mid p且o(a)\ge 2，那么只能是o(a)=p

对于U_n，这里有推论当n为\{1,2,4,p^k,2p^k\}，其中p为奇素数时群一定循环，这里不证

费马小定理和欧拉定理

（费马小定理）若p是素数且p\nmid a，则在群\mathbb{Z}_p^*（定义模乘法）（阶为p-1）中，有
::: align-center
a^{p-1}\equiv 1\pmod{p}

:::

（欧拉定理）若gcd(a,n)=1，则在群U_n（定义模乘法）（阶为\phi(n)）中，有
::: align-center
a^{\phi(n)}\equiv 1\pmod{n}

:::

在计算一个a^p\pmod{n}时，可以考虑使用费马小定理/欧拉定理简化计算

1. 如果n是素数，且n\nmid a时，费马小定理可用，一定有a^{n-1}\equiv 1\pmod{n}，此时只需要计算a^{p\bmod n-1}\pmod{n}即可
2. 如果n本身非素，但a,n互素，则欧拉定理依然可用，此时依然可以直接计算a^{p\bmod \phi(n)}\pmod{n}

证明：
费马小定理：
令r\equiv a\pmod{p}，因为p不整除a，所以r\neq 0
考虑群\mathbb{Z}_p^*（定义模p乘法），已经在群的部分证明当p为素数时它是群，而且阶为p-1
r在此群里，由拉格朗日定理的推论（2）得到
::: align-center
r^{p-1}\equiv 1\pmod{p}

:::
于是
::: align-center
a^{p-1}\equiv 1\pmod{p}

:::

欧拉定理：
因为gcd(a,n)=1，则由U_n的定义得到a是U_n的一个元素，又知道U_n的阶数可通过欧拉函数\phi(n)计算得到，再结合拉格朗日定理的推论（2）得到
::: align-center
a^{|U_n|}=a^{\phi(n)}\equiv 1\pmod{n}

:::