代数学基础

返回笔记目录

1 预备知识

1.1 集合与映射

1.1.1 集合初步

$A\subseteq B/B\supseteq A:\forall a\in A,a\in B$

$A\subset B$ ，则 $A\subseteq B$ 且 $A\not=B$

$A$ 中元素有限，则记 $A$ 的阶 $|A|=\operatorname{card}A$ 为 $A$ 中元素的个数

1.1.2 集合运算

$\cup:$ 并集
$\sqcup:$ 不交并集

$A=(A\setminus B)\sqcup(A\cap B)$

$A\subseteq U$
$A^c:=\complement_UA$

1.1.3 容斥原理

$|A\cup B|=|A|+|B|-|A\cap B|$

$A_i\subseteq U,i\in I\Rightarrow\bigcap\limits_{i\in I}A_i^c=(\bigcup\limits_{i\in I}A_i)^c$

1.1.4 笛卡尔积

$\operatorname{def}A\times B=\{(a,b)\mid a\in A,b\in B\}$

1.1.5 常用符号

$\mathbb{Z_+,N,Z,Q,R}$
$F[X]$ 表示 $F(F$ 为 $\mathbb{Z,Q,R\dots}$ 中的一个$)$ 上的多项式（一元）的集合

1.1.6 映射

定义：

• $f:A\rightarrow B,a\mapsto b=f(a)$
• $\verb|also | A\overset{f}{\rightarrow}B$
• $f(a)=b$，则 $a$ 称为 $b$ 的一个原相

复合

1. 定义 $(f\circ g)(x)=f(g(x))$
2. 性质 $(f\circ g)\circ h=f\circ(g\circ h)$

单射，满射，双射

1. 若 $a\not ={b}$ 则 $f(a)\not ={f(b)}$， 则 $f$ 是单射
2. 若 $\forall b\in B,\exists a\in A$ 使得 $f(a)=b$，则 $f$ 是满射
3. 若 $f$ 又单又满，则 $f$ 称为一一映射

1.1.7 二元运算

$f:S\times S\rightarrow S,(a,b)\mapsto p$ 为 $S$ 上的二元运算

性质

1. 交换律 $f(a,b)=f(b,a)$
2. 结合律 $f(f(a,b),c)=f(a,f(b,c))$

例子

1. 记 $\sum_A$ 表示 $A\rightarrow A$ 的所有映射的集合，则映射的复合构成 $\sum_A$ 上的二元运算
   $\sum_A\times\sum_A\rightarrow\sum_A,(a_x,a_y)\mapsto b=a_x\circ a_y$
2. 记 $S_A$ 表示 $A\rightarrow A$ 的所有映射的集合，则映射的复合构成 $S_A$ 上的二元运算
   $S_A\subseteq\sum_A$

1.1.8 等价关系

$\operatorname{def} A\sim B$

性质

1. 自反性 $a\sim a$
2. 对称性 $a\sim b\Rightarrow b\sim a$
3. 传递性 $a\sim b,b\sim c\Rightarrow a\sim c$

等价类

• $[a]=\{b\in A\mid a\sim b\}$
• $$[a]\cap[b]=\begin{cases} [a]=[b]&\verb|if |a\sim b\\ \varnothing&\verb|otherwise| \end{cases}$$

分拆

• $A/\sim:=\{[a]\mid a\in A\}$
• $A=\bigsqcup\limits_{[a]\in A/\sim}[a]$
• 此时 $A/\sim$ 称为 $A$ 的一个分拆。
• 这说明，集合 $A$ 上的等价分拆与定义在 $A$ 上的等价关系一一对应

函数

• $b\not=b'\Leftrightarrow f^{-1}(b)\cap f^{-1}(b')=\varnothing$
• $f^{-1}(b)=\varnothing$ 当且仅当 $b\notin f(A)$
• 定义 $A=\bigsqcup\limits_{b\in f(A)}f^{-1}(b)$ 为 $f$ 的原像
• 这个分拆决定的等价关系是：$a\sim a'\Leftrightarrow f(a)=f(a')$

1.2 求和&求积 符号

$\sum\limits_{i=1}^{n}a_i=a_1+a_2+\cdots+a_n$
$\prod\limits_{i=1}^{n}a_i=a_1a_2\cdots a_n$

$\sum\limits_{i\in I}a_i$ 和 $\prod\limits_{i\in I}a_i$ 亦可

性质

1. $\sum\limits_{i\in I}x=x|I|$
2. $\prod\limits_{i\in I}x=x^{|I|}$
3. $I=I_1\sqcup I_2\Rightarrow\sum\limits_{i\in I}a_i=\sum\limits_{i\in I_1}a_i+\sum\limits_{i\in I_2}a_i,\prod\limits_{i\in I}a_i=\prod\limits_{i\in I_1}a_i\cdot\prod\limits_{i\in I_2}a_i$

1.2.1 容斥原理

