一、整数的唯一分解定理
1.1 问题引入
在环的理论中，唯一分解是一个极为重要的性质。最早人们发现在整数中，任意一个正整数都可以唯一地写成若干个素数的乘积（不计顺序），例如 $6 = 2 \times 3$，$14 = 2 \times 7$。后来人们考虑：除了整数环，还有哪些环也具有这种唯一分解性质？事实上，很多环——包括域上的一元多项式环——也具有类似的性质。
下面是算术基本定理（Fundamental Theorem of Arithmetic）的完整证明：任何一个正整数都可以分解成素数的乘积，并且这种分解在不计顺序下是唯一的。
只考虑正整数。对于负数，只需乘上一个 $-1$ 即可归约到正整数的情形。
1.2 分解的存在性（归纳证明）
命题：任意正整数 $n$ 都可以写成若干个素数的乘积。
证明（对 $n$ 使用归纳法）：
- 基础步：$n = 1$ 时，认为 $1$ 是零个素数的乘积（对空集求乘积定义为 $1$）。
- $n = 2$ 时，$2$ 本身就是素数，成立。
- 以下对 $n \geqslant 3$ 进行归纳。
设对所有小于 $n$ 的正整数命题成立，考虑 $n$。
分两种情况：
-
若 $n$ 是素数：则 $n$ 本身就是一个素数的乘积（只有一个因子），命题成立。
-
若 $n$ 不是素数（即 $n$ 是合数）：根据素数的定义，$n$ 不是素数意味着它在 $2$ 到 $n-1$ 之间存在正的因子。因此可以写成 $n = a \cdot b$，其中
\[2 \leqslant a \leqslant n-1,\quad 2 \leqslant b \leqslant n-1\]由于 $a$ 和 $b$ 都严格小于 $n$，根据归纳假设，它们都可以分解为素数的乘积：
\[a = p_1 p_2 \cdots p_k, \quad b = q_1 q_2 \cdots q_\ell\]因此
\[n = a \cdot b = p_1 p_2 \cdots p_k \cdot q_1 q_2 \cdots q_\ell\]也是若干个素数的乘积。$\square$
这个证明看似没有多说什么，但它确实是一个严格的证明。它把”不可能无穷无尽地分解下去”的直觉给严格化了。一般这种证明都采用归纳法来完成。
1.3 素数的关键性质（核心引理）
要证明分解的唯一性，仅靠”素数大于等于二且其正的因子只有一和它自己”这个定义是不够的。需要素数满足以下更关键的性质：
引理：设 $p$ 为素数，$a, b$ 为整数。若 $p \mid ab$，则 $p \mid a$ 或 $p \mid b$。
直观理解：
- $p = 2$ 时，这个命题就是说：如果两个数乘起来是偶数，则至少有一个数是偶数。
- $p = 3$ 时：如果两个数乘起来是 $3$ 的倍数，则至少有一个数是 $3$ 的倍数。
- 但对于合数，这个性质不成立。例如 $4 \mid 6 \times 10 = 60$，但 $4 \nmid 6$ 且 $4 \nmid 10$。这是因为 $4$ 本身可以拆分（$4 = 2 \times 2$），两个 $2$ 分别分给 $6$ 和 $10$，而素数不能再往下分了。
证明：不妨设 $p \nmid a$（若 $p \mid a$ 则结论已成立）。
由于 $p$ 是素数且 $p \nmid a$，$p$ 和 $a$ 的最大公因数只能是 $1$（因为 $p$ 的正因子只有 $1$ 和 $p$，而 $p \nmid a$ 排除了 $p$）。
所以 $\gcd(p, a) = 1$，从而存在整数 $x, y$ 使得
\[px + ay = 1\]两边同时乘以 $b$：
\[pbx + aby = b\]现在观察：$p \mid pbx$（显然），且由条件 $p \mid ab$，所以 $p \mid aby$。因此 $p$ 整除等式右边的每一项，从而 $p \mid b$。$\square$
上面用到的”若 $\gcd(u, v) = 1$ 且 $u \mid vw$，则 $u \mid w$”这个命题之前讲过，务必掌握。
这个引理可以通过归纳法推广到多个因子的情形：若素数 $p$ 整除一个乘积 $a_1 a_2 \cdots a_s$，则 $p$ 至少整除其中一个因子。
1.4 唯一性的证明
命题（算术基本定理的唯一性部分）：设 $p_1 \leqslant p_2 \leqslant \cdots \leqslant p_t$ 和 $q_1 \leqslant q_2 \leqslant \cdots \leqslant q_s$ 都是素数（已从小到大排列），且
\[p_1 p_2 \cdots p_t = q_1 q_2 \cdots q_s\]则 $t = s$ 且对任意 $1 \leqslant i \leqslant t$ 有 $p_i = q_i$。
证明思路：通过对 $t$（左边素因子的个数）使用归纳法。
-
基础步：$t = 0$ 时，左边乘积为 $1$，则右边乘积也为 $1$，因此 $s = 0$，命题成立。
-
归纳步：设 $t \geqslant 1$。
考察 $p_t$（左边最大的素数）。因为
\[p_t \mid p_1 \cdots p_t = q_1 \cdots q_s\]由前面引理的推广形式，$p_t$ 必整除某个 $q_i$。而 $q_i$ 也是素数，其大于等于 $2$ 的正因子只能是它自身，故 $p_t = q_i$。
同理，考察 $q_s$（右边最大的素数），它必整除某个 $p_j$，从而 $q_s = p_j$。
现在利用从小到大排列的性质：
\[p_t = q_i \leqslant q_s = p_j \leqslant p_t\]（$p_t \leqslant p_j$ 因为 $p_t$ 是 $p$ 序列中最大的，$q_i \leqslant q_s$ 因为 $q_i$ 不超过 $q$ 序列中最大的）
这一连串不等式首尾都是 $p_t$，因此所有小于等于号都必须取等号，从而 $p_t = q_s$。
在等式 $p_1 \cdots p_t = q_1 \cdots q_s$ 两边同时消去 $p_t = q_s$，得到
\[p_1 \cdots p_{t-1} = q_1 \cdots q_{s-1}\]由归纳假设（因子个数减少了），$t-1 = s-1$ 且对任意 $i \leqslant t-1$ 有 $p_i = q_i$。从而 $t = s$ 且全部对应相等。$\square$
这个唯一性的证明与我们通常做计算的方式很不一样。它不是通过构造性的算法去找出分解，而是通过素数的抽象性质（$p \mid ab \implies p \mid a \text{ 或 } p \mid b$）来保证唯一性。证明唯一性的时候，不能只是说”我找了两次发现它们一样”，一定要用这种抽象的性质来确保。
1.5 素性检测与因子分解的算法问题
虽然已经从理论上证明了每个正整数都存在唯一的素因子分解，但如何高效地找到这个分解是一个更困难的计算问题。
素性检测（Primality Testing）
判断一个数 $n$ 是否为素数，如果按照定义穷举：
- 从 $2$ 到 $n-1$ 逐一试除——这需要 $\sim n$ 次操作，不是有效算法。
- 在算法理论中，”有效”通常指运行时间是输入规模的某个多项式函数。输入的规模是二进制位数，即 $\sim \log_2 n$。
朴素改进：只需从 $2$ 到 $\sqrt{n}$ 逐一试除即可。原因是：若 $n$ 是合数（$n = p_1 \cdots p_s$，$s \geqslant 2$），则 $n \geqslant p_1^2$，从而 $p_1 \leqslant \sqrt{n}$。即 $n$ 必定有一个素因子不超过 $\sqrt{n}$。
至少要知道这个结论——判断一个三位数是不是素数，最多试到二十几或三十几即可。
AKS素性检测算法：直到 21 世纪之前（2006 年左右），人们还不知道是否存在判断素数的一般有效算法。此前虽然有一些基于未证明猜想的算法（如基于广义黎曼猜想的算法），但在 2006 年，由三位印度计算机科学家（Agrawal、Kayal、Saxena）利用有限域的知识，首次给出了一个完全不依赖任何未证明猜想的确定性的多项式时间素性检测算法（即 AKS 算法）。这篇论文完全自我包含，不依赖任何其他猜想。
因子分解（Factorization）
因子分解比素性检测更难——如果能把一个数的所有素因子都找出来，自然就能判断它是不是素数。但是：
- 整数上的因子分解至今没有找到有效的多项式时间算法。
- 人们普遍相信这种有效算法应该是存在的，但至今仍未找到。
- 相比之下，在某些有限域上的多项式的因式分解反而存在有效时间算法。
二、域的定义与回顾
2.1 域的公理化定义
在研究多项式环之前，先回顾域（Field）的定义。
设 $F$（或记为 $E$）是一个集合，其上有加法和乘法两种运算。
环的条件：
- $(F, +)$ 是交换群（加法群）
- 乘法满足结合律
- 加法与乘法之间有分配律
- 乘法有幺元，记为 $1$，且 $1 \neq 0$
（本课程中，所有环都默认假设乘法有结合律和幺元。）
域的附加条件：
- 乘法满足交换律：$ab = ba$
- 除法性质：$\forall a \in F, a \neq 0$，存在 $b \in F$ 使得 $ab = 1$（即每个非零元都有乘法逆元）
直观理解：前四条正好就是加法、减法、乘法的性质（结合律、交换律、分配律）。第五条就是能做除法——非零元素都有倒数。只是因为域可以不嵌入实数/复数之中，通常不写 $\frac{1}{a}$ 而写作 $a^{-1}$。
最早域的定义是针对实数或复数的子集，研究对加减乘除封闭的集合。后来才抽象出来——不依赖于它一定是数的子集。这种抽象使得可以研究像有限域这样和实数完全不同的结构。
2.2 有限域及其在计算机中的应用
例子：设 $p$ 为素数，模 $p$ 剩余类环 $\mathbb{Z}_p = {0, 1, \ldots, p-1}$ 在模 $p$ 加法和模 $p$ 乘法下构成一个域（记为 $\mathbb{F}_p$）。
特别地，当 $p = 2$ 时，$\mathbb{F}_2 = {0, 1}$：
- 加法：$1 + 1 = 0$（模 $2$ 加法，即 XOR）
- 乘法：$0 \cdot 0 = 0, \; 0 \cdot 1 = 0, \; 1 \cdot 1 = 1$
有限域在计算机科学中甚至比无限域用得更多。计算机里的数写成二进制就是 $0$ 和 $1$ 的有限序列 ${a_n a_{n-1} \cdots a_0}$，每个 $a_i \in {0, 1}$，可以用来表示信息、状态，或者存储数值。有限 $\mathbb{F}_2$ 的结构在编码理论、密码学等领域有大量应用。
除了实数域 $\mathbb{R}$、复数域 $\mathbb{C}$ 和有限域 $\mathbb{F}_p$ 之外，还有其他很多域（例如从满足一定条件的环出发构造出的域），后面会介绍。
三、域上的一元多项式环
3.1 从微积分中”跳出来”——纯代数的多项式定义
之前在复数域上定义过幂级数和多项式。现在将定义推广到一般的域 $F$ 上。
在一般的域上，不能像在微积分中那样定义”收敛”，所以域上的幂级数只能是一个形式上的记号，没有分析意义上的收敛性。这里的运算完全是纯代数的二元运算。
形式幂级数环 $F[[x]]$
作为集合，$F[[x]]$ 中的元素是全体 $F$ 中元素构成的、以自然数为下标的序列：
\[\alpha = (\alpha_0, \alpha_1, \alpha_2, \ldots), \quad \alpha_i \in F\]加法：按分量相加 \((\alpha + \beta)_i = \alpha_i + \beta_i\)
乘法（卷积/柯西乘积）： \((\alpha * \beta)_n = \sum_{k=0}^{n} \alpha_k \cdot \beta_{n-k}\)
直观上，乘法就是”$X$ 的幂次一样的合并到一起”——角标加起来等于 $n$ 的所有项求和。
幺元（乘法单位元）为：第 $0$ 个分量等于 $1$，其余分量都等于 $0$。
未定元 $X$（indeterminate）：定义为一个特殊元素 \(X = (0, 1, 0, 0, 0, \ldots)\) 即第 $0$ 个分量为 $0$，第 $1$ 个分量为 $1$，其余为 $0$。
根据乘法的定义，容易验证 $X^m$： \(X^m = (\underbrace{0, 0, \ldots, 0}_{m\text{ 个}}, 1, 0, 0, \ldots)\) 即第 $m$ 个位置为 $1$（注意下标从 $0$ 开始，所以这是第 $m$ 次方）。
数乘：对 $a \in F$，定义 $a\alpha = (a\alpha_0, a\alpha_1, a\alpha_2, \ldots)$，即每个分量都乘上 $a$。
$F[[x]]$ 在此运算下构成一个交换环（有结合律、有幺元、乘法可交换）。
多项式环 $F[x]$
多项式（polynomial）是幂级数的一个子集：只有有限个非零分量的幂级数。
即 $\alpha$ 是多项式当且仅当存在 $m \in \mathbb{N}$，使得对所有 $i > m$ 都有 $\alpha_i = 0$。
记 $F[x]$ 为 $F$ 上全体一元多项式的集合（用一个方框表示，区别于幂级数环 $F[[x]]$ 的双方框记号）。
可以验证两个多项式的乘积仍然是多项式。
多项式与幂级数的两种等价视角
- 序列视角：$\alpha = (\alpha_0, \alpha_1, \ldots, \alpha_m, 0, 0, \ldots)$
- 形式记号：$\alpha = \sum_{i=0}^{m} \alpha_i X^i$
这两种写法本质上是一致的。如果从序列定义出发，结合加法、乘法、数乘的定义，可以严格地推导出形式记号的合法性——它不再是”形式上”的，而是有严格代数意义的等式。
如果你不习惯从序列出发，直接把它看成形式记号 $\sum \alpha_i X^i$ 也没有问题，关键是要知道加法、乘法和数乘的定义是怎么来的——按幂次相同的合并即可。
实际上，上述定义中除了”数乘下次数不变”需要用到域（或整环）的性质之外，加法和乘法的定义对任何环 $F$ 也同样有效。本课程将重点放在域上的多项式。
3.2 多项式的次数（Degree）
次数（degree）是研究多项式最基本的量。
定义：对于非零多项式 $f$，设 $m$ 是使得 $f_m \neq 0$ 的最大下标，则 $f$ 的次数 $\deg(f) = m$。
零多项式：人为规定 $\deg(0) = -\infty$。
零次多项式：只有常数项（第 $0$ 位非零，其余为 $0$），即域 $F$ 中的元素。记法上直接把零次多项式写成域中对应的元素。
注意：对一般的幂级数（而非多项式）是无法定义次数的，因为它可能有无限多个非零系数，找不到”最大的那个不为零的下标”。这是多项式独有的性质。
3.3 次数的基本性质
命题：设 $f, g \in F[x]$，$0 \neq a \in F$，则
- $\deg(f + g) \leqslant \max{\deg(f), \deg(g)}$
- 若 $\deg(f) < \deg(g)$，则 $\deg(f + g) = \deg(g)$
- $\deg(af) = \deg(f)$（数乘非零元素不改变次数）
- $\deg(f * g) = \deg(f) + \deg(g)$
关于规定 $-\infty$ 的运算约定（与微积分中类似）：
- $-\infty + \text{任何实数} = -\infty$
- $-\infty + (-\infty) = -\infty$
在此规定下，以上四条性质在涉及零多项式时仍然形式上成立。
性质 1 的证明
不妨设 $f$ 的次数为 $M$，$g$ 的次数为 $N$（若 $f$ 或 $g$ 为零多项式则结论显然）。
对任意 $i \geqslant \max{M, N} + 1$，根据次数定义有 $f_i = 0$ 且 $g_i = 0$，因此 \((f + g)_i = f_i + g_i = 0 + 0 = 0\)
这说明在 $\max{M, N}$ 以上的位置，$f+g$ 的系数全为零。因此 $f+g$ 的非零系数最多只能出现在不超过 $\max{M, N}$ 的位置上，从而 $\deg(f+g) \leqslant \max{M, N}$。$\square$
性质 2 的证明
设 $\deg(f) = M < N = \deg(g)$。由性质 1，$\deg(f+g) \leqslant N$。
再看第 $N$ 个位置： \((f+g)_N = f_N + g_N\)
由于 $\deg(f) = M < N$，所以 $f_N = 0$（超出 $f$ 的次数）。而 $\deg(g) = N$，由次数定义 $g_N \neq 0$。
因此 $(f+g)_N = g_N \neq 0$，这意味着 $f+g$ 至少有一个 $N$ 次的非零系数。于是 $\deg(f+g) \geqslant N$。
综合两方面，$\deg(f+g) = N$。$\square$
性质 3 的证明
设 $f \neq 0$，$\deg(f) = N$。
第 $N$ 个位置：$(af)_N = a \cdot f_N$。在域中，两个非零元素的乘积仍为非零元素（这里用到了域的整环性质——这是关键），故 $(af)_N \neq 0$。
对 $i \geqslant N+1$：$(af)_i = a \cdot f_i = a \cdot 0 = 0$。
因此数乘后，最高非零系数的位置不变，次数不变。$\square$
这一步开始真正用到了域的性质。”在域中两个非零元素相乘仍为非零”这个性质对一般环不一定成立，这正是域（准确说是整环）区别于一般环的关键。
性质 4 的证明
设 $f \neq 0$，$\deg(f) = M$；$g \neq 0$，$\deg(g) = N$。
要证 $\deg(f * g) = M + N$。
首先看第 $M+N$ 个位置（根据乘法定义）： \((f * g)_{M+N} = \sum_{k=0}^{M+N} f_k \cdot g_{M+N-k}\)
需要证明这个和式中只有一项是非零的，即 $k=M$ 时对应的项 $f_M \cdot g_N$：
- 若 $k \geqslant M+1$，则 $f_k = 0$（超出 $f$ 的次数），该项为 $0$。
- 若 $0 \leqslant k \leqslant M-1$，则 $M+N-k \geqslant N+1$，于是 $g_{M+N-k} = 0$（超出 $g$ 的次数），该项为 $0$。
因此整个和式中只有 $k = M$ 的那一项可能非零： \((f * g)_{M+N} = f_M \cdot g_N\)
由于 $f_M \neq 0$，$g_N \neq 0$，且 $F$ 是域（整环），$f_M \cdot g_N \neq 0$。因此 $(f*g)_{M+N} \neq 0$。
还需要证明对 $i \geqslant M+N+1$，$(f*g)_i = 0$。这只需说明若 $i = M+N+L$（$L \geqslant 1$），则在和式 \((f*g)_i = \sum_{k} f_k \cdot g_{i-k}\)
中，每一项要么 $f_k = 0$（$k > M$），要么 $i-k > N$ 于是 $g_{i-k} = 0$（因为 $i-k \geqslant M+N+1-k$，代入最小可能的 $k=M$ 得 $i-M \geqslant N+1$）。因此全部为零，从而 $\deg(f*g) \leqslant M+N$。
综合以上，$\deg(f*g) = M+N$。$\square$
多项式次数的乘法性质是整个多项式唯一分解理论的出发点。正如整数中通过”比大小”可以做带余除法，多项式通过”比次数”也可以做带余除法（division algorithm）。有了带余除法，就能像整数一样推导出多项式环中的唯一分解定理。这个后续会继续展开。
四、课程概述
后续将继续在带余除法的基础上，建立类似于整数环中”最大公因式”、”不可约多项式”（对应整数中的”素数”）以及”唯一分解”的理论。有限域上的多项式因式分解有有效算法，与整数的因子分解形成了有趣的对比。