I.群初步

I.基础定义

• 封闭性：$\forall a,b\in\mathbb S,a\cdot b\in\mathbb S$。
• 结合律：$\forall a,b,c\in\mathbb S,(a\cdot b)\cdot c=a\cdot(b\cdot c)$。
• 单位元/幺元：$\exists e\in\mathbb S,\operatorname{s.t.}\forall a\in\mathbb S,e\cdot a=a\cdot e=a$​。
• 逆元：$\forall a\in\mathbb S,\exists b\in\mathbb S,\operatorname{s.t.}a\cdot b=b\cdot a=e$。称 $b$ 为 $a$ 的逆元，记作 $a^{-1}$。

• 封闭性：$\forall a,b\in\mathbb S,a\cdot b\in\mathbb S$。
• 结合律：$\forall a,b,c\in\mathbb S,(a\cdot b)\cdot c=a\cdot(b\cdot c)$。
• 左单位元/幺元：$\exists e\in\mathbb S,\operatorname{s.t.}\forall a\in\mathbb S,e\cdot a=a$​​​。
• 左逆元：$\forall a\in\mathbb S,\exists b\in\mathbb S,\operatorname{s.t.}b\cdot a=e$​​​。称 $b$​​​ 为 $a$​​​ 的左逆元，记作 $a^{-1}$​​​。

Proof 1.左单位元等于右单位元

设左单位元为 $e_l$，右单位元为 $e_r$。则 $e_le_r=e_l$（$e_r$ 是右单位元），且 $e_le_r=e_r$（$e_l$ 是左单位元），故 $e_l=e_r$。

Proof 2.单位元唯一

设有两单位元 $e,e'$。则 $ee'=e=e'$。

Proof 3.左逆元等于右逆元

设 $a$ 的左逆元为 $b$，右逆元为 $c$，则 $ba=e=ac$，则 $bac=ec$，则 $be=ec$，则 $b=c$。

• 消去律：在群中如果 $ab=ac$，则 $b=c$。可以直接左乘 $a^{-1}$ 得证。
  这被称作“左消去律”，该性质是左逆元存在的直接推论。
  同理有右逆元的推论——右消去律。
  因为在群中左右逆元均存在，所以二者被合并作了消去律。
  由消去律可以直接证得左右逆元均唯一，进而证得逆元的逆元是本身。

II.基础含义

III.扩展定义

Proof：

必要性显然，因为若其是群则左右同乘 $a$ 的逆元即证。

充分性：先证单位元。若令 $a=b$​​​，则由上，方程 $xb=b$​​ 有解，设为 $e$​​。那么如果 $\forall a\in\mathbb G,ea=a$​​ 则 $e$​​ 是单位元。因 $by=a$​​​​ 有解，故设解为 $c$​ 则 $ea=e(bc)=(eb)c=bc=a$​。

逆元显然存在。

Proof：

必要性显然。

考虑令 $\mathbb G$​ 中所有元素全都左乘 $a$​ 得到一集合 $\mathbb G'$​。因为 $\mathbb G$​​ 是群，所以 $\mathbb G'\subseteq\mathbb G$​。因为 $\mathbb G$​ 中无相同元素，所以由消去律 $\mathbb G'$​ 中亦无相同元素，则 $|\mathbb G'|=|\mathbb G|$​，即二者相同，即方程 $ay=b$​ 必有解。同理 $xa=b$ 亦有解。

注意该 Proof 在 $\mathbb G$​​ 是无限群时不一定成立，这涉及到无限的知识，与群论就不太紧密了，暂且忽略。

IV.群的子系统

前者由单位元唯一和母群消去律得证；后者由逆元唯一和母群消去律得证。

$\mathbb G$ 是群，故运算有结合律；$\mathbb H$ 又是封闭的，故 $\mathbb H$ 是半群；应用有限群判定定理即证。

update on 2022.2.22：增加了“子集”的描述。之前写的时候漏掉了这一点，导致出现了很无厘头的定理。感谢 @1kri 的指出。

Proof：

考虑 $\mathbb{G=F\cup H}$。

则必然存在 $f\notin\mathbb F,h\notin\mathbb H$（不然就不是真子群了）。

则必然有 $f\in\mathbb H,h\in\mathbb F$。

考虑 $hf$​。

如 $hf\in\mathbb F$，则 $h^{-1}hf\in{\mathbb F}$，则 $f\in\mathbb F$，与前提相悖。同理可排除 $hf\in{\mathbb H}$ 的场景。

$hf\notin\mathbb{F,H}$，则 $hf\notin\mathbb G$，即 $\mathbb{G\neq F\cup H}$。​

V.群元素的阶

Proof：

证明 $|a|=n$ 时，常用套路是先证 $a^n=e$，再证 $n$ 是最小的。

应用到本处时，前者显然，后者就用如果 $(a^k)^m=e$ 那么 $km$ 必是 $|a|$ 的倍数而这最小的 $m$ 即为上式值。

Proof：

$(ab)^{mn}=e$​ 显然。

如 $(ab)^r=e$​​，则 $(ab)^{rm}=e$​​，即 $b^{rm}=e$​​，这等价于 $n|rm$​​，又 $\gcd(n,m)=1$​​，则 $n|r$​，则最小 $r$​ 即为 $mn$​。

Proof：

考虑反证。假设存在 $|a|=n$ 且 $n\nmid m$。则必存在一个质数 $p$，使得 $n$ 中 $p$ 的次数大于 $m$ 中 $p$​ 的次数。

现设 $m$​ 对应的元素是 $b$（即 $|b|=m$）。

不妨令 $n=p^Nn',m=p^Mm'$​，则应有 $N>M$​。则 $|b^{p^M}|=\dfrac{m}{\gcd(p^M,m)}=m',|a^{n'}|=p^N$​。