$$|A_1\cup A_2\cup\cdots\cup A_n|=\sum_{j=1}^{n}(-1)^{j-1}\sum_{\{i_1,\cdots,i_j\}\in\{1,\cdots,n\}}|A_{i_1}\cap\cdots\cap A_{i_j}|$$

1.2.2 牛顿二项式定理

$(x+y)^n=\sum\limits_{k=0}^{n}\binom{n}{k}x^ky^{n-k}$

1.2.3 阿贝尔变换 (Abel transformation / 分部求和)

令 $\sum\limits_{i=1}^{k}a_i=S_k$ 以及 $S_0=0$

1.3 复数

$c\in\mathbb C:c=x+yi$

$\verb|Re|c=x,\verb|Im|c=y$

加减乘除，结合律交换律

纯虚数 $=\{yi\mid y\in\mathbb N,y\not=0\}$

$x+yi=r(\cos\theta+i\sin\theta),r=\sqrt{x^2+y^2},\tan\theta=\frac{y}{x}$

$r_1e^{i\theta_1}\cdot r_2e^{i\theta_2}=r_1r_2e^{i(\theta_1+\theta_2)}$

$\omega_n^k=e^{i\cdot\frac{2k\pi}{n}}$ 为 $n$ 次单位根

$\{z\in\mathbb C\mid z^n=1\}=\{e^{i\cdot\frac{2k\pi}{n}}\mid k=0 ,2,3,\cdots,n-1\}$

2 群环域

2.1 基本定义

2.1.1 知识梳理

1. $f:S\times S\rightarrow S$ 称为 $S$ 上的二元运算
2. 映射 $f:A\rightarrow B$ 决定的分拆 $A=\bigsqcup\limits_{b\in f(A)}f^{-1}(b)$，其中 $f^{-1}(b)$ 为 $b$ 的原像集
3. 满足以下三个条件为群（满足(1)为半群，满足(1)(2)为含幺半群）
   • (1) 结合律：$\forall a, b, c\in G, (a\circ b)\circ c=a\circ(b\circ c)$
   • (2) 幺元：$\exists 1\in G,1\circ a=a\circ 1=a$
   • (3) 逆元：$\forall a\in G,\exists a^{-1}\in G$ 使得 $a\circ a^{-1}=a^{-1}\circ a=1$
4. Abel 群（交换群）：满足交换律 $a\circ b=b\circ a$ 的群 $G$ 称为 Abel 群
5. 对称群（置换群）：记 $M_A=\{f\mid f:A\rightarrow A\}$（自己到自己的映射组成的集合），$S_A$ 为其中一一对应的映射组成的集合。那么在映射复合 $\circ$ 意义下， $M_A$ 是含幺半群但不是群，$S_A$ 是群，$S_A$ 被称为对称群（置换群）
6. 子群：如果 $H\subseteq G$，且 $H$ 关于群 $G$ 的运算成群，则称：$H$ 为 $G$ 的子群，记作 $H\le G$
7. $H\le g\Leftrightarrow\forall a,b\in H, ab^{-1}\in H$
   证明：正方向显然。反方向：
   1. 取 $b=a$ 则 $ab^{-1}=1\in H$（有幺元）
   2. 取 $a=1$ 则 $ab^{-1}=b^{-1}\in H$（有逆元）
   3. 取 $b=y^{-1}$ 则 $ab^{-1}=ay\in H$（乘积在 $H$ 中）
8. 群的直积 $G=G_1\times G_2$
   令 $(a_1,b_1)\circ(a_2,b_2)=(a_1 a_2,b_1 b_2)$
   则 $G$ 关于 $\circ$ 成群，为 $G_1,G_2$ 的直积
9. $R$ 为环，当且仅当 $R$ 为 $+$ Abel 群和 $\times$ 幺半群，且 $R$ 中存在分配率 $\lambda(a+b)=\lambda a+\lambda b,(a+b)\lambda=a\lambda+b\lambda$
   若 $R$ 同时有乘法交换律，则称 $R$ 为交换环
10. 若环 $R$ 满足 $R-\{0\}$ 为 $\times$ Abel 群则为域
11. 环 $R$ 上的单位群 $R^{\times}=\{g\mid g$ 有乘法逆元 $\}$
12. Gauss 整数环 $\mathbb Z[i]=\{a+bi\mid a,b\in\mathbb Z\}$
    Gauss 数域 $\mathbb Q[i]=\{a+bi\mid a,b\in\mathbb Q\}$
13. 四元数 $\mathbb H=\left\{\left(\begin{matrix}a&b\\-b&a\end{matrix}\right)\mid a,b\in\mathbb C\right\}$ 在矩阵加乘法下构成环，且 $\mathbb H^{\times}=\mathbb H-\{0\}$ 为乘法群
14. 环 $\mathbb R$ 为域 $\Leftrightarrow$ 单位群 $\mathbb R^{\times}=\mathbb R-\{0\}$ 且为 Abel 群

3 整数理论

