近世代数乱编

我曾经在极度愤怒的情况下…… # $\mathscr P\!art\ 1$ ：抽象代数 ### $\color{blue}\text{\bf 代数运算}$ 下面用 $\circ,\otimes,\oplus$ 等来代指某种代数运算。本文中所涉及的运算多为二元运算。 本质上是个映射，$A\circ B=C$ 的意思就是 $\times$ 运算将 $(A,B)$ 映射到 $C$。 需要定义值域 $U$ ，即能参与运算的 $A\circ B$ 中 $A,B$ 的范围。 ### $\color{blue}\text{\bf 运算律}$ 这一部分是大家在“具体代数”中已经熟知的了。 - $\color{blue}\bf\Delta$**结合律** 若有 $(A\circ B)\circ C=A\circ(B\circ C)$ ，则称 $\circ$ 运算满足**结合律**。 - $\color{blue}\bf\Delta$**交换律** 若有 $A\circ B=B\circ A$ ，则称 $\circ$ 运算满足**交换律**。 - $\color{blue}\bf\Delta$**消去律** 若有 $A≠0,A\circ B=A\circ C\Rightarrow B=C$ ，则称 $\circ$ 运算满足**左消去律**。(我们消去了 $\circ$ 左侧的 $A$) 若有 $A≠0,B\circ A=C\circ A\Rightarrow B=C$ ，则称 $\circ$ 运算满足**右消去律**。(我们消去了 $\circ$ 右侧的 $A$) 运算不一定具有交换律，所以对消去律进行分类是必要的。 当运算具有交换律时，左右消去律总是同时满足或不满足（等价），此时统称为**消去律**。 - $\color{blue}\bf\Delta$**分配律** 若有 $C\otimes (A\oplus B)=(C\otimes A)\oplus(C\otimes B)$ ，则称 $\otimes$ 运算对 $\oplus$ 满足**左分配律**。 (我们将 $\otimes$ 左侧的 $C$ 分配给了右侧的 $A,B$ ) 若有 $(A\oplus B)\otimes C=(A\otimes C)\oplus(B\otimes C)$ ，则称 $\otimes$ 运算对 $\oplus$ 满足**右分配律**。 (我们将 $\otimes$ 右侧的 $C$ 分配给了左侧的 $A,B$ ) 当运算具有交换律时，两者等价，统称为**分配律**。 上面的定义均未说明运算所定义的集合，更严谨的表达为 ： 运算 $\circ$ 在集合 $S$ 上具有 ……律。 脱离所定义的集合，运算的性质只是空谈。 **例** ：在 $R$ 上，$+,\times$ 运算显然具有交换律，结合律，消去律。且 $\times$ 对 $+$ 具有分配律。 ### $\color{blue}\text{\bf 映射}$ 设 $f : A\rightarrow B$ 为集合 $A$ 和 $B$ 中的一种对应关系。 即 ： 对于 $u\in A$ ，则有确定的一个 $f(u)\in B$。称 $f(u)$ 为 $u$ 在 $f$ 作用下的像。 也可以将 $f$ 理解为定义在 $A$ 上，取值在 $B$ 内的一个函数,像可以理解为函数值。 - $\color{blue}\bf\Delta$**笛卡尔积** 称 $\{(a_1,a_2...a_n)\|a_1\in A_1,a_2\in A_2,...a_n\in A_n\}$ 为集合 $A_1,A_2...A_n$ 的笛卡尔积。 记作 $A_1\times A_2\times...\times A_n$。 也就是从每个集合中各取一个元素形成有序多元组的集合。 **例** ：若 $A=\{a,b,c\},B=\{1,2\}$ ，则 $A\times B=\{(a,1),(a,1),(b,1),(b,2),(c,2),(c,2)\}$。 - 小性质 ： $|A\times B|=|A|\times |B|$ ，即计数的乘法原理。 - $\color{blue}\bf\Delta$**单射** 若映射 $f$ 满足 $a≠b\Rightarrow f(a)≠f(b)$ 则称 $f$ 为单射。即不会有两个不同元素的像相同。 - $\color{blue}\bf\Delta$**满射** 若映射 $f:A\rightarrow B$ 满足对任意 $b\in B$ 都存在 $a\in A$ 使得 $f(a)=b$，则称 $f$ 为满射。 即 $A$ 中元素的像布满整个 $B$。（值域是 $B$） - $\color{blue}\bf\Delta$**双射** 即是单射又是满射的映射称为双射，又称为一一映射。可以认为是 $A$ 中元素和 $B$ 中元素的“匹配(配对)”。 - 小性质 ： 若 $A,B$ 之间存在双射,则 $|A|=|B|$。构造双射进行转化是解决计数问题的重要手段。 - $\color{blue}\bf\Delta$**映射的复合** 定义和函数的复合相同。 - 性质 ： 单射的复合仍是单射，满射的复合仍是满射，双射的复合仍是双射。 - 群论的一些基础知识就略去了，也可以见 [群论小记](https://www.luogu.com.cn/blog/command-block/qun-lun-xiao-ji)。 ### $\color{blue}\text{\bf 环和域 : 概论}$ 这一节一开始会有一点背书的感觉，是因为这些定义和性质还没有投入应用层，请耐心等待片刻。 - $\color{blue}\bf\Delta$**环** 对于集合 $R$ ，以及运算 $+,\times$ ，若满足以下三条性质 ： 1. $(R,+)$ 是交换群。 2. $(R,*)$ 满足封闭性和结合律。 3. 在 $R$ 中 ，$\times$ 对 $+$ 的左右分配律均成立。 则称 $R$ 关于 $+,\times$ 成环，记作 $(R,+,\times)$。 称加群中（而非乘群中）的单位元为 $0$ 元，加群中的逆元改称负元。（以免称谓不清） - $\color{blue}\bf\Delta$**数乘** 对于环 $(R,+,\times)$ , 若 $a\in R,n\in Z^+$ ，称 $\quad na=\overbrace{a+a+...+a}^{\text{共n个}}$ 为 $a$ 的 $n$ 倍。若 $n\in Z^-$ 可以看作先数乘正数再取负元。 容易验证数乘具有分配律等，（部分）交换律等运算律。 为了避免误会，代表“数”而非环中元素的符号可能会用 $\color{blue}\text{蓝色}$ 来标记。 - $\color{blue}\bf\Delta$**零因子** 设 $R$ 是一个环，若 $a,b$ 是两个非零元，且 $ab=0$。 则称 $a$ 是左零因子， $b$ 是右零因子。若一个元同时为左右零因子，则简称为零因子。 **例** ：在经典 $+,\times$ 下，$Z$ 没有 $0$ 因子，而 $Z_8$ 中有 $2*4=0\pmod 8$。 - $\color{blue}\bf\Delta$**环的分类** 1. 若环中的乘法有交换律，则称为**交换环**。 定理 : 在交换环中，二项式定理成立。 （证明考虑归纳） 2. 若含有乘法单位元，则称为(含)**幺($y\bar{a}o$)环** 3. 若不含零因子，则称为**无零因子环** 定理 : 环不含零因子 $\Leftrightarrow$ 乘法消去律成立。 4. 同时满足上述三条，则称为**整环**。 5. **除环**需要满足下列两条性质 ： 1. 是幺环。 2. 每个非零元都有逆元。 定理 ： 除环是无零因子环。 证明 ： 若 $a$ 可逆, 即存在 $b$ 使 $ab = ba = 1$。 若 $c$ 使得 $ac=0$, 则有 $c = bac = 0$。 类似的, 若 $ca = 0$, 有 $c = cab = 0$。 因此与可逆元相乘得 $0$ 的只有 $0$ , 即可逆元总不是零因子。 - $\color{blue}\bf\Delta$**域** 对于一个环，若其关于乘法成交换群，则称为域。 或者说，交换除环称为域。 不难感知，域的性质是非常好的，常见的一些运算律都可以放心大胆地使用。 下面是一些环分类的例子 ： $$ \begin{matrix} &\text{交换环}&\text{幺环}&\text{无零因子环}&\text{整环}&\text{除环}&\text{域}\\ \\ Q,R,C&\sqrt{}&\sqrt{}&\sqrt{}&\sqrt{}&\sqrt{}&\sqrt{}\\ \\ Z&\sqrt{}&\sqrt{}&\sqrt{}&\sqrt{}&\times&\times\\ \\ \text{矩阵环}M_n&\times&\sqrt{}&\times&\times&\times&\times\\ \\ \text{同余系}Z_n&\sqrt{}&\sqrt{}&\times&\times&\times&\times\\ \\ \text{剩余类}Z_p&\sqrt{}&\sqrt{}&\sqrt{}&\sqrt{}&\sqrt{}&\sqrt{}\\ \\ \text{偶数集} 2Z&\sqrt{}&\times&\sqrt{}&\times&\times&\times\\ \\ \end{matrix} $$ **例** ： 我们做题时，遇到 $F_p$ 下无 $w$ 的二次剩余的情况，往往会把数改造成类似复数的 $a+b\sqrt{w}$ 的形式。 此时 $R=\{a+b\sqrt{w}|a,b\in Z_p\}$ 关于模意义下的加乘是域。这个技巧又被称为扩域。 如 [P5320 [BJOI2019]勘破神机](https://www.luogu.com.cn/problem/P5320) - $\color{blue}\bf\Delta$**环的特征** - **定理** : 一个至少有两个元的无零因子**有限**环是除环。 **证明** ： 该命题等价于 ： （有限集合）满足封闭性，结合律，消去律的即是群。 设 $R=\{a_1,a_2,...a_n\}$ ,对于某个 $a\in R$ 构造 $aR=\{aa_1,aa_2,...aa_n\}$ 由消去律 $a≠0,ab=ac\Leftrightarrow b=c$ 即 $a≠0,ab≠ac\Leftrightarrow b≠c$。所以 $aR$ 中元素是互异的。进一步地 ，$|aR|=|R|$。 由于封闭性，又有 $aR\subseteq R$ ,所以 $aR=R$。 这样，对于任意的 $a\in R$ ，都存在 $1=aa_k\in aR$ ,即逆元。 **附** : 注意，对于无限集合便不能这么做，如 $(Z,\times)$ ，满足封闭性，结合律，消去律，但不是群。 - **定理** : 一个无零因子环中，所有（非零）元素在加法群中的阶都相同。 **证明** ： 设有 $0≠a\in R$ ,且 ${\rm ord}(a)=k$ ，即 ${\color{blue}k}a=0$ (数乘) 对于另一个 $0≠b\in R$ ,有 $({\color{blue}k}a)b=({\color{blue}k}b)a=0$ 。 又因为无零因子，所以必然只有 ${\color{blue}k}b=0$ ,这说明 ${\rm ord}(b)|k$ 即 ${\rm ord}(b)\leq k$。 反过来也有 ${\rm ord}(a)\leq {\rm ord}(b)$ ,所以只能是 ${\rm ord}(a)={\rm ord}(b)$。 这个统一的阶数称为特征。 所以,若特征为 $p$ ,对于数乘运算有 ${\color{blue}k}a=({\color{blue}k\bmod p})a$ - **定理** ： 若一个环的特征值有限，则必为素数。 **证明** ： （反证）若 ${\rm ord}(a)$ 可以分解为 $n_1n_2\ (n_1,n_2>1)$ ,这说明 ${\color{blue}n_1}a≠0,{\color{blue}}n_2a≠0$。 然而 $({\color{blue}n_1}a)({\color{blue}n_2}a)=({\color{blue}n_1}{\color{blue}n_2}a)a=0a=0$ ，结合无零因子性。这说明 ${\color{blue}n_1}a,{\color{blue}n_2}a$ 中至少一个为 $0$。 - **定理** ： 在一个特征为 $p$ 的交换环中，有 $(a+b)^p=a^p+b^p$。 **证明** ： 使用二项式定理得： $(a+b)^p=\sum\limits_{i=0}^p\dbinom{p}{i}a^ib^{p-i}$ $=a^p+b_p+\sum\limits_{i=1}^{p-1}\dbinom{p}{i}a^ib^{p-i}$ - 小结论 ：对于素数 $p$ 以及任意的 $i\in[1,p-1]$ ，都有 $p|\binom{p}{i}$ 即 $\binom{p}{i}\bmod p=0$。 证明 ：$\dbinom{p}{i}=\dfrac{p!}{i!(p-i)!}$ ,而显然 $i,p-i<p$ ，它们的阶乘必然不含因子 $p$ ，也就无法消掉上面 $p!$ 中的恰好一个因子 $p$。 这样，后面的求和都数乘了 $0$ ，无贡献。 - $\color{blue}\bf\Delta$**子环** 对于环 $(R,+,\times)$ ，若有 $S\subseteq R$ 使得 $(S,+,\times)$ 是环，则称后者是前者的子环。 类似地有子除环，子域等。 ### $\color{blue}\text{\bf 多项式环}$ 摸爬滚打了一阵之后，对幂级数运算的合法性有了更深的的理解。 发现啥也看不懂，应用层断裂，这部分咕了。 # $\mathscr P\!art\ 2$ ：高等代数--多项式相关 这部分的东西就比较杂乱了，等到学的东西多了再来整理吧。 ### $\color{blue}\text{\bf 分圆多项式}$ 众所周知，$n$ 次单位根 $w_n^0,w_n^1,w_n^2...w_n^{n-1}$ 是方程 $x^n-1=0$ 的所有根。 能够推知 $\prod\limits_{i=0}^{n-1}(x-w_n^i)=x^n-1$。 - **定义** ： 对于复数 $z$ ，若有 $z^n=1$ 且 $z^m≠1\ (m\in [0,n)∩Z)$ ，即 $z$ 的阶恰好为 $n$ ，则称 $z$ 为 $n$ 次**本原单位根**，可以类比原根理解。 定义**分圆多项式** $\Phi_n(x)=\prod\limits_{i=0}^{n-1}(x-w_n^i)^{\small [i\perp n]}$ ，即根恰为所有 $n$ 次本原单位根。 - **定理** ： $\prod\limits_{d|n}\Phi_d(x)=x^n-1$。 **证明** ： 上式意味着 $\prod\limits_{d|n}\Phi_d(x)$ 不重不漏地涉及了所有的 $n$ 次单位根。 当复数 $z$ 的阶为 $d$ 时，其是任意的 $kd$ 次单位根。 所以，阶为 $n$ 的因数的单位根必然是 $n$ 次单位根。 另一方面，不难发现 $|\Phi_d(x)|=\varphi(d)$ ，考察等式两边多项式的次数，可得 $\sum\limits_{d|n}\varphi(d)$ 和 $n$ ，两者已经相等，说明没有遗漏单位根。 由上述定理可得到一种 $\Phi_d(x)$ 的计算方法。 取对数可得 $$\sum\limits_{d|n}\ln \Phi_d(x)=\ln (x^n-1)$$ 使用莫比乌斯反演 $$\ln \Phi_n(x)=\sum\limits_{d|n}\ln (x^d-1)\mu(n/d)$$ $\exp$ 回去 $$\Phi_n(x)=\prod\limits_{d|n}(x^d-1)^{\mu(n/d)}$$ - **定理** ： 分圆多项式必为整系数多项式。 好像要本原多项式和高斯定理那一套，先不证了。 - **定理** ： 分圆多项式在 $Q$ 上不可约。 好像很难的样子，根本不会证…… 这说明分圆多项式恰好给出 $x^n-1$ 在 $Q$ 上的分解。 应用(模板) ：[P1520 因式分解](https://www.luogu.com.cn/problem/P1520) - **定理** ： 在 $\pmod{\Phi_n(x)}$ 意义下， $x$ 的阶恰为 $n$。 **证明** ： 首先显然有 $\Phi_n(x)|(x^n-1)$ ，则 $x^n-1=0\pmod {\Phi_n(x)}$ 即 $x^n=1\pmod {\Phi_n(x)}$。 然后，对于任意的 $m<n$ 若有 $x^m=1\pmod {\Phi_n(x)}$ ，则有 $\Phi_n(x)|(x^m-1)$。 考虑 $w_n$ ，显然这是个 $n$ 次本原单位根。 此时 $(x-w_n)|\Phi_n(w_n)$ ，但是 $(x^m-1)$ 显然没有 $w_n$ 这个根，矛盾。