交换群、互质，上一个定理的条件齐全，得到 $|b^{p^M}a^{n'}|=m'p^N$​。因为 $N>M$，所以 $m'p^N>m$，与 $m$ 是最大阶的前提矛盾。​​

VI.特殊群

闲话一句：这里的“挠群”听上去有些怪，但是其英文是 torsion group，翻译过来就是 扭曲的群。而“挠”字在汉语中除了“抓挠”的意思外，也有“扭曲”的意思，如“不屈不挠”。

我觉得起这个名称纯粹是因为“扭曲群”这种翻译太怪了。

接下来我会一直称其为挠群，因为周期群容易和下面介绍的循环群混淆。

Proof：$a$​ 的次幂必成环，否则显然群不可能有限。

顺带提一句，这并不意味着无限群就一定不是挠群，典型例子如令 $\Omega_i$​ 表示 $i$​ 次单位根全集，则全体 $\Omega_i$​ 的并集是挠群。

这很显然，因为 $a$ 的次幂定是关于 $|a|$ 成环的。

一对一映射是可能的，只需要找到循环群的生成元然后拿它去一一对应即可。

Proof：不妨设母循环群其中一个生成元是 $a$。考虑将其子群中所有元素写成 $a^k$ 的形式并找到 $k$ 最小的一个。则因为是子群，所以所有 $a^{ik}$ 都在群中，其中 $i$ 是整数。如果还有其它 $a$ 的非 $ik$ 次幂在子群中，则恰大于其的一个 $ik$ 次幂与其逆元之积是一个 $a$ 的小于 $k$​ 次幂，与 $k$ 是幂次最小的一个的前提相悖。则该子群是循环群，一个生成元是 $a^k$。

Proof：无限循环群情形显然。有限循环群下，考虑令 $n=pq$​​，则 $|a^q|=p$​​，故 $\left<a^q\right>$​​ 阶数为 $p$​。考虑若 $\left<a^r\right>$​ 阶数亦为 $p$​，则 $|a^r|=p=\dfrac nq$​。且有 $|a^r|=\dfrac{n}{\gcd(n,r)}$​​，则 $q=\gcd(n,r)=r$。

II.变换群与置换群

I.映射与同构初步

这部分是为了让定义严密而出现的，与群论关系不大

不了解这些东西不会对本章的大部分东西的理解产生影响，但是窃以为您会在读到 IV 章时后悔的。

这个定义以后还会改头换面再次出现。

Proof：

向量空间间线性映射可以由矩阵 $A$​​​​ 刻画。因为是同维度，所以 $A$ 是方阵。

如果是单射则方程 $A\mathbf x=\mathbf b$​​ 有至多一解，即 $A$ 的列线性无关，即 $A$ 的列空间等于全集，即 $A$ 满射。

如果是满射则方程 $A\mathbf x=\mathbf b$ 有至少一解，即 $\mathbf b$ 位于 $A$ 的列空间中，即 $A$ 的列空间等于全集，即 $A$ 的列线性无关，即 $A$ 可逆。那么求逆即可由 $\bf b$ 逆推出 $\bf x$，则是单射。

这很显然。

update on 2023.8.6:

在写环论的过程中发现此处的纰漏，并修改了此处描述。现在此处的描述应该是最常见的描述。

II.置换与置换群初步

这里大家可能有一个疑问：集合间的元素不应该是无序的吗，那么集合到自身的双射，结果难道不是定为集合本身吗？

确实是这样，但是这是因为侧重点错误。在研究置换时，不应该关注集合本身，而应该关注集合中的每个元素——只有对每个元素来说，置换才是有意义的。

III.置换群进阶

Proof：

设有一群 $\mathbb G$​​。现在有一个变换 $\tau_a:x\mapsto ax$​​，其中 $a,x\in\mathbb G$​​​。

因为 $\mathbb G$ 是群，所以显然也有 $ax\in\mathbb G$。

显然这个变换是满射的，因为对于每个 $ax$​ 只需要左乘 $a$​​ 的逆元就能得到与之对应的 $x$。

显然这个变换是单射的，因为左消去律在群中成立。

故这个变换是双射的，即其是置换。

考虑所有置换 $\tau_a$ 与变换复合运算 $\circ$ 构成的二元组。

显然其是封闭的：$\tau_a\circ\tau_b=\tau_{ab}$。

显然其是结合的，因为 $\circ$ 是结合的。

显然其有单位元，即为恒等变换 $\tau_e$​。显然其有逆元，因为置换是双射所以其逆一定存在。

则该二元组是群。设其为 $\mathbb T$。

考虑构建映射 $\varphi:\mathbb{G\to T},a\mapsto \tau_a$。

显然该映射是双射。

显然映射前的 $\cdot$ 运算与映射后的 $\circ$ 运算等价。

则 $\mathbb{G,T}$​​​ 同构。

“保留范围”这个术语不正规，但是我暂时找不到有相同意义的正规术语，那就暂且先这么用罢。

显然只有两不相交轮换的保留范围中的元素在复合中的结果是不平凡的。而它们的保留范围无交，故所有此中元素必经历一次平凡映射（到自身的映射）与一次非平凡映射。其结果必为该非平凡映射，且无论是先进行平凡映射还是先进行非平凡映射都是一样的。

考虑把置换写成序列的形式。

每对换一次，显然序列的逆序对数会变化一，也即奇偶性会变化。

显然在分解为对换之复合时，我们可以再复合一个单位置换，其逆序对数为 $0$。

假设我们有一组合法的分解序列。考虑在其基础上通过增加或删除某些对换以得到其它分解序列。每增加或删除一个对换，序列逆序对数的奇偶性亦会翻转，这就意味着我们还需要再增加或删除一个对换以扳平逆序对数的奇偶性。

这就表示奇偶性是固定的。

Proof：

奇偶置换之积的奇偶性同奇偶数之和的奇偶性类似，即有 $\text{奇}\times\text{奇}=\text{偶},\text{奇}\times\text{偶}=\text{奇},\text{偶}\times\text{偶}=\text{偶}$​​。则显然置换群中可以没有奇置换。

现假设群中有至少一个奇置换。则我们令群中所有元素全都左乘该奇置换得到了一个新结构，因为消去律存在所以该新结构中元素两两不同，又因为封闭性存在所以该新结构就是原群。而左乘的操作翻转了所有置换的奇偶性，所以便得到了该群中奇偶置换数量相同。

前者显然。后者因为不相交轮换间乘法有交换律，所以 $\text{置换}^{\text{幂}}=\text{轮换之积}^{\text{幂}}=\text{轮换}^{\text{幂}}\text{之积}$，进而得到最小公倍数的结论。

III.子群扩展

I.陪集初步

具体是什么性质呢？在 IV 章中就能见到了。

Proof：

$\mathbb H$ 中所有元素左乘 $a$ 后显然仍两两不同，故 $|a\mathbb H|=|\mathbb H|$。

Proof：

$\Rightarrow$：因为 $\mathbb H$ 是群，所以 $a\mathbb H$ 是 $\mathbb H$ 的子集。又由左消去律的逆否命题，$\mathbb H$ 中不相等的两个数在左乘 $a$ 后亦不可能相等，则 $|a\mathbb H|=|\mathbb H|$，即 $a\mathbb H=\mathbb H$。

$\Leftarrow$：显然有 $a\in a\mathbb H$（由 $\mathbb H$ 中单位元得到），进而 $a\in\mathbb H$。

$\Leftarrow$：由上显然。

$\Rightarrow$：群中必有单位元，单位元存在则必有 $a^{-1}\in\mathbb H$，进而有 $a\in\mathbb H$。

Update on 2022.2.23：修改一处手癌。感谢 @1kri 指出。

因为左同余关系的实质是左陪集相等，而相等关系具有传递性，因而成等价类。

Proof：

$\Rightarrow$：显然 $b\in b\mathbb H$（由 $\mathbb H$​ 中单位元得到），进而 $b\in a\mathbb H$。

$\Leftarrow$：若 $b\in a\mathbb H$，则显然存在 $c\in\mathbb H$ 满足 $b=ac$。则 $b\mathbb H=(ac)\mathbb H\xlongequal{群上运算的结合律} a(c\mathbb H)\xlongequal{c\in\mathbb H\Leftrightarrow c\mathbb H=\mathbb H}a\mathbb H$，也即 $a\equiv b\pmod{\mathbb H}$。

Proof：

后一个等价符号只需交换 $a,b$ 即可由前一个等价符号证明。下只证前一个等价符号。

由前一个证明，$a\equiv b\pmod{\mathbb H}\Leftrightarrow b\in a\mathbb H$，则 $b\in a\mathbb H\Leftrightarrow b=ac,c\in\mathbb H\Leftrightarrow a^{-1}b\in\mathbb H$。​​

II.陪集分解

Proof：

如 $a\mathbb H\cap b\mathbb H\neq\varnothing$，则设 $c\in(a\mathbb H\cap b\mathbb H)$，显然有 $c\in a\mathbb H,c\in b\mathbb H$，按照上面的定理则有 $a\equiv c\equiv b$​​，即左陪集有交等价于左陪集等价，逆否命题就是左陪集不等价等价于左陪集无交。

Proof：

各一次：显然 $a\in a\mathbb H$，则所有 $a\mathbb H$ 之并等于全集。

恰一次：显然等价类间不可能再等价，故它们只可能无交，则显然所有元素最多在一个等价类中出现。

Proof：

令左右陪集分解分别为 $\mathbb{L,R}$。

构造 $\varphi:\mathbb L\to\mathbb R,a\mathbb H\mapsto \mathbb Ha^{-1}$。显然其是双射。

III.子群指数与拉格朗日定理

Proof：

首先，$\mathbb H$ 的所有陪集的大小相等，这个在以前就证过了。

其次，关于 $\mathbb H$​​ 的陪集分解中所有陪集无交且并为 $\mathbb G$。

这就直接得到了拉格朗日定理。

Proof：

首先我们在很久以前就证过了有限群中元素的阶非无穷。

那么我们令子群 $\mathbb H=\left<a\right>$，显然其阶就等于 $a$ 的阶。

依据拉格朗日定理，$|\mathbb H|$ 是 $|\mathbb G|$ 的因数，则 $|a|$ 是 $|\mathbb G|$ 的因数。

Proof：

依据拉格朗日定理，此群的子群之阶只有可能为 $1$​ 或该素数。

阶为 $1$ 的子群显然只可能仅包含单位元。阶为该素数的子群显然就是该群本身。

同理，群中元素的阶也仅可能为 $1$​​ 或该素数。显然阶为 $1$ 的元素仅可能为单位元。

故该有限群中存在阶等于该群的阶的元素。我们前面已经证过了，其为循环群。

$(\mathbb G:\mathbb H)|\mathbb H|=|\mathbb G|$​，然后就易证了。

IV.群间运算与关系

I.群同态进阶

Proof：

设满同态映射为 $\varphi$。因为同态，故 $\varphi(a)\varphi(b)=\varphi(ab)$​。

则有 $\Big(\varphi(a)\varphi(b)\Big)\varphi(c)=\varphi(ab)\varphi(c)=\varphi(abc)=\varphi(a)\varphi(bc)=\varphi(a)\Big(\varphi(b)\varphi(c)\Big)$​。

因为是满同态，所以值域中任一元素均可被表示成至少一个 $\varphi(a)$​ 的形式，进而该运算在其中满足结合律。

Proof：

设该满同态映射为 $\varphi:\mathbb G\to\mathbb G'$。则因为同态，所以 $\varphi(a)\varphi(b)=\varphi(ab)$​。​

现验证群的各项要求：

• 结合律，上方已证过。
• 单位元。$\varphi(e)\varphi(a)=\varphi(ea)=\varphi(a)$。
• 逆元。$\varphi(a^{-1})\varphi(a)=\varphi(a^{-1}a)=\varphi(e)$​。

又因为是满同态，所以 $\mathbb G'$ 中任一元素均可被表示成至少一个 $\varphi(a)$ 的形式，进而满足其是群。

• $\varphi(e)=e'$。
• $\varphi(a^{-1})=\varphi(a)^{-1}$（注意这里的两个 $-1$ 是在不同群中的逆元）。

Proof：

虽然 $\varphi$ 不是 $\mathbb G$ 与 $\mathbb G'$ 间的满同态，但定是 $\mathbb G$ 与 $\varphi(\mathbb G)$ 间的满同态。由群结构在满同态上的传递性定理，$\varphi(\mathbb G)$ 亦是群，则其是 $\mathbb G'$​ 的子群。故上述两性质成立。

Proof：

$\Rightarrow$：因为在 $\mathbb H$ 上的 $\varphi$ 是满射，且 $\mathbb H$ 是群，则 $\varphi$ 在 $\mathbb H$ 上是满同态，进而由群结构在满同态上的传递性定理，$\varphi(\mathbb H)$ 亦是群，则其是 $\mathbb G'$​​ 的子群。

$\Leftarrow$：由上个定理，$\mathbb H$ 中有逆元和单位元，且可证得对于 $\varphi(a),\varphi(b)\in\mathbb \varphi(\mathbb H)$，总有 $a^{-1}b\in\mathbb H$，进而有封闭性，进而是群。​

Proof：

必要性显然。

充分性：若 $\varphi(a)=\varphi(b)$，则 $\varphi(a^{-1})\varphi(b)=\varphi(a)^{-1}\varphi(b)=e'$，若原像唯一（显然此时其仅可能为 $e$）则可得到 $a^{-1}b=e$，即 $a=b$。

II.积

子群积也大量、普遍、泛用地被叫做“积”，符号同样是 $\mathbb D=\mathbb F\times\mathbb H$，并同样可以被省略乘号。也就是说，它与直积在符号上区分不开。但是，一般都可以简单判定到底是哪种积。

只需展开子群积即可。

Counterexample：

设有两个矩阵 $A,B$ 满足 $A^2=I,B^2=I,A\neq B$。现考虑它们生成的群 $\left<A,B\right>$。$\{I,A\}\times\{I,B\}=\{I,A,B,AB\}$，其并非 $\left<A,B\right>$ 的子群，因为 $BA$ 不在其中。​

注意到这里用的是子集符号 $\subseteq$​​ 而非子群符号 $\leq$​，原因是 $\mathbb{F,H}$​ 不一定是群，再大大咧咧地用群的符号好像不太对劲。

证明显然，因为只需要考虑乘上的是单位元即可。

Proof：

显然 $\mathbb{F\cap H}$​​ 是 $\mathbb F$​​ 的子群，进而有 $\mathbb F$​​ 关于 $\mathbb{F\cap H}$​​ 的左陪集分解：$\mathbb F=\bigcup\limits_{f_i\in\mathbb F}f_i(\mathbb{F\cap H})$​​。显然 $f_i$​​ 的个数即为 $\mathbb{\dfrac{|F|}{|F\cap H|}}$​​。

显然 $\mathbb H\subseteq\mathbb{FH}\subseteq\mathbb G$​​。进而定可构造出 $\mathbb{FH}=\bigcup\limits_{h_i\in\mathbb F}h_i\mathbb H$​，因为显然全体 $\mathbb F$​ 中元素即为一组合法的 $h$​。因为显然 $h_i\mathbb H$​ 中亦有等价类存在且不同等价类中的元素无交，故我们仍可对于每个等价类仅保留一个元素。但注意这并非左陪集分解，因为 $\mathbb{FH}$​ 甚至连群都不是。​

显然 $h$ 仅取 $\mathbb F$ 中元素是可行的。考虑什么样的 $h$ 是合法的 $h$。$h_i\mathbb H=h_j\mathbb H\Leftrightarrow h_ih_j^{-1}\in\mathbb H$。又 $h_i,h_j\in\mathbb F$，则 $h_ih_j^{-1}\in\mathbb F$，则 $h_ih_j^{-1}\in\mathbb{F\cap H}$，则 $f_i(\mathbb{F\cap H})=f_j(\mathbb{F\cap H})$。这条性质反过来仍然可推证。故 $h_i\mathbb H=h_j\mathbb H\Leftrightarrow f_i(\mathbb{F\cap H})=f_j(\mathbb{F\cap H})$。这说明全体 $f$ 即为一组合法的 $h$。

则 $f_i$​ 的个数就等于 $h_i$​ 的个数，即 $\mathbb{\dfrac{|F|}{|F\cap H|}}$​。然后每个 $h_i\mathbb H$​ 的大小显然都是 $|\mathbb H|$​，故得出 $|\mathbb{FH}|=\dfrac{|\mathbb F||\mathbb H|}{|\mathbb F\cap\mathbb H|}$​。

III.正规子群

Update on 2022.2.21：删除“正规子群的子群仍是正规子群”这一定理。这里写的时候还不太理解，导致我想当然了。感谢 @chenxia25 指出。希望大家多多指正，多多挑错，让这篇文章变得更加严谨。

Proof：

指数为 $2$ 表明其左/右陪集分解的大小都为 $2$。而因为陪集分解中必然包括该子群本身（关于该子群内部元素的陪集），所以分解中另一个陪集必然是该子群的补集，并且该补集在左右分解中都是相同的。故而，此时的左右陪集分解是相同的，因而是正规子群。

Proof：

$\forall a\in\mathbb G,a\mathbb H=\mathbb Ha$，此式是正规子群的定义。

因为有结合律，所以上式等价于 $\forall a\in\mathbb G,a\mathbb Ha^{-1}=\mathbb H$。

因为左右消去律在群中存在，所以只需要证明所有 $aba^{-1}\in\mathbb H$ 即可，其中 $b\in\mathbb H$。

而这就是上式。

Proof：

首先我们前面已经证过了如 $\mathbb H$ 是子群则 $\varphi(\mathbb H)$​ 亦是子群，反之亦然。

然后，在同态群上显然有 $aba^{-1}=\varphi(a)\varphi(b)\varphi(a)^{-1}$。

上面的性质在常规同态上也是成立的；但是正规子群还要求是满同态，就是因为常规同态下仅保证 $\varphi(\mathbb G)\leq\mathbb G'$​，这意味着有一些 $\mathbb G'$​ 中元素可能不存在原像，进而在 $aba^{-1}=\varphi(a)\varphi(b)\varphi(a)^{-1}$​ 一式中找不到对应的 $a$​，以至于上式可能不成立。然而在满同态上每个 $\mathbb G'$​ 中元素都有原像，进而上式必然成立。

Proof：

设 $\mathbb D=\mathbb{FH}=\bigcup\limits_{f\in\mathbb F}f\mathbb H$，并且 $\mathbb F$ 是常规子群、$\mathbb H$ 是正规子群。

应用子群判定定理，只需证明 $\forall(f_1,f_2\in\mathbb F,h_1,h_2\in\mathbb H),f_1h_1(f_2h_2)^{-1}\in\mathbb D$​​ 即可。

$(f_2h_2)^{-1}=h_2^{-1}f_2^{-1}$。则 $f_1h_1(f_2h_2)^{-1}=f_1h_1h_2^{-1}f_2^{-1}$。

显然有 $h_1h_2^{-1}\in\mathbb H$，则设其为 $h$。则有上式等于 $f_1hf_2^{-1}$。

显然有 $f_1h\in f_1\mathbb H=\mathbb Hf_1$，即 $f_1h$ 定可被表示成 $h_3f_3$ 的形式。

上式等于 $h_3f_3f_2^{-1}$​。显然 $f_3f_2^{-1}\in\mathbb F$​，故设其为 $f$​。

则上式等于 $h_3f$。显然有 $h_3f\in\mathbb Hf=f\mathbb H$，即 $h_3f\in\mathbb D$，即 $f_1h_1(f_2h_2)^{-1}\in\mathbb D$。

证毕。

Proof：

设 $\mathbb D=\mathbb{FH}=\bigcup\limits_{f\in\mathbb F}f\mathbb H$​，并且 $\mathbb{F,H}$​ 均是正规子群。

首先 $\mathbb D$ 是母群 $\mathbb G$ 的子群。

然后即证 $\forall(g\in\mathbb G,d\in\mathbb D),gdg^{-1}\in\mathbb D$。

显然 $d=fh=fg^{-1}gh$。则要证 $gfg^{-1}ghg^{-1}\in\mathbb D$。显然 $gfg^{-1}\in\mathbb F$，$ghg^{-1}\in\mathbb H$。则上式可表示成 $f'h'\in\mathbb D$，而这个式子即是 $\mathbb D$ 的定义。​

这是显然的。

Proof：

• $\text N(\mathbb H)\leq\mathbb G$​​。
  首先显然有 $\text N(\mathbb H)\subseteq\mathbb G$。
  然后用子群判定定理，即证 $\forall a,b\in\text N(\mathbb H),ab^{-1}\in\text N(\mathbb H)$。
  显然 $a\mathbb Ha^{-1}=\mathbb H,b\mathbb Hb^{-1}=\mathbb H$​。则证 $ab^{-1}\mathbb H(ab^{-1})^{-1}=\mathbb H$​。
  $ab^{-1}\mathbb H(ab^{-1})^{-1}=ab^{-1}\mathbb Hba^{-1}=a\mathbb Ha^{-1}=\mathbb H$。
• $\mathbb H\unlhd\text N(\mathbb H)$。直接用正规子群的定义即可。

IV.商

Proof：

设有正规子群 $\mathbb H$​。则 $(a\mathbb H)(b\mathbb H)=a(\mathbb Hb)\mathbb H=a(b\mathbb H)\mathbb H=(ab)\mathbb H$​。（子群积间存在结合律；一个群与其自身的子群积只会得到其自身）。

则可建立满射 $\varphi:a\mapsto a\mathbb H$​​。易证该满射是同态，即陪集构成的集合满同态于母群。因为满同态传递群结构，所以陪集构成的集合成群。

记住这个映射，它会多次出现。

易证满同态传递交换律。

Proof：

设 $|\mathbb G|=pn$。现对每个 $p$ 来说，对于 $n$ 用归纳法。

显然当 $n=1$​ 时 Cauchy 定理成立。

现设对于一切 $k<n$​ 的 $k$​ 来说 Cauchy 定理均成立，下证 Cauchy 定理在阶为 $pn$ 时亦成立。

取 $|\mathbb G|$ 中任一非单位元元素 $a$。

• $|a|$​​ 是 $p$​​​ 的倍数。设为 $s$ 倍，则 $|a^s|=\dfrac{|a|}{\gcd(s,|a|)}=p$。
• $|a|$​ 非 $p$​ 的倍数，则设其为 $m$​。显然应有 $\gcd(m,p)=1$​​。而由 Lagrange 定理的直接推论——群中元素的阶整除群的阶，则有 $m|pn$​，进而 $m|n$​。
  现构造子群 $\mathbb H=\left<a\right>$，则显然 $|\mathbb H|=|a|=m$。因为 $\mathbb G$ 是交换群，所以 $\mathbb H$ 必是正规子群，进而存在商群 $\mathbb G/\mathbb H$，且 $|\mathbb G/\mathbb H|=\dfrac{pn}{m}$。因为 $a$ 非单位元，则 $m>2$，则 $\dfrac nm<n$，由归纳假设 $\mathbb G/\mathbb H$ 中存在 $p$ 阶元 $b\mathbb H$。令 $|b|=r$，则 $(b\mathbb H)^r=b^r\mathbb H=\mathbb H$。因为 $b\mathbb H$ 的阶是 $p$，所以理应有 $p|r$。则可令 $r=pt$，则 $|b^t|=p$。

是不是已经忘记单群是什么了？重申一遍，单群是只有平凡正规子群的群。

V.群同态深入

也有大写的 $\text{Ker}$​ 记法。

$\ker\varphi$ 中元素关于交换律成立的哦。

有没有发现这个定义有些熟悉？没错，它就是 $\varphi(\mathbb G)$。

$\varphi':\mathbb G\rightarrow\Im\varphi$ 显然是满同态，依照我们之前证过的，满同态传递群形态。

这个同态具体是什么？它实际上在我们给出商群的定义的时候就一带给出了！假如 $\mathbb H\unlhd\mathbb G$，则同态 $\tau:\mathbb G\mapsto{\mathbb G/\mathbb H},a\mapsto a\mathbb H$​ 就是自然同态。

$\mathbb{G/H}$ 的单位元显然是 $\mathbb H$，而映到 $\mathbb H$ 的所有元素即为所有 $\mathbb H$​ 中元素。

Proof：

可以构造映射 $\sigma:\mathbb G/\ker\varphi\to\mathbb \Im\varphi,a\ker\varphi\mapsto\varphi(a)$​。

• $\sigma$ 是同态。这很显然，因为 $\tau(a\ker\varphi)\tau(b\ker\varphi)=\varphi(a) \varphi(b)=\varphi(ab)=\tau(ab\ker\varphi)$。
• $\sigma$​​​​ 是单射。$a\ker\varphi=b\ker\varphi\Leftrightarrow a^{-1}b\in\ker\varphi\Leftrightarrow\varphi(a^{-1}b)=\varphi(e)$​​​​。而显然 $\mathbb G/\ker\varphi$​​​​ 中所有的 $a\ker\varphi$​​​​ 都两两不同，故 $\varphi(e)$​​​​ 的原像只可能在 $a\ker\varphi=b\ker\varphi$​​​​ 即 $a^{-1}b=e$ 时产生​​​​，则 $\varphi(e)$​​​ 的原像仅有 $e\ker\varphi$ 一个。我们之前证过，因为 $\varphi(e)$ 是 $\Im\varphi$ 上的单位元，所以其原像唯一即等价于 $\sigma$​​​​ 是单射。
• $\sigma$​​​ 是满射。 对于任何 $a'\in\Im\varphi$​​​，显然必存在 $a$​ 满足 $\varphi(a)=a'$​​。则在 $\sigma$ 中 $a\ker\varphi$​​ 必映射到 $a'$。

又单又满的同态就是同构。

显然生成元的像亦为生成元。

Proof：

依据正规子群在满同态上传递定理，有 $\mathbb H'$ 亦为正规子群。

定义 $\tau:\mathbb{G/H}\to\mathbb{G'/H'},a\mathbb H\mapsto\varphi(a)\mathbb H'$。

• 是映射且是单射（即原像相同等价于像相同）。
  下式中所有式从上到下依次等价。
  $$\begin{matrix}\tau(a\mathbb H)=\tau(b\mathbb H)\\\varphi(a)\mathbb H'=\varphi(b)\mathbb H'\\\varphi(a)\varphi(b)^{-1}\in\mathbb H'\\\varphi(ab^{-1})\in\mathbb H'\\\exists c\in\mathbb H\text{ s.t. }\varphi(c)=\varphi(ab^{-1})\\\varphi(ab^{-1}c^{-1})=\varphi(e)=e'\\ ab^{-1}c^{-1}\in\ker\varphi\leq\mathbb H\\ab^{-1}\in\mathbb H\\a\mathbb H=b\mathbb H\end{matrix}$$
• 是同态。$\tau(a\mathbb Hb\mathbb H)=\tau(ab\mathbb H)=\varphi(ab)\mathbb H'=\varphi(a)\varphi(b)\mathbb H'=\varphi(a)\mathbb H'\varphi(b)\mathbb H'=\tau(a\mathbb H)\tau(b\mathbb H)$​。
• 是满射。显然因为 $\varphi$ 是满射，所以对于每个 $a'\in\mathbb G'$ 均可找到满足 $\varphi(a)=a'$ 的 $a$。则显然对于 $\mathbb{G'/H'}$ 中的每个元素亦可找到其原像。

Proof：

首先要证明 $\mathbb{H/F}$​ 是 $\mathbb{G/F}$​ 的正规子群，即 $\forall(g\mathbb F\in\mathbb{G/F},h\mathbb F\in\mathbb{H/F}),(g\mathbb F)(h\mathbb F)(g\mathbb F)^{-1}\in\mathbb{H/F}$​。首先可以乱交换左右陪集得到要证式子 $ghg^{-1}\mathbb F\in\mathbb{H/F}$​，即证 $ghg^{-1}\mathbb F\in\mathbb H$​，而该条件等价于 $\mathbb H\unlhd\mathbb G$​。

现可构造自然同态 $\tau:\mathbb G\to\mathbb{G/F}$​​​​​。我们证过自然同态的核即为 $\mathbb F$​​，且有 $\tau(\mathbb H)=\mathbb{H/F}$​​。套用前一个定理即证。

首先，$\mathbb F$ 定是 $\mathbb{HF}$ 的正规子群，因为 $\mathbb{HF}$ 是 $\mathbb G$ 的子群。

其次也定有 $\mathbb{H\cap F\unlhd H}$​​​。

构造映射 $\varphi:\mathbb{H\to HF/F},h\mapsto h\mathbb F$​​​。该映射是同态，因为其是自然同态消减定义域的结果。同时其也是满同态，因为对于 $hf\in\mathbb{HF}$，总有 $hf\mathbb F=h\mathbb F$，即消减定义域后值域并没有改变。

显然 $\ker\varphi$ 中的元素应是 $\mathbb F$ 中元素。而其又是 $\mathbb H$ 中元素，所以其为 $\mathbb{H\cup F}$ 中元素。

那么结构就和再前一个定理并无不同了。

Proof：

显然 $\mathbb H\subseteq\varphi^{-1}(\varphi(\mathbb H))$。

显然 $\forall a\in\varphi^{-1}(\varphi(\mathbb H)),\varphi(a)\in\varphi(\mathbb H)$。

则 $\exists b\in\mathbb H,\varphi(a)=\varphi(b)$，则 $\varphi(ab^{-1})=\varphi(e)$，也即 $ab^{-1}\in\ker\varphi\leq\mathbb H$，也即 $a\in\mathbb H$。

这意味着 $\mathbb H\supseteq\varphi^{-1}(\varphi(\mathbb H))$。两者结合即为 $\mathbb H=\varphi^{-1}(\varphi(\mathbb H))$。

Proof：

构造 $\sigma:\mathbb H\mapsto\varphi(\mathbb H)$。由满同态传递群结构得知，$\varphi(\mathbb G)\leq\mathbb G'$。进而可有 $\sigma:\mathbb{M\to M'}$​。