$1. 基本事实：\boxed{非空正整数集合总有最小元}$ $2. 传递性：\boxed{a|b,b|c\Rightarrow a|c}$
$3. 线性组合性：\boxed{a|b,a|c\Rightarrow a|nb+mc}$

3.1 整除

3.1.1 带余除法

$\operatorname{Def.}$ 如果存在 $c\in Z$ 使 $a=bc$ 则称 $b$ 整除 $a$，记作 $b|a$

$a,b\in\mathbb Z,b\not=0,$ 则 $\exists q,r\in\mathbb Z$ 使得 $a=bq+r,0\le r<|b|$ 且 $q,r$ 唯一

1. 存在性：$I=\{a-bk\mid k\in\mathbb Z\}$
   $k=-2b|a|$
   $a-kb=a+2b^2|a|\ge b^2|a|\ge 0$
   $\therefore I\cap\mathbb N\not=\varnothing$
   则 $0\le r=\min(I\cap\mathbb N)<|b|$
   否则，$r\ge|b|$ 则 $r-|b|\ge0$ 矛盾
2. 唯一性：若 $a=q_1b+r_1=q_2b+r_2$ 则 $(q_1-q_2)b=r_1-r_2\Rightarrow b|(r_1-r_2)$
   $\therefore-|b|<r_1-r_2<|b|\Rightarrow r_1=r_2\Rightarrow q_1=q_2$

3.1.2 最大公因子

$d=(a,b)$ 当且仅当

1. $d|a,d|b$
2. 若 $d'|a,d'|b$ 则 $d'\le d$

$a,b$ 互质当且仅当 $(a,b)=1$

性质：

1. $(\pm a,\pm b)=(a,b)$
2. $(a,b)=(b,a)$
3. $a\not=0$ 则 $(a,a)=(a,0)=|a|$
4. $(a,b)=(a+by,b)=(a,b+ax)$

$I=\{ax+by\mid x,y\in\mathbb Z\},d\mathbb Z=\{dz\mid z\in\mathbb Z\}$ 证明 $I=d\mathbb Z$：

1. 设 $d_1$ 为 $I$ 中最小元素，则 $d|d_1$，$d\le d_1$ ，若 $d_1\not|a$ ，设 $a=qd_1+r$，则 $r=a-qd_1=a(1-qx)+b(-qy)\in I$，矛盾，所以 $d_1|(a,b)$ ，则 $d_1\le d$ ，故 $d_1=d$
2. $d\mathbb Z\subseteq I,I\subseteq d\mathbb Z$

性质：

1. $d|a,d|b\Rightarrow d|(a,b)$
2. $m>0$ 则 $m(a,b)=(ma,mb)$
3. $(a,b)=d$ 则 $\left(\frac{a}{d},\frac{b}{d}\right)=1$
4. $(a,m)=(b,m)=1$ 则 $(ab,m) = 1$
5. $c|ab,(c,b)=1\Rightarrow c|a$

3.1.3 辗转相除

$\Theta(\log \max\{a,b\})$ 时间内求出 $\gcd$

3.1.4 lcm

1. $[a, b]\cdot(a,b)=|ab|$
2. $a|[a,b],b|[a,b]$
3. $[a,b]=[b,a]$
4. $[ma,mb]=|m|[a,b]$

3.2 素数，算数基本定理

素数：$d|p$ 当且仅当 $d=1/d=p$

算数基本定理：每个不等于 $1$ 的正整数都可以分解为有限个素数的积，且唯一

也可表示为 $n=\operatorname{sgn}(n)\cdot\prod\limits_{p\in\operatorname{primes}}p^{v_p(n)}$（且分解唯一），这称为 $n$ 的因式分解

4 整数的同余理论

4.1 同余式

4.1.1 定义

$a\equiv b\pmod m$ 等价于 $m\mid(a-b)$

4.1.2 性质

1. $\begin{cases}a\equiv b\pmod m\\c\equiv d\pmod m\end{cases}\Rightarrow \begin{cases}a\pm c\equiv b\pm d\pmod m\\ac\equiv bd\pmod m\end{cases}$
2. $a\equiv b\bmod m_i\Rightarrow a\equiv b\bmod([m_1,\cdots,m_n])$
3. $ax\equiv b\bmod m$ 有解当且仅当 $(a,m)\mid b$

4.1.3 同余类

1. $[r]=m\mathbb Z+r$
2. $\mathbb Z/m\mathbb Z=\{[0],[1],\cdots,[m-1]\}$
3. $[a]+[b]=[a+b],[a][b]=[ab]$
4. $\mathbb Z/m\mathbb Z$ 在上述加法和乘法意义下构成 $m$ 元交换环
5. $F_p=\mathbb Z/p\mathbb Z$ 称为 $p$ 元素数域

$f:\mathbb Z/nm\mathbb Z\to(\mathbb Z/n\mathbb Z,\mathbb Z/m\mathbb Z)$
$a\mapsto(a\bmod n,a\bmod m)$