我曾经在极度愤怒的情况下……

\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 运算律}

这一部分是大家在“具体代数”中已经熟知的了。

• 若有 $(A\circ B)\circ C=A\circ(B\circ C)$ ，则称 $\circ$ 运算满足**结合律**。
• 若有 $A\circ B=B\circ A$ ，则称 $\circ$ 运算满足**交换律**。
• 若有 $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$) 运算不一定具有交换律，所以对消去律进行分类是必要的。 当运算具有交换律时，左右消去律总是同时满足或不满足（等价），此时统称为**消去律**。
• 若有 $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 内的一个函数,像可以理解为函数值。

• 称 $\{(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|$ ，即计数的乘法原理。
• 若映射 $f$ 满足 $a≠b\Rightarrow f(a)≠f(b)$ 则称 $f$ 为单射。即不会有两个不同元素的像相同。
• 若映射 $f:A\rightarrow B$ 满足对任意 $b\in B$ 都存在 $a\in A$ 使得 $f(a)=b$，则称 $f$ 为满射。 即 $A$ 中元素的像布满整个 $B$。（值域是 $B$）
• 即是单射又是满射的映射称为双射，又称为一一映射。可以认为是 $A$ 中元素和 $B$ 中元素的“匹配(配对)”。 - 小性质 ： 若 $A,B$ 之间存在双射,则 $|A|=|B|$。构造双射进行转化是解决计数问题的重要手段。
• 定义和函数的复合相同。 - 性质 ： 单射的复合仍是单射，满射的复合仍是满射，双射的复合仍是双射。

• 群论的一些基础知识就略去了，也可以见 群论小记。

\color{blue}\text{\bf 环和域 : 概论}

这一节一开始会有一点背书的感觉，是因为这些定义和性质还没有投入应用层，请耐心等待片刻。

• 对于集合 $R$ ，以及运算 $+,\times$ ，若满足以下三条性质 ： 1. $(R,+)$ 是交换群。 2. $(R,*)$ 满足封闭性和结合律。 3. 在 $R$ 中 ，$\times$ 对 $+$ 的左右分配律均成立。 则称 $R$ 关于 $+,\times$ 成环，记作 $(R,+,\times)$。 称加群中（而非乘群中）的单位元为 $0$ 元，加群中的逆元改称负元。（以免称谓不清）
• 对于环 $(R,+,\times)$ , 若 $a\in R,n\in Z^+$ ，称 $\quad na=\overbrace{a+a+...+a}^{\text{共n个}}

  为 a 的 n 倍。若 n\in Z^- 可以看作先数乘正数再取负元。

  容易验证数乘具有分配律等，（部分）交换律等运算律。

  为了避免误会，代表“数”而非环中元素的符号可能会用 \color{blue}\text{蓝色} 来标记。

• 设 $R$ 是一个环，若 $a,b$ 是两个非零元，且 $ab=0$。 则称 $a$ 是左零因子， $b$ 是右零因子。若一个元同时为左右零因子，则简称为零因子。 **例** ：在经典 $+,\times$ 下，$Z$ 没有 $0$ 因子，而 $Z_8$ 中有 $2*4=0\pmod 8$。
• 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$ , 即可逆元总不是零因子。
• 对于一个环，若其关于乘法成交换群，则称为域。 或者说，交换除环称为域。 不难感知，域的性质是非常好的，常见的一些运算律都可以放心大胆地使用。 下面是一些环分类的例子 ： $$ \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)
• - **定理** : 一个至少有两个元的无零因子**有限**环是除环。 **证明** ： 该命题等价于 ： （有限集合）满足封闭性，结合律，消去律的即是群。 设 $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 ，无贡献。

  对于环 (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) $$\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$ 这个根，矛盾。