由前一条定理，$\sigma$ 是单射（像相同可推出原像相同）。

对于 $\mathbb M'$ 中所有元素 $\mathbb H'$，考虑其原像集合 $\varphi^{-1}(\mathbb H')$。显然其中必然包含 $\ker\varphi$（其是 $e'$​ 的所有逆——显然 $e'$ 必在一切 $\mathbb H'$​ 中），即其原像集合必然属于 $\mathbb M$。则 $\sigma$ 是满射。

则 $\sigma$ 是双射。

显然其亦保持包含关系。

wiki 说该定理有时被叫做第三或第四同构定理。

在子群对应定理中令 $\varphi$ 为自然同态 $\tau:\mathbb G\to\mathbb{G/N}$​​ 即证。

wiki 说该定理有时被叫做第四同构定理。众所周知，四大同构定理有五个。

可以发现本定理具有特殊的韵律感。因而有人形象地把它称作“蝴蝶引理”。

Proof：

首先 $\mathbb{(A'\cap B)\leq G}$（子群交是子群）。这样之后 $\mathbb{(A'\cap B)\leq A'}\leq\text N(\mathbb A)$。这就意味着 $\mathbb{(A'\cap B)A}=\sum\limits_{x\in\mathbb{(A'\cap B)}}x\mathbb A=\sum\limits_{x\in\mathbb{(A'\cap B)}}\mathbb Ax=\mathbb{A(A'\cap B)}$，即二者的子群积满足交换律。显然同样的交换律在该定理中出现的四个子群积中均成立。

满足交换律的子群积的结果仍是子群，因为我们在证明“正规子群与子群的积结果仍是子群”时，仅用到了两者间的交换律，可以回翻到该定理的证明处复习。

故我们证明了该定理中出现的四个子群积的结果都是子群。可喜可贺可喜可贺（

式子 $\mathbb{(A'\cap B)\unlhd(A'\cap B')}$​ 是我们下一个证明的目标。由正规子群判定定理，即证 $\forall x\in\mathbb{(A'\cap B')},y\in\mathbb{(A'\cap B)}$​，有 $xyx^{-1}\in\mathbb{(A'\cap B)}$​。显然 $x,y\in\mathbb A'$，故 $xyx^{-1}\in\mathbb A'$；因为 $\mathbb{B\unlhd B'}$，而 $x\in\mathbb B',y\in\mathbb B$​，则 $xyx^{-1}\in\mathbb B$；两者结合，上式成立。

式子 $\mathbb{A(A'\cap B)\unlhd A(A'\cap B')}$​​ 是我们再下一个证明的目标。即证 $\forall a,c\in\mathbb A,b\in(\mathbb{A'\cap B’}),d\in(\mathbb{A'\cap B})$​​，有 $abcd(ab)^{-1}\in\mathbb A(\mathbb{A'\cap B})$​​​。上式写成 $abcdb^{-1}a^{-1}$​​ 没有问题。

一个比较棒的想法是将其转成 $a(bcb^{-1})(bdb^{-1})a^{-1}$​ 的形式。然后因为 $\mathbb{A\unlhd A'}$​ 且 $b\in(\mathbb{A'\cap B’})\leq\mathbb A'$​ 且 $c\in\mathbb A$​ 所以即可写成 $ac'(bdb^{-1})a^{-1}$​，其中 $c'\in\mathbb A$​；同理 $d$​ 亦可被转成 $d'=bdb^{-1}$​：因为 $\mathbb{B\unlhd B'}$​ 且 $d\in(\mathbb{A'\cap B})\leq\mathbb B$​ 且 $b\in(\mathbb{A'\cap B’})\leq\mathbb B'$​ 则得 $d'\in\mathbb B$​，因为 $b,d\in\mathbb A'$​ 则得 $d'\in\mathbb A'$​，所以 $d'\in(\mathbb{A'\cap B})$​，式子为 $ac'd'a^{-1}$​。

顺理成章地，写成 $(ac'a^{-1})(ad'a^{-1})$ 的形式。$a,c'\in\mathbb A$ 然后得到 $c''(ad'a^{-1})$。考虑式子 $d'a^{-1}d'^{-1}$，像上面一样地推即可简单转成 $a'\in\mathbb A$，然后知 $d'a^{-1}d'^{-1}=a'$，即 $d'a^{-1}=a'd'$，所以 $c''(ad'a^{-1})=c''aa'd'=c'''d'$，其中 $c'''\in\mathbb A$。显然 $c'''d'\in\mathbb{A(A'\cap B)}$。则 $\mathbb{A(A'\cap B)\unlhd A(A'\cap B')}$ 得证，同构式右边的式子类似可证。

我们终于证明出了本定理的式子没有出现定义错误，可喜可贺可喜可贺（

考虑在本定理的式子中间用 $\mathbb{\dfrac{A'\cap B'}{(A'\cap B)(A\cap B')}}$ 架起桥梁，即如 $\mathbb{\dfrac{A(A'\cap B')}{A(A'\cap B)}\cong\dfrac{A'\cap B'}{(A'\cap B)(A\cap B')}}$ 可证，同构式另一边的式子亦可类似证。

要想这个桥梁成立，必须先有 $\mathbb{(A'\cap B)(A\cap B')\unlhd(A'\cap B')}$ 成立。考虑设 $a\in(\mathbb{A'\cap B'}),b\in(\mathbb{A'\cap B}),c\in(\mathbb{A\cap B'})$，则证 $abca^{-1}\in\mathbb{(A'\cap B)(A\cap B')}$。

老套路啦。$abca^{-1}=(aba^{-1})(aca^{-1})=b'c'$，然后考虑证明 $b'=aba^{-1}$ 和 $c'=aca^{-1}$ 的性质：$a,b\in\mathbb A'$ 故 $aba^{-1}\in\mathbb A'$；$a\in\mathbb B',b\in\mathbb B$ 故 $b'\in\mathbb B$；则 $b'\in(\mathbb{A'\cap B})$，$c'$ 同理，然后知 $\mathbb{(A'\cap B)(A\cap B')\unlhd(A'\cap B')}$。

考虑建立映射 $\varphi:\mathbb{(A'\cap B')\to\dfrac{A(A'\cap B')}{A(A'\cap B)}},a\mapsto a\mathbb{A(A'\cap B)}$​。

考虑 $x\in\mathbb{A'\cap B'}$。$x\in\ker\varphi\Leftrightarrow x\in\mathbb{A(A'\cap B)}=x\in\mathbb{(A'\cap B)A}=\mathbb{A'A\cap BA}=\mathbb{A'\cap BA}$（显然有 $\mathbb{AA'=A'}$；中间用了之前证过的交换律）。

则有 $x\in\mathbb{A'\cap B'\cap BA=(A'\cap B)(A\cap B')}$。显然这是充要条件，因为每条都可以逆推。则 $\ker\varphi=\mathbb{(A'\cap B)(A\cap B')}$。

如果 $\varphi$​​ 是满同态则直接应用第一同构定理即证。同态显然，现考虑证明 $\varphi$​ 是满射。

考虑左陪集 $x\mathbb{A(A'\cap B)}$​。如果对于任何 $x\in\mathbb{A(A'\cap B')=(A'\cap B')A}$​ 都能在该集合中找到一个属于 $(\mathbb{A'\cap B'})$​ 的元素，则 $\varphi$​ 是满射。

设 $x=ab$，其中 $a\in(\mathbb{A'\cap B'}),b\in\mathbb A$。则 $x\mathbb{A(A'\cap B)}=ab\mathbb{A(A'\cap B)}=a\mathbb{A(A'\cap B)}$。显然 $a\in(\mathbb{A'\cap B'})$ 且 $a\in x\mathbb{A(A'\cap B)}$。则 $\varphi(a)=x\mathbb{A(A'\cap B)}$，即 $\varphi$ 是满射。

证毕（累死我了）。

VI.自同构初步

这个定义莫名熟悉，实际上它在正规子群的定义与判定中频繁出现。

Proof：

只需证明 $\varphi\tau_a\varphi^{-1}\in\operatorname{Inn}\mathbb G$​。

令 $\varphi(x)=y$，则 $\varphi^{-1}(y)=x$（因为 $\varphi$ 是双射）。

则 $\varphi\Big(\tau_a\big(\varphi^{-1}(y)\big)\Big)=\varphi\big(\tau_a(x)\big)=\varphi(axa^{-1})=\varphi(a)\varphi(x)\varphi(a^{-1})=\varphi(a)y\varphi(a)^{-1}=\tau_{\varphi(a)}(y)\in\operatorname{Inn}\mathbb G$​。

Proof：

首先可构造满射 $\varphi:\mathbb G\to\operatorname{Inn}\mathbb G,a\mapsto\tau_a$​。易证其是满同态。

考虑恒等自同构 $\epsilon$​​​。 $\tau_a=\epsilon\Leftrightarrow\forall x\in\mathbb G,axa^{-1}=x\Leftrightarrow\forall x\in\mathbb G,ax=xa\Leftrightarrow a\in\text C(\mathbb G)$​​​。

则 $\text C(\mathbb G)=\ker\varphi$​​​​。用第一同构定理即证。

V.群作用

I.群作用初步

• $a\circ x=ax$​（这里的 $ax$​​ 就是普通的乘法）。这种群作用被称作左平移作用。
• $a\circ x=axa^{-1}$​。我们之前说过，这是共轭作用。

II.轨道与稳定子

在各种场合下，轨道可能有诸如 $\mathbb S_x$​、$\text{Orb}(x)$​ 等多种符号语言。这里选取了个人认为最简洁泛用的 $\text O(x)$​​ 写法。

显然 $ex=x$，则 $x\in\mathbb S_x$。

Proof：

设 $\text O(x)\cap\text O(y)\neq\varnothing$​​。则取 $z\in\text O(x)\cap\text O(y)$​​，显然应满足存在 $a,b$​​ 使得 $ax=z=by$​​。

则有 $y=b^{-1}(ax)=(b^{-1}a)x\in\text O(x)$​。

$y\in\text O(x)$​​ 意味着 $y=cx$​​，进而 $dy=dcx$​​，进而 $\text O(y)\subseteq\text O(x)$​​。

交换 $x,y$​​，同理可得 $\text O(x)\subseteq\text O(x)$​​。则 $\text O(x)=\text O(y)$​​。

在其它文章中，稳定子可能有 $\mathbb G_x$​ 等其它符号语言。这里仍选取符合本人喜好的表示方式。

Proof：

• 是映射且是单射，即原像相同等价于像相同。
  $ax=bx\Leftrightarrow b^{-1}ax=x\Leftrightarrow b^{-1}a\in\text{Stab}(x)\Leftrightarrow a\text{Stab}(x)=b\text{Stab}(x)$
• 显然是满射，因为全体 $g$ 显然取到了全体可能的左陪集。

III.群方程

同理，$\text{Cl}(x)$ 也只不过是众多表示方式中比较流行的一种。

共轭类首先是轨道，而轨道是等价类。

依照轨道-稳定子定理简单证。

Proof：

首先，因为共轭类首先是轨道，所以共轭等价类也构成了 $\mathbb G$​ 的分解，即 $|\mathbb G|=\sum\limits_x|\text{Cl}(x)|$。

用轨道-稳定子定理，即得 $|\mathbb G|=\sum\limits_x(\mathbb G:\text C(x))$。

现考虑全体中心中元素。发现显然有中心中元素的共轭类中元素唯一（因为中心元素满足交换律），进而便可将其从 $\sum$ 中提出。

与狭义 Cauchy 定理的不同仅在于这里不要求是交换群。

Proof：

仍归纳。显然在 $2$​ 阶群中广义 Cauchy 定理成立。现设 $<n$​ 阶群中广义 Cauchy 定理均成立。

现考虑群方程定理 $|\mathbb G|=|\text C(\mathbb G)|+\sum\limits_x(\mathbb G:\text C(x))$。

• $p$ 是 $|\text C(\mathbb G)|$ 的因数。显然 $\text C(\mathbb G)$ 是交换群，那么在 $\text C(\mathbb G)$ 中用狭义 Cauchy 定理即可证得其存在 $p$ 阶元素。
• $p$ 非 $|\text C(\mathbb G)|$ 因数。因为 $p$ 是 $|\mathbb G|$ 的因数，所以 $p$ 定非 $\sum\limits_x(\mathbb G:\text C(x))$ 的因数，进而定存在一个 $(\mathbb G:\text C(x))$ 不是 $p$ 的倍数。因为 $(\mathbb G:\text C(x))=|\mathbb G|/|\text C(x)|$，所以 $p$ 必是 $|\text C(x)|$ 的因数。
  显然 $|\text C(x)|$ 是 $\mathbb G$​ 的真子群。则由归纳假设，$\text C(x)$ 存在 $p$ 阶元素。

VI.群作用下计数问题

I.Burnside 引理

Proof：

$$\sum\limits_{g\in\mathbb G}|\text F(g)|=\sum\limits_{g\in\mathbb G}\sum\limits_{x\in\mathbb S}[g\circ x=x]=\sum\limits_{x\in\mathbb S}\sum\limits_{g\in\mathbb G}[g\circ x=x]=\sum\limits_{x\in\mathbb S}|\text{Stab}(x)|=\sum\limits_{x\in\mathbb S}\dfrac{|\mathbb G|}{|\text O(x)|}$$

我们之前证过轨道间要么无交，要么等价。那么在上式求和式中每个不同的 $\text O(x)$ 共出现了 $|\text O(x)|$​​​ 次，于是我们枚举每条本质不同轨道的代表元便得到了

$$\sum\limits_{g\in\mathbb G}|\text F(g)|=\sum\limits_{x\in\mathbb S}\dfrac{|\mathbb G|}{|\text O(x)|}=\sum\limits_{i=1}^n\dfrac{|\mathbb G|}{|\text O(x_i)|}\times|\text O(x_i)|=n|\mathbb G|$$

I.【模板】Pólya 定理

CPP

#include<bits/stdc++.h>
using namespace std;
int T,n;
const int mod=1e9+7;
int ksm(int x,int y=mod-2){
	int z=1;
	for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)z=1ll*z*x%mod;
	return z;
}
int phi(int x){
//	printf("%d:",x);
	int ret=1;
	for(int i=2;i*i<=x;i++){
		if(x%i)continue;
		ret=1ll*ret*(i-1)%mod;
		int tms=-1;while(!(x%i))x/=i,tms++;
		ret=1ll*ret*ksm(i,tms)%mod;
	}
	if(x!=1)ret=1ll*ret*(x-1)%mod;
//	printf("%d\n",ret);
	return ret;
}
int calc(){
	int ret=0;
	for(int i=1;i*i<=n;i++){
		if(n%i)continue;
		(ret+=1ll*ksm(n,i)*phi(n/i)%mod)%=mod;
		if(i*i!=n)(ret+=1ll*ksm(n,n/i)*phi(i)%mod)%=mod;
	}
	return 1ll*ret*ksm(n)%mod;
}
int main(){
	scanf("%d",&T);
	while(T--)scanf("%d",&n),printf("%d\n",calc());
	return 0;
}

II.[HNOI2008]Cards

CPP

#include<bits/stdc++.h>
using namespace std;
int r,g,b,m,n,p,dsu[110],sz[110],f[30][30],res;
int find(int x){return dsu[x]==x?x:dsu[x]=find(dsu[x]);}
void merge(int x,int y){x=find(x),y=find(y);if(x!=y)dsu[y]=x,sz[x]+=sz[y];}
int ksm(int x,int y=p-2){
	int z=1;
	for(;y;y>>=1,x=x*x%p)if(y&1)z=z*x%p;
	return z;
}
int main(){
	scanf("%d%d%d%d%d",&r,&g,&b,&m,&p),n=r+b+g;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++)dsu[j]=j,sz[j]=1;
		for(int j=1,x;j<=n;j++)scanf("%d",&x),merge(j,x);
		memset(f,0,sizeof(f)),f[0][0]=1;
		for(int j=1;j<=n;j++){
			if(dsu[j]!=j)continue;
//			printf("%d\n",sz[j]);
			for(int R=r;R>=0;R--)for(int G=g;G>=0;G--){
				if(R+sz[j]<=r)(f[R+sz[j]][G]+=f[R][G])%=p;
				if(G+sz[j]<=g)(f[R][G+sz[j]]+=f[R][G])%=p;
			}
		}
		(res+=f[r][g])%=p;
	}
	memset(f,0,sizeof(f)),f[0][0]=1;
	for(int j=1;j<=n;j++){
		for(int R=r;R>=0;R--)for(int G=g;G>=0;G--){
			if(R+1<=r)(f[R+1][G]+=f[R][G])%=p;
			if(G+1<=g)(f[R][G+1]+=f[R][G])%=p;
		}
	}
	(res+=f[r][g])%=p;
	printf("%d\n",res*ksm(m+1)%p);
	return 0;
}

III.TRANSP2 - Transposing is Even More Fun

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
const int mod=1e6+3;
int ksm(int x,int y=mod-2){int z=1;for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)z=1ll*z*x%mod;return z;}
int T,n[1001000],res[1001000],all[1001000],pri[1001000],phi[1001000],bit[1001000];
vector<pair<int,int> >v[1001000];
void sieve(){
	phi[1]=1;for(int i=2;i<=N;i++){
		if(!pri[i])pri[++pri[0]]=i,phi[i]=i-1;
		for(int j=1;j<=pri[0]&&i*pri[j]<=N;j++){
			pri[i*pri[j]]=true;
			if(!(i%pri[j])){phi[i*pri[j]]=phi[i]*pri[j];break;}
			phi[i*pri[j]]=phi[i]*phi[pri[j]];
		}
	}
}
int main(){
	sieve();bit[0]=1;for(int i=1;i<=N;i++)bit[i]=(bit[i-1]<<1)%mod;
	scanf("%d",&T);
	for(int i=1,a,b;i<=T;i++){
		scanf("%d%d",&a,&b);
		if(!a||!b)continue;
		all[i]=bit[a+b];
		v[n[i]=(a+b)/__gcd(a,b)].push_back(make_pair(__gcd(a,b),i));
	}
	for(int i=1;i<=N;i++)for(int j=1;i*j<=N;j++)for(auto k:v[i*j])(res[k.second]+=1ll*bit[i*k.first]*phi[j]%mod)%=mod;
	for(int i=1;i<=T;i++)printf("%d\n",(all[i]-1ll*res[i]*ksm(n[i])%mod+mod)%mod);
	return 0;
}

IV.[SDOI2013]项链

Step 1.考虑计算符合条件的珠子数

Step 2.考虑计算符合条件的串数

Step 3.考虑计算 $f$

Step 4.特判

CPP

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int inv6=166666668;
const int N=1e7;
int ksm(int x,int y=mod-2){int z=1;for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)z=1ll*z*x%mod;return z;}
int T,m,p,mu[10010000],pri[10010000],inv[10010000];
ll n;
int calc(int x){return 1ll*x*(x+1)%mod*(x+2)%mod*inv6%mod;}
void sieve(){
	mu[1]=1;for(int i=2;i<=N;i++){
		if(!pri[i])pri[++pri[0]]=i,inv[pri[0]]=ksm(i),mu[i]=-1;
		for(int j=1;j<=pri[0]&&i*pri[j]<=N;j++){
			pri[i*pri[j]]=true;
			if(i%pri[j])mu[i*pri[j]]=-mu[i];
			else{mu[i*pri[j]]=0;break;}
		}
	}
	for(int i=1;i<=N;i++)mu[i]+=mu[i-1];
}
int f(ll n){return (ksm(p-1,n%(mod-1))+(n&1?mod-(p-1):(p-1)))%mod;}
struct dat{
	int a,b;
	dat(int x){a=x/mod,b=x%mod;if(b<0)b+=mod,a--;if(a<0)a+=mod;}
	dat(int x,int y){a=x,b=y;}
	void operator*=(const int&v){a=(1ll*a*v+1ll*b*v/mod)%mod,b=1ll*b*v%mod;}
	void operator*=(const dat&v){a=(1ll*a*v.b+1ll*b*v.a+1ll*b*v.b/mod)%mod,b=1ll*b*v.b%mod;}
	dat operator*(const dat&v){return dat((1ll*a*v.b+1ll*b*v.a+1ll*b*v.b/mod)%mod,1ll*b*v.b%mod);}
	void operator+=(const dat&v){a=(a+v.a+(b+v.b)/mod)%mod,b=(b+v.b)%mod;}
	dat operator+(const dat&v){return dat((a+v.a+(b+v.b)/mod)%mod,b=(b+v.b)%mod);}
	dat operator-(){return dat((mod-a)%mod,(mod-b)%mod);}
};
dat ksm(dat x,ll y=1ll*mod*(mod-1)-1){dat z(1);for(;y;y>>=1,x*=x)if(y&1)z*=x;return z;}
const dat INV6=ksm(dat(6));
dat CALC(int x){return dat(x)*dat(x+1)*dat(x+2)*INV6;}
dat P(0);
dat F(ll n){return ksm(P,n)+(n&1?(-P):P);}
int main(){
	sieve();
	scanf("%d",&T);
	while(T--){
		scanf("%lld%d",&n,&m);
		if(m==1){printf("%d\n",n==1);continue;}
		vector<int>v;ll tmpn=n;
		for(int i=1;i<=pri[0];i++){
			if(tmpn%pri[i])continue;
			v.push_back(i);
			while(!(tmpn%pri[i]))tmpn/=pri[i];
		}
		if(n%mod){
			p=0;
			for(int l=1,r;l<=m;l=r+1)r=m/(m/l),(p+=1ll*calc(m/l)*(0ll+mu[r]-mu[l-1]+mod)%mod)%=mod;
			int invn=ksm(tmpn%mod);
			int res=0;
			for(int i=1;1ll*i*i<=n;i++){
				if(n%i)continue;
				int tmp=(n/i)%mod*f(i)%mod;
				for(auto j:v)if(!((n/i)%pri[j]))tmp=1ll*tmp*(pri[j]-1)%mod*inv[j]%mod;
				if(tmpn!=1&&!((n/i)%tmpn))tmp=(tmpn-1)%mod*tmp%mod*invn%mod;
				(res+=tmp)%=mod;
				if(1ll*i*i==n)break;
				tmp=1ll*i*f(n/i)%mod;
				for(auto j:v)if(!(i%pri[j]))tmp=1ll*tmp*(pri[j]-1)%mod*inv[j]%mod;
				if(tmpn!=1&&!(i%tmpn))tmp=(tmpn-1)%mod*tmp%mod*invn%mod;
				(res+=tmp)%=mod;
			}
			printf("%d\n",1ll*res*ksm(n%mod)%mod);			
		}else{
			P=dat(0);
			for(int l=1,r;l<=m;l=r+1)r=m/(m/l),P+=CALC(m/l)*dat(mu[r]-mu[l-1]);
			P+=dat(-1);
			dat res(0);
			for(int i=1;1ll*i*i<=n;i++){
				if(n%i)continue;
				dat tmp=F(i);
				if((n/i)%mod){
					tmp*=(n/i)%mod;
					for(auto j:v)if(!((n/i)%pri[j]))tmp*=1ll*(pri[j]-1)*inv[j]%mod;
				}else{
					tmp*=(mod-1);
					for(auto j:v)if(!((n/i)%pri[j]))tmp*=1ll*(pri[j]-1)*inv[j]%mod;
				}
				res+=tmp;
				if(1ll*i*i==n)break;
				tmp=F(n/i),tmp*=i;
				for(auto j:v)if(!(i%pri[j]))tmp*=1ll*(pri[j]-1)*inv[j]%mod;
				res+=tmp;
			}
			printf("%d\n",1ll*res.a*ksm(n/mod)%mod);
		}
	}
	return 0;
}

V.[MtOI2018]魔力环

CPP

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int n,m,K,fac[100100],inv[100100],res;
int ksm(int x,int y=mod-2){int z=1;for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)z=1ll*z*x%mod;return z;}
int func(int x,int y){if(!y)return !x;return 1ll*fac[x+y-1]*inv[y-1]%mod*inv[x]%mod;}
int solve(int x,int y){
//	printf("(%d,%d)\n",x,y);
	int ret=0;
	for(int i=0;i*(K+1)<=x&&i<=y;i++){
		int tmp=1ll*func(x-i*(K+1),y)*fac[y]%mod*inv[i]%mod*inv[y-i]%mod;
//		printf("__%d\n",tmp);
		if(i&1)ret=(ret+mod-tmp)%mod;
		else ret=(ret+tmp)%mod;
	}
//	printf("%d\n",ret);
	return ret;
}
int calc(int d){
	int ret=0;
	for(int i=0;i<=min(m/d,K);i++)ret=(1ll*(i+1)*solve(m/d-i,(n-m)/d-1)+ret)%mod;
//	printf("%d:%d\n",d,ret);
	return ret;
}
int pri[100100],phi[100100];
void sieve(){
	phi[1]=1;
	for(int i=2;i<=n;i++){
		if(!pri[i])pri[++pri[0]]=i,phi[i]=i-1;
		for(int j=1;j<=pri[0]&&i*pri[j]<=n;j++){
			pri[i*pri[j]]=true;
			if(i%pri[j])phi[i*pri[j]]=phi[i]*phi[pri[j]];
			else{phi[i*pri[j]]=phi[i]*pri[j];break;}
		}
	}
}
int main(){
	scanf("%d%d%d",&n,&m,&K),K=min(K,n);
	sieve();
//	for(int i=1;i<=n;i++)printf("%d ",phi[i]);puts("");
	if(n==m){puts(K==n?"1":"0");return 0;}
	fac[0]=1;for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod;
	inv[n]=ksm(fac[n]);for(int i=n;i;i--)inv[i-1]=1ll*inv[i]*i%mod;
	for(int i=1;i<=n;i++)if(!(n%i)&&!(m%i))res=(1ll*phi[i]*calc(i)+res)%mod;
	printf("%d\n",1ll*res*ksm(n)%mod);
	return 0;
}

II.Pólya定理

I.[SHOI2006] 有色图

CPP

#include<bits/stdc++.h>
using namespace std;
int n,m,mod,fac[110],inv[110],INV[110],res,sum[110];
int ksm(int x,int y=mod-2){
	int z=1;
	for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)z=1ll*z*x%mod;
	return z;
}
vector<int>v;
int calc(){
	int ret=1,tot=0;
	for(auto i:v)ret=1ll*ret*INV[i]%mod,tot+=i/2;
	for(int i=1;i<=n;i++)if(sum[i])ret=1ll*ret*inv[sum[i]]%mod;
	for(int i=0;i<v.size();i++)for(int j=i+1;j<v.size();j++)tot+=__gcd(v[i],v[j]);
	return 1ll*ret*ksm(m,tot)%mod;
}
void dfs(int lef,int lim){
	if(!lef){(res+=calc())%=mod;return;}
	for(int i=min(lef,lim);i;i--)sum[i]++,v.push_back(i),dfs(lef-i,i),v.pop_back(),sum[i]--;
}
int main(){
	scanf("%d%d%d",&n,&m,&mod);
	fac[0]=1;for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod,INV[i]=ksm(i);
	inv[n]=ksm(fac[n]);for(int i=n-1;i>=0;i--)inv[i]=1ll*inv[i+1]*(i+1)%mod;
	dfs(n,n);
	printf("%d\n",res);
	return 0;
}

II.[HNOI2009]图的同构计数

CPP

#include<bits/stdc++.h>
using namespace std;
const int mod=997;
int n,m,fac[110],inv[110],INV[110],res,sum[110];
int ksm(int x,int y=mod-2){
	int z=1;
	for(;y;y>>=1,x=x*x%mod)if(y&1)z=z*x%mod;
	return z;
}
vector<int>v;
int calc(){
	int ret=1,tot=0;
	for(auto i:v)ret=ret*INV[i]%mod,tot+=i/2;
	for(int i=1;i<=n;i++)if(sum[i])ret=ret*inv[sum[i]]%mod;
	for(int i=0;i<v.size();i++)for(int j=i+1;j<v.size();j++)tot+=__gcd(v[i],v[j]);
	return ret*ksm(2,tot)%mod;
}
void dfs(int lef,int lim){
	if(!lef){(res+=calc())%=mod;return;}
	for(int i=min(lef,lim);i;i--)sum[i]++,v.push_back(i),dfs(lef-i,i),v.pop_back(),sum[i]--;
}
int main(){
	scanf("%d",&n);
	fac[0]=1;for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod,INV[i]=ksm(i);
	inv[n]=ksm(fac[n]);for(int i=n-1;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
	dfs(n,n);
	printf("%d\n",res);
	return 0;
}

VII.某些特殊子群的存在性

I.$p$-群初步

Proof：

由 Cauchy 定理，任何包含非 $p$​ 的质数作为因数的 $|\mathbb G|$​ 都必存在阶为该质数的元素，进而 $p$​-群的阶必然只包含 $p$​ 作为质因数，进而就必是 $p$​ 的非负整数次幂。

Proof：

由轨道-稳定子定理，$|\text O(x)|$ 必是 $|\mathbb G|$ 的因子。

现 $|\mathbb G|$ 为质数，则 $|\text O(x)|$ 要么是 $1$，要么是 $p$ 的正整数幂次。

$\text F(\mathbb G)$​ 是不动元素集，则其中元素的 $|\text O(x)|=1$​​，而不在其中元素的 $|\text O(x)|$ 为 $p$ 的正整数幂次​。

因为轨道是分解，所以 $|\mathbb S|$​ 等于 $|\text F(\mathbb G)|$​ 个阶为 $1$​ 的轨道再并上很多阶为 $p$​ 的幂次的轨道。

那么显然两边同模 $p$ 便得到上式。

Proof：

令 $\mathbb S$ 为 $\mathbb H$ 关于 $\mathbb G$ 的全体左陪集构成的集合，则 $\text S(\mathbb S)$​ 即为其上对称群。

定义 $\tau_a:g\mathbb H\mapsto ag\mathbb H$ 为 $\text S(\mathbb S)$ 中一个置换。

定义同态 $\varphi:\mathbb H\to\text S(\mathbb S),a\mapsto\tau_a$​。则其是一个作用。

显然有 $|\mathbb S|=(\mathbb{G:H})$​。则如果我们可以证明 $\varphi$​ 下的 $\text F(\mathbb H)=\text N(\mathbb H)/\mathbb H$​​​，则应用前一个定理即证。

首先先考虑 $\text F(a)$​，即全体在 $\tau_a$​ 下不变的元素。则应满足 $ag\mathbb H=g\mathbb H$​。

对于 $g\in\text N(\mathbb H)$，有 $ag\mathbb H=a\mathbb Hg$。又 $a$ 是 $\mathbb H$ 中元素，所以 $a\mathbb Hg=\mathbb Hg=g\mathbb H$。

对于 $g\notin\text N(\mathbb H)$​​​​​​​​​​​，必存在 $x\in\mathbb H$​​​​​​​​​​​，满足 $xg\notin g\mathbb H$​​​​​​​​​（即右偏集中必有某个元素不在左陪集中）即 $xg\mathbb H\neq g\mathbb H$​​​​​​​​​​。​​

则 $\text F(\mathbb H)=\text N(\mathbb H)/\mathbb H$​​ ，证毕。

II.Sylow 定理

Proof：

$p^0$ 阶 $p$-子群显然存在，即为 $\{e\}$。

现考虑归纳。现假设 $p^\beta$​ 阶子群（$0\leq\beta<\alpha$）存在，下证 $p^{\beta+1}$​​​ 阶子群存在。

现设 $p^\beta$​ 阶子群是 $\mathbb H$​。则，$(\mathbb{G:H})=\dfrac{|\mathbb G|}{|\mathbb H|}=\dfrac{p^\alpha m}{p^\beta}=p^{\alpha-\beta}m$​。因为 $\beta<\alpha$​，所以 $p|(\mathbb{G:H})$​，进而运用我们之前证过的定理，$p|(\text N(\mathbb H):\mathbb H)$​。

使用 Cauchy 定理在 $\text N(\mathbb H)/\mathbb H$​ 中找到 $p$ 阶元 $a\mathbb H$。考虑循环群 $\left<a\mathbb H\right>$，其容显然为 $p$​，且其中任意两个元素（即两个左陪集）无交。则考虑其中所有左陪集中的所有元素——共有 $p^{\beta+1}$ 个。如果它们构成 $\mathbb G$的子群，则显然就已经归纳成功了。

现考虑证明其是子群。应用子群判定定理，即证：对于任两个该循环群中左陪集 $b\mathbb H,c\mathbb H$​ 中的任两个元素 $x,y$​，存在一个左陪集满足 $xy^{-1}$ 是其中元素。

显然 $y^{-1}\in(c\mathbb H)^{-1}=c^{-1}\mathbb H$。显然 $xy^{-1}\in(b\mathbb H)(c^{-1}\mathbb H)=(bc^{-1})\mathbb H$。显然 $bc^{-1}\mathbb H$​ 是该循环群中的元素。故证毕。

考虑我们构造的方式，就会发现这样构造可以为每个低阶子群构造一个包含其的高阶子群。

Proof：设 $\mathbb{P,Q}\in\text{Syl}_p(\mathbb G)$。考虑 $\mathbb P$ 所有左陪集构成的集合 $\mathbb S$，显然 $|\mathbb S|=\dfrac{|\mathbb G|}{|\mathbb P|}=m$（这里的 $m$ 同上方定义）。

令群 $\mathbb Q$ 左平移作用于 $\mathbb S$。（忘记左平移作用是什么了？Ctrl+F 找一下吧！）按照我们之前证过的定理，$\mathbb S$ 的大小在模 $p$ 意义下同余于不动元素数；而 $|\mathbb S|$ 显然非 $p$ 的倍数，故存在不动元素。则存在 $a\in\mathbb P$ 满足对于一切 $b\in\mathbb Q$，$ba\mathbb P=a\mathbb P$，则 $ba\mathbb Pa^{-1}=a\mathbb Pa^{-1}$，即 $b\in a\mathbb Pa^{-1}$，即 $\mathbb Q\subseteq a\mathbb Pa^{-1}$。显然 $a\mathbb Pa^{-1}$ 是 $\mathbb P$ 的共轭，则 $|a\mathbb Pa^{-1}|=|\mathbb P|=|\mathbb Q|$，则 $\mathbb Q=a\mathbb Pa^{-1}$。

Proof：

按照 Sylow 第二定理，$\text{Syl}_p(\mathbb G)$ 中任两个群共轭；那么，是否有 $\text{Syl}_p(\mathbb G)$ 中任意群的共轭群都属于 $\text{Syl}_p(\mathbb G)$ 呢？（这等价于 $\text{Syl}$ 是一个共轭类）

答案是肯定的，因为 Sylow 第二定理的证明中每一条的逆定理均成立。（自己可以尝试证一下哦）

则 $n_p(\mathbb G)=|\text{Cl}(\mathbb P)|$​​​​​，因为共轭关系具有传递性。

我们证过 $|\text{Cl}(\mathbb P)|=(\mathbb G:\text N(\mathbb P))$，可以翻到“群方程”一节复习。

Proof：

是因数我们已经在上一个定理中证过了。

考虑令 $\mathbb P$​ 共轭作用于 $\text{Syl}_p(\mathbb G)$​。则 $|\text{Syl}_p(\mathbb G)|$​ 同余于该作用的不动元素数（我们在上一节证过该定理）。

考虑证明不动元素唯一。对于每个 $\mathbb Q=a\mathbb Pa^{-1}\in\text{Syl}_p(\mathbb G)$​ 且 $\mathbb Q\neq\mathbb P$​，我们均可以将其作用上 $a^{-1}$​（它一定存在，因为 $\mathbb P$ 是群）以还原出 $\mathbb P$​​。这意味着它们都不是不动元素。而显然 $\mathbb P$​​ 本身是不动元素。则不动元素唯一。

证毕。

INF.结语

update on 2022.2.15：大家似乎都很期待上面的文章啊。为了回应大家的期待，我将在 NOI2022 后 至少更新上述两种理论的一种。如果我有幸拿了 Au，那么 两篇文章都会更新。应该也会向日报投稿。假如不出意外的话，在明年的这个时候，大家应该就能在日报中见到上述续篇之一了。

感谢大家的支持！祝大家学习愉快，有所收获！也祝我自己在接下来的省选和 NOI 中 rp++

update on 2022.8.26：寄了。差 eps 分没拿到 Au。明年再战。

于是只有环论和域论了。

因为 NOI 延期导致更新必然会在开学后，但会更的。

不知道什么时候再见吧。

whk 我的 whk……

update on 2023.8.30

坑已经填完了，可以在 洛谷博客 阅读。

但是因为你谷逆天的 Latex 渲染，只能看到依托炸了的东西。

不准备投日报，除非你谷把渲染修好。

也可以选择渲染更友好的 cnblogs。

借物处：

这份专栏

这篇文章

Visual Group Theory 这本书。

文章编排、定理证明、定理挑选有部分来自于上述材料。