域论

引入

域论（field theory）是关于域的理论。

本文涉及的域论主要是域的扩张理论。域是对加、减、乘、除都封闭的代数结构，算法竞赛中经常需要对质数 $p$ 取模，就相当于在有限域 $\mathbf F_p$ 上进行运算。和实数域 $\mathbf R$ 的情形类似，有些问题的求解在更大的域（即复数域 $\mathbf C$）上进行计算更为方便，常见的例子比如利用快速傅里叶变换加速实系数多项式的乘法。对于有限域也可以做类似的操作。多数读者对于有限域的扩张相对陌生，因而，了解一般的域上的扩张理论是有益的。文末给出了一些需要对有限域进行扩张的算法应用，同时也简单地讨论了部分应用中可能需要的整数环上的扩张。

与域论紧密相关的是 Galois 理论。它将域的扩张与其自同构群联系起来，从而可以通过群论的工具来理解域的扩张的性质。尽管这一理论也往往是相关代数课程的核心内容，但是与算法竞赛的内容相去甚远，故而本文不做过多介绍。有兴趣的读者应当阅读相关专业书籍。

记号

在不引起歧义时，本文可能会省略掉环和域的乘法记号，并且会将环 $(R,+,\cdot)$ 写作环 $R$，将域 $(F,+,\cdot)$ 写作域 $F$。环和域的加法单位元称为零元，乘法单位元称为幺元。而且，本文中的 $p$ 总是素数，而 $q$ 总是素数幂，且可以写作 $p^n$，其中，$n$ 是正整数。

域的扩张

类似群、环的情形，可以建立子域和域同态的概念。

子域

对于域 $F$，如果它的子环 $E$ 也是域，那么称 $E$ 是域 $F$ 的子域（subfield）。

其中，无论环和子环的定义对于幺元的处理如何，子域 $E$ 必然包含域 $F$ 的幺元[^subfield-one]。

域同态

自域 $F$ 到域 $E$ 的环同态 $\varphi:F\rightarrow E$ 也称为自域 $F$ 到域 $E$ 的 域同态（field homomorphism）。

域同态对幺元的处理

如果与本文的定义不同，环同态要求幺元映射到幺元，那么域同态自然也要求幺元映射到幺元。否则，幺元也可能映射到零元。

因为域只有平凡的理想，所以域同态要么将整个域映射到零元，要么必然是嵌入映射。这说明，域同态的讨论可以转化为子域的讨论。

在域的情形，往往更小的域是更为熟悉的域，所以，通常会转而以子域作为基点来考察更大的域。这就是域的扩张的概念。

域扩张

对于域 $F$，如果 $F$ 是 $E$ 的子域，则称域 $E$ 是域 $F$ 的扩张（extension），或称扩域，记作 $E/F$。

域扩张的记号

尽管形式上一致，但是域扩张的概念和商环并没有关系，不应混淆。

例子

复数域 $\mathbf C$ 就是实数域 $\mathbf R$ 的扩张，而实数域 $\mathbf R$ 又是有理数域 $\mathbf Q$ 的扩张。

域扩张的次数

对于域扩张 $E/F$，域 $E$ 总是域 $F$ 上的线性空间。这个线性空间的维度就是域扩张的次数。

域扩张的次数

域扩张 $E/F$ 的次数（degree），是指将 $E$ 看作是域 $F$ 上线性空间时的维度，即 $\dim_F(E)$，记作 $[E:F]$。如果域扩张的次数是有限的，就称域扩张为 有限扩张（finite extension），否则就称为 无限扩张（infinite extension）。

例子

域扩张 $\mathbf C/\mathbf R$ 的次数 $[\mathbf C:\mathbf R]$ 等于 $2$，所以是有限扩张。域扩张 $\mathbf R/\mathbf Q$ 是无限扩张。

域的扩张次数满足乘法原理。

定理

设 $F\subseteq K\subseteq E$ 都是域，则它们之间的扩张次数满足 $[E:F]=[E:K][K:F]$。

证明

对于扩张次数是无限的情形，这是显然的；否则，如果 $\{\alpha_i\}$ 是 $E$ 作为 $K$ 上线性空间的一组基，且 $\{\beta_j\}$ 是 $K$ 作为 $F$ 上线性空间的一组基，那么可以验证，$\{\alpha_i\beta_j\}$ 是 $E$ 作为 $F$ 上线性空间的一组基。

本文讨论的情形主要是域的有限扩张。

域的特征

对域扩张的研究，有一个自然的起点，就是包含域 $F$ 幺元的最小子域，这个域也称为域 $F$ 的 素子域（prime subfield）。

素子域的结构，由域幺元的性质唯一确定。域的特征就概括了这样的性质。

域的特征

域 $F$ 的特征（characteristic）是使得 $n\cdot 1=0$ 成立的最小正整数 $n$；如果这样的 $n$ 不存在，则称域 $F$ 的特征是 $0$。其中，$n\cdot 1$ 指 $n$ 个幺元 $1$ 相加的结果。如果域 $F$ 的特征不为 $0$，那么就称域 $F$ 是 有限特征的（finite characteristic）。

域的特征可以通过环同态来理解。整数环 $\mathbf Z$ 就是自 $0$ 和 $1$ 出发，反复施加加、减、乘等运算得到的封闭结构。它可以看作某种「原型」，所有包含幺元的环都应当「继承」了整数环的部分结构[^initial-object-ring]。因而，对于域 $F$，可以考察环同态 $\varphi:\mathbf Z\rightarrow F$ 并要求 $\varphi(1)=1$。这样的环同态是唯一确定的，它将 $n\in\mathbf N_+$ 映射到 $n\cdot 1$，即 $n$ 个幺元 $1$ 相加。该同态的像 $\varphi(\mathbf Z)$ 嵌入了域 $F$ 中，必然含幺、交换、无零因子，故而是整环。所以，同态的核 $\ker\varphi$ 必然是素理想。整数环 $\mathbf Z$ 的素理想只能是 $(n)$ 的形式，其中 $n=0$ 或者 $n$ 是素数。这样得到的 $n$ 就是该域的特征。

域的特征确定了素子域的结构：

当特征为 $0$ 时，同态 $\varphi$ 是单的，整数环 $\mathbf Z$ 嵌入了域 $F$ 中。有理数域 $\mathbf Q$ 作为最小的包含整数环的域必然也可以嵌入域 $F$ 中，它就是域 $F$ 的素子域；
当特征为素数 $p$ 时，同态 $\varphi$ 的像 $\mathbf Z/p\mathbf Z$ 嵌入了域 $F$ 中。此时，$\mathbf Z/p\mathbf Z$ 已经是域，记作 $\mathbf F_p$，它就是域 $F$ 的素子域。

这些讨论实际上说明了如下结论：

定理

域 $F$ 的特征只能是 $0$ 或素数 $p$。特征为 $0$ 的域对应的素子域是 $\mathbf Q$，特征为素数 $p$ 的域对应的素子域是 $\mathbf F_p$。

定理中的 $\mathbf Q$ 和 $\mathbf F_p$ 也称为素域（prime field），即子域只有它自身的域。有限域必然是有限特征的，因为特征为 $0$ 的域至少包含子域 $\mathbf Q$。

特征有限的域和零特征的域性质往往不同。比如，有限特征的域有如下性质：

定理

设 $F$ 的特征为 $p$，则有：

域 $F$ 的加法群中，所有非零元素的阶都是 $p$，即对所有 $x\in F$ 都有 $px=0$；
「新手之梦」（freshman's dream），即对所有 $x,y\in F$ 都有 $(x+y)^p=x^p+y^p$。进而，映射 $x\mapsto x^p$ 是 $F$ 上的单自同态，叫做 Frobenius 自同态（Frobenius endomorphism）。

证明

对于第一条性质，只要注意到 $px=(p1)x=0x=0$ 即可。对于第二条性质，只需要注意到 $(x+y)^p$ 的二项式展开中，除了 $x^p$ 和 $y^p$ 外的全部其他项的系数都是 $p$ 的倍数，故而根据第一条性质就有 $(x+y)^p=x^p+y^p$。至于验证 $x\mapsto x^p$ 是自同态，只需要再验证 $(xy)^p=x^py^p$，这是因为域的乘法满足交换律。最后，域之间的环同态将幺元映射到幺元，则必然是单射。

当然，对于有限域，Frobenius 自同态必然也是满的，因而是域的自同构。

单扩张

类似于实数域扩张到复数域的情形，很多扩张可以通过向域中添加额外的元素，并规定其运算性质来完成。在一般的情形，为避免规定运算性质引起的麻烦，不妨考虑在域扩张 $E/F$ 中，将 $E\setminus F$ 中的元素附加到 $F$ 上的情形，此时这些额外的元素与域 $F$ 中元素的运算的规则已经在更大的域 $E$ 中确定了。

由子集生成的域扩张

设 $E/F$ 是域扩张，$S\subseteq E$，那么 由 $S$ 生成的域 $F$ 上的扩张（extension generated by $S$ over $F$）就是指同时包含 $F$ 和 $S$ 的，最小的 $E$ 的子域，记作 $F(S)$。

最为简单的情形自然是集合 $S$ 中的元素很少的情形。

有限生成扩张

设 $E/F$ 是域扩张，如果存在有限集 $S=\{\alpha_1,\cdots,\alpha_n\}\subseteq E$ 使得 $E=F(S)$ 成立，则称 $E$ 为域 $F$ 的 有限生成扩张（finitely generated extension），也记作 $F(\alpha_1,\cdots,\alpha_n)$。

单扩张

设 $E/F$ 是域扩张，如果存在 $\alpha\in E$ 使得 $E=F(\alpha)$ 成立，则称域 $E$ 是域 $F$ 的 单扩张（simple extension）。其中，元素 $\alpha$ 称为这个单扩张的 本原元（primitive element）。

例子

这些例子都是向 $\mathbf Q$ 中添加 $\mathbf C$ 中的元素得到的。

对于无平方因子的整数 $D\neq 0,1$，二次域 $\mathbf Q(\sqrt D)$ 就是在域 $\mathbf Q$ 中添加了 $\sqrt D\in\mathbf C\setminus\mathbf Q$ 得到的单扩张。它的扩张次数是 $2$，因为 $\{1,\sqrt D\}$ 构成了一组基。
域 $\mathbf Q(\sqrt 2,\sqrt 3)$ 就是在域 $\mathbf Q$ 中添加了 $\sqrt 2$ 和 $\sqrt 3$ 得到的扩张。当然有 $\mathbf Q(\sqrt 2,\sqrt 3)=\mathbf Q(\sqrt 2)(\sqrt 3)=\mathbf Q(\sqrt 3)(\sqrt 2)$，即最后的扩张与元素的添加顺序和方式无关。这也是单扩张，因为 $\mathbf Q(\sqrt 2,\sqrt 3)=\mathbf Q(\sqrt 2+\sqrt 3)$。它的扩张次数是 $4$，因为 $\{1,\sqrt 2,\sqrt 3,\sqrt 6\}$ 构成了一组基。
域 $\mathbf Q(\pi)$ 也是单扩张，其中，$\pi$ 是圆周率。它是无限扩张，因为 $\mathbf Q[\pi]\subseteq \mathbf Q(\pi)$ 已经有一组基 $\{1,\pi,\pi^2,\cdots\}$。
域 $\mathbf Q(\pi,\mathrm e)$ 是有限生成的扩张，但不是单扩张。其中，$\pi$ 是圆周率，$\mathrm e$ 是自然对数的底。

这些例子说明，单扩张的性质可能相差悬殊。这取决于添加的元素的性质。

代数扩张

为了分析向域中添加元素可能出现的所有情形，不妨仿照前文对域的特征的讨论，考察多项式环 $F[x]$ 到扩张 $E/F$ 的环同态。此处的 $F[x]$ 起到了前文的整数环 $\mathbf Z$ 的作用：它正是在域 $F$ 中添加不定元 $x$ 后且对加、减、乘封闭的结构的「原型」[^polynomial-universal]。

设环同态 $\varphi:F[x]\rightarrow E$ 满足 $\varphi$ 限制在 $F$ 上是恒等映射，且 $\varphi(x)=\alpha$，即将不定元映射到扩张 $E$ 中的某个元素。此时，因为像 $\varphi(F[x])=F[\alpha]$ 必然是整环，同态的核 $\ker\varphi$ 必然是多项式环 $F[x]$ 的素理想。域上的多项式环是主理想整环，因而它必然有 $(f(x))$ 的形式，其中 $f(x)=0$ 或 $f(x)$ 是 $F[x]$ 中的不可约元。对此有如下讨论：

当同态的核 $\ker\varphi=\{0\}$ 时，多项式环 $F[x]$ 嵌入到 $E$ 中，它的像 $F[\alpha]$ 是整环。因而，域 $E$ 中同时包含 $F$ 和 $\alpha$ 的最小的域就是 $F[\alpha]$ 的分式域，即 $F(\alpha)$。这个记号，既可以解释为将有理分式域 $F(x)$ 中的不定元代入 $\alpha$ 的结果，也可以解释为域 $F$ 上由 $\alpha$ 生成的单扩张：这两个解释在这个语境下得到的结果是一致的；
当同态的核 $\ker\varphi=(f(x))$，且 $f(x)$ 为不可约元时，就成立 $\varphi(f(x))=f(\alpha)=0$，即 $\alpha\in E$ 是 $F$ 上的多项式 $f(x)$ 的根。因为 $F$ 是域，不妨设 $f(x)$ 是首一多项式。此时同态 $\varphi$ 的像是域 $F(\alpha)$，故而有

\[ F[x]/(f(x))\cong F(\alpha). \]

此时又可以分为两种情形：
1. 如果 $f(x)$ 是一次多项式，即 $f(x)=x-\alpha$ 时，有 $\alpha\in F$，故而扩张 $F(\alpha)=F$ 是平凡的；
2. 其余情形，$f(x)$ 是高于一次的不可约多项式，且 $\alpha\in E\setminus F$，此时的像 $F[\alpha]$ 已经是包含 $F$ 和 $\alpha$ 的域，因而，它就是 $F(\alpha)$，即 $F$ 上由 $\alpha$ 生成的扩张，且 $F(\alpha)\supset F$ 不是平凡的。

这些讨论启发了如下的定义：

代数元与超越元

对于扩张 $E/F$，如果元素 $\alpha\in E$ 是 $F$ 上某个非零多项式 $f(x)$ 的根，则称 $\alpha$ 是 $F$ 上的 代数元（algebraic element）；否则，称元素 $\alpha$ 是 $F$ 上的 超越元（transcendental element）。

极小多项式

对于域 $F$ 上的代数元 $\alpha$，以 $\alpha$ 为根且次数最小的首一多项式 $f(x)$ 称作它的 极小多项式（minimal polynomial）。

此处的极小多项式就是前文分析中的不可约多项式 $f(x)$。当然，也可以直接证明极小多项式都是不可约的。极小多项式 $f(x)$ 的极小性就意味着，只要域 $F$ 上的多项式以 $\alpha$ 为根，就必然能够分解出因子 $f(x)$。

例子

$\sqrt 2$ 是 $\mathbf Q$ 上的代数元，极小多项式是 $x^2-2$。
$\sqrt 2$ 是 $\mathbf R$ 上的代数元，极小多项式是 $x-\sqrt 2$。
$\pi$ 是 $\mathbf Q$ 上的超越元。
一般地，$\mathbf Q$ 上的代数元称为 代数数（algebraic number），而超越元称为 超越数（transcendental number）。特别地，如果代数数的极小多项式是首一多项式，它就称作 代数整数（algebraic integer）。代数扩张中的全体代数整数构成环。例如，二次域 $\mathbf Q(\sqrt{D})$ 中的代数整数就构成二次整数环 $\mathbf Z[\omega]$。此处记号的含义见二次整数环页面。

代数扩张与超越扩张

对于扩张 $E/F$，如果域 $E$ 的元素都是 $F$ 中的代数元，则称域 $E$ 是 $F$ 上的 代数扩张（algebraic extension）；否则，称域 $E$ 是 $F$ 上的 超越扩张（transcendental extension）。

单扩张的结果，根据添加元素的性质不同，可以分为两类。当添加的元素是超越元时，单扩张总是同构于有理分式域。此时，没有任何可以进一步化简的可能性。但是，当添加的元素是代数元时，单扩张实际上就是 $F[\alpha]$，即将 $\alpha$ 直接替换多项式环 $F[x]$ 中的不定元 $x$ 得到的结果。从初等的视角看，相较于超越元的情形，此时扩域中的元素可以没有分母；这意味着，类似于初等算术中「分母有理化」的过程，在代数元的单扩张中总是可行的。因为算法竞赛中涉及到的扩域主要是单代数扩张，下一节要对它的计算做更为细致的讨论。

单代数扩张的重要性，也反映在如下的定理中：

定理

域扩张是有限扩张，当且仅当它是有限生成的代数扩张。

证明

设 $F$ 为域，$E=F(\alpha_1,\cdots,\alpha_n)$ 为域上的有限生成代数扩张，即 $\alpha_i$ 都是 $F$ 上的代数元。设 $E_i=F(\alpha_1,\cdots,\alpha_i)$，则 $E_0=F$ 且 $E_n=E$。注意到，$\alpha_i$ 必然是 $E_{i-1}$ 上的代数元，因为 $\alpha_i$ 在域 $F$ 上的极小多项式也是 $E_{i-1}$ 上的多项式；而且 $\alpha_i$ 在 $E_{i-1}$ 上的极小多项式次数必然不超过 $\alpha_i$ 在域 $F$ 上的极小多项式次数。故而，$[E_i:E_{i-1}]$ 必然是有限的，根据域扩张次数的乘法原理，$[E:F]=\prod_{i=1}^n[E_i:E_{i-1}]$ 也是有限的。反过来，从 $E_0=F$ 开始，对于已经构造好的 $E_i$，可以每次都在 $E\setminus E_i$ 中选择元素 $\alpha_{i+1}$ 加入到 $E_i$ 中，得到扩域 $E_{i+1}=E_i(\alpha_{i+1})$，直到 $E_n=E$ 为止。因为扩张的次数在不断的降低，这个过程必然在有限步内终止。因此，有限扩张必然是有限生成的代数扩张。

这意味着，要理解有限扩张的性质，只要理解单代数扩张即可。因为有限扩张总是可以通过有限多个的单代数扩张得到。

单代数扩张的结构与计算

本节中，设 $F$ 是数域，$E$ 是它的扩域，且 $\alpha\in E\setminus F$ 是域 $F$ 上的代数元。设 $\alpha$ 的极小多项式是 $f(x)$，且多项式 $f(x)$ 是 $n$ 次首一多项式，亦即

\[ f(x)=x^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0, \]

其中，$a_0,a_1,\cdots,a_{n-1}\in F$ 且 $f(x)$ 在 $F$ 上不可约。

同构关系 $F(\alpha)\cong F[x]/(f(x))$ 指出，扩域 $F(\alpha)$ 中的运算就是模 $f(x)$ 的多项式的计算。根据多项式的带余除法，只需要考虑所有次数小于 $n=\deg f(x)$ 的多项式的同余类就可以了。对于这些多项式，自然的一组基就是 $\{1,\alpha,\cdots,\alpha^{n-1}\}$。因此，有如下结论：

定理

在本节的假设下，扩域 $F(\alpha)$ 可以写作

\[ F(\alpha)=\{\lambda(\alpha)=\lambda_0+\lambda_1\alpha+\cdots+\lambda_{n-1}\alpha^{n-1}:\lambda_0,\lambda_1,\cdots,\lambda_{n-1}\in F\}. \]

其中，$\lambda(x)$ 遍历全体次数小于 $n$ 的多项式。因此，扩张次数 $[F(\alpha):F]=n$，即 $\alpha$ 的极小多项式的次数。扩域中，元素 $\lambda(\alpha)$ 和 $\mu(\alpha)$ 的加法，就是多项式的加法，即对应位置的系数相加；元素 $\lambda(\alpha)$ 和 $\mu(\alpha)$ 的乘法，结果可以写作 $\rho(\alpha)$，其中 $\rho(x)$ 是乘积 $\lambda(x)\mu(x)$ 除以 $f(x)$ 的余式。

当然，作为域，还可以计算 $F(\alpha)$ 中元素的除法。根据定理中描述的乘法的过程，这相当于求解多项式环上的线性同余方程。类比整数的做法，要计算商 $\lambda(\alpha)/\mu(\alpha)$，可以先确定 $\mu(\alpha)$ 的乘法逆元，再乘以 $\lambda(\alpha)$ 即可。要计算 $\mu(\alpha)$ 的乘法逆元，只要解同余方程 $\mu(x)\xi(x)\equiv 1\pmod{f(x)}$ 即可。这可以通过扩展欧几里得算法实现。

下面，通过几个具体的例子理解计算的细节。

例子

考察扩域 $\mathbf Q(\alpha)$，其中的 $\alpha$ 是方程 $x^3-2x-2=0$ 的一个根。要计算

\[ \frac{1+\alpha}{1+\alpha+\alpha^2} \]

的值。

第一步是计算 $1+\alpha+\alpha^2$ 的逆元，也就是要计算同余方程

\[ (x^2+x+1)\xi(x)+(x^3-2x-2)\nu(x)=1 \]

的解。对此应用扩展欧几里得算法。先做辗转相除法，即有如下过程：

\[ \begin{aligned} x^3-2x-2 &= (x-1)(x^2+x+1)+(-2x-1),\\ x^2+x+1 &= \left(-\frac12x-\frac14\right)(-2x-1)+\frac34,\\ -2x-1 &= \left(-\frac{8}{3}x-\frac{4}{3}\right)\frac{3}{4}. \end{aligned} \]

再计算同余方程中的系数，即有

\[ \begin{aligned} \frac{3}{4} &=(x^2+x+1)+\left(\frac12x+\frac14\right)(-2x-1)\\ &=(x^2+x+1)+\left(\frac12x+\frac14\right)\left((x^3-2x-2)-(x-1)(x^2+x+1)\right)\\ &=\left(-\frac12x^2+\frac14x+\frac54\right)(x^2+x+1)+\left(\frac12x+\frac14\right)(x^3-2x-2). \end{aligned} \]

因而，方程的解为

\[ \xi(x)=-\frac23x^2+\frac13x+\frac53,\ \nu(x)=\frac23x+\frac13. \]

这说明 $1+\alpha+\alpha^2$ 的逆元是

\[ -\frac23\alpha^2+\frac13\alpha+\frac53. \]

第二步，就是计算逆元和 $1+\alpha$ 的乘积。对此，有

\[ \begin{aligned} (1+\alpha)\left(-\frac23\alpha^2+\frac13\alpha+\frac53\right) &=-\frac23\alpha^3-\frac13\alpha^2+2\alpha+\frac53\\ &=-\frac23(2\alpha+2)-\frac13\alpha^2+2\alpha+\frac53\\ &=-\frac13\alpha^2+\frac23\alpha+\frac13. \end{aligned} \]

这就是最后的答案。

在例子中只用到了 $\alpha$ 是方程的一个根这个条件，却并没有指定它是任何一个具体的根。多项式 $x^3-2x-2=0$ 在复数域 $\mathbf C$ 有一个实根和一对共轭复根，将它们中的任何一个添加进有理数域 $\mathbf Q$ 中得到的扩域都是同构的。也就是说，这三个互异的根在代数的视角上是没有区别的。

一般地，对于域 $F$ 上的不可约多项式 $f(x)$，在扩域中有不同的根 $\alpha\neq\beta$，这些根在分别对域 $F$ 做单扩张时表现出相同的代数性质，这些根互相称为共轭（conjugate）。复数域上的通常意义的共轭，就是这一概念在域扩张 $\mathbf C/\mathbf R$ 上的特例。

例子

考察扩域 $\mathbf F_2(\alpha)$，其中的 $\alpha$ 是方程 $x^2+x+1=0$ 的一个根。一般地，对于 $a+b\alpha$ 和 $c+d\alpha$，有运算规则

\[ \begin{aligned} (a+b\alpha)+(c+d\alpha)&=(a+c)+(b+d)\alpha,\\ (a+b\alpha)(c+d\alpha)&=ac+(ad+bc)\alpha+bd\alpha^2\\ &=(ac+bd)+(ad+bc+bd)\alpha. \end{aligned} \]

这提供了类似于复数域上的运算法则。大多数读者对于这样的根 $\alpha$ 都应当是陌生的，但这并不妨碍对这样的域中的元素进行运算。实际上，有 $[\mathbf F_2(\alpha):\mathbf F_2]=2$，因而，作为线性空间 $|\mathbf F_2(\alpha)|=4$，即这样得到的是大小为 $4$ 的有限域。稍后会看到，所有的有限域都是这样构造的。

在小规模运算时，对首一多项式取模 $f(x)$ 的运算通常可以通过代入

\[ x^n=-a_{n-1}x^{n-1}-\cdots-a_1x-a_0 \]

对目标多项式降次来进行。而且，对于低次的扩张，往往可以直接计算出系数的运算规则，使用类似复数类的实现而不必每次都计算取模等过程。

作为单代数扩张的实例，可以参考下文中的有限域的参考实现。

此处描述的算法在实践中都只能处理扩张次数比较低的情形，这对于绝大多数算法竞赛中的应用都是足够的。对于扩张次数高到成为复杂度瓶颈的情形，应当采取适当的多项式技术（快速傅里叶变换、快速数论变换、多项式快速取余、多项式欧几里得等）加速运算。

分裂域

上文已经对单代数扩张的结构做了详尽的讨论。但是，这样的扩张往往并不充分：

例子

考察扩张 $\mathbf Q(\sqrt[3]{2})/\mathbf Q$。代数元 $\sqrt[3]{2}$ 在域 $\mathbf Q$ 上的极小多项式是 $x^3-2$。在复数域 $\mathbf C$ 中，多项式 $x^3-2$ 有三个根，即 $\sqrt[3]{2},\sqrt[3]{2}\omega,\sqrt[3]{2}\omega^2$，其中，$\omega=\mathrm{e}^{2\pi\mathrm{i}/3}$ 是 $1$ 的三次原根。尽管 $\mathbf Q(\sqrt[3]{2})\cong\mathbf Q(\sqrt[3]{2}\omega)\cong\mathbf Q(\sqrt[3]{2}\omega^2)$，但是 $\mathbf Q(\sqrt[3]{2})$ 中并没有另外的两个根，这使得 $\sqrt[3]{2}+\sqrt[3]{2}\omega$ 这种运算就已经无法进行。如果要完整地考察这三个根，需要对域 $\mathbf Q(\sqrt[3]{2})$ 做进一步扩张，即扩张至 $\mathbf Q(\sqrt[3]{2},\sqrt[3]{2}\omega,\sqrt[3]{2}\omega^2)$。

前文已经说明，要做这样的扩张，只要对元素逐个做单扩张即可。应当注意的是，$\sqrt[3]{2}\omega$ 在域 $\mathbf Q$ 中和在域 $\mathbf Q(\sqrt[3]{2})$ 中的极小多项式并不相同：前者是 $x^3-2\in\mathbf Q[x]$，后者则是 $x^2+\sqrt[3]{2}x+\sqrt[3]{4}\in \mathbf Q(\sqrt[3]{2})[x]$，因为有

\[ x^3-2 = (x-\sqrt[3]{2})(x^2+\sqrt[3]{2}x+\sqrt[3]{4}). \]

原来的极小多项式在域的扩张后分解出一次因子，因而剩余的根的极小多项式的次数低于原来的域上的极小多项式。域不断扩张的过程，就是多项式不断「分裂」的过程。因此，每次单扩张时，都需要重新确定极小多项式。

将多项式的全部根都添加到域中，得到的就是多项式的分裂域。

分裂

设 $F$ 为域。如果多项式 $f(x)$ 在 $F[x]$ 中可以分解为一系列一次因子的乘积，就称多项式 $f(x)$ 在域 $F$ 中分裂（split）。

分裂域

对于域 $F$ 上的多项式 $f(x)$，如果扩张 $E/F$ 满足 $f(x)$ 在域 $E$ 中分裂但不在任何 $E$ 的真子域中分裂，就称域 $E$ 是多项式 $f(x)$ 的 分裂域（splitting field）。

可以证明，如同单扩张一样，给定多项式的分裂域在同构意义下是唯一确定的，与具体的构造方法无关。分裂域总是有限扩张。

正规扩张

对于代数扩张 $E/F$，如果对所有 $\alpha\in E$ 都有 $\alpha$ 的极小多项式在 $E$ 中分裂，则称域 $E$ 是域 $F$ 的 正规扩张（normal extension）。

正规扩张在 Galois 理论中起到基础的作用。

代数闭域

前文提及的多数扩张的概念原则上需要在比扩张更大的域内进行。尽管对于单扩张的情形，通过多项式环可以不依赖于更大的域构造出域的扩张，但是对于一般的情形并没有这样的手段。对于有理数域 $\mathbf Q$ 和实数域 $\mathbf R$，总是可以假定代数扩张包含在复数域 $\mathbf C$ 内部。对于有限域，并没有类似的已知的域。其实，对于所有的域，都存在代数闭包，使得域上所有的代数扩张都可以假定在代数闭包内进行。这就彻底解决了这一问题。

代数闭包

对于域 $F$，如果域 $\overline F$ 是域 $F$ 的代数扩张，且所有的 $f(x)\in F[x]$ 都在 $\overline F$ 中分裂，则称域 $\overline F$ 是域 $F$ 的 代数闭包（algebraic closure）。

代数闭包是域上的正规扩张。它的构造方式也基本上就是将所有可能的多项式的根添加到域中。而且和分裂域一样，某个域的代数闭包在同构意义下也是唯一的。

定理

任何域 $F$ 都有代数闭包。

证明

证明的困难来自于集合论。此处引用 Artin 的一个证明。

证明的第一部分从 $F$ 出发，构造了扩张 $K_1/F$ 使得所有 $F$ 上的多项式在 $K_1$ 中都有至少一个根。对于域 $F$，考察多元多项式环[^multi-poly-ring] $R=F[\cdots,x_f,\cdots]$，其中的不定元 $x_f$ 的下标取遍所有 $F$ 上的首一多项式。此时，由所有 $f(x_f)$ 生成的理想记作 $I$。首先，$I\neq R$，故而极大理想 $M\supseteq I$ 存在。否则，如果 $1\in I$，必然存在有限多个域 $F$ 上的首一多项式 $f_i$ 和相应的环 $R$ 中的元素 $g_i$ 使得 $g_1f_1(x_{f_1})+\cdots+g_kf_k(x_{f_k})=1$ 成立。设 $F(\alpha_1,\cdots,\alpha_k)$ 为向 $F$ 中添加 $f_i(x)$ 的根 $\alpha_i$ 后得到的代数扩张，则在 $F(\alpha_1,\cdots,\alpha_k)$ 中令上面得到的恒等式中 $x_{f_i}$ 都代入 $\alpha_i$，而在各个 $g_i$ 中出现的其它不定元 $x_f$ 都带入 $0$，则得到 $F(\alpha_1,\cdots,\alpha_k)$ 上的等式 $0=1$，这矛盾。故而，$I\neq R$，极大理想 $M$ 的构造是合法的。此时商环 $R/M$ 是域，记作 $K_1$，且任何 $F$ 上的首一多项式 $f(x)$ 都在 $K_1$ 中有根 $\overline{x_f}$。

证明的第二部分则归纳地得到了包含 $F$ 的一个代数闭域 $K$（定义见下文）。重复上述构造，基于域 $K_i$ 可以构造出域 $K_{i+1}$，使得 $K_i$ 的多项式在 $K_{i+1}$ 中都至少有一个根。而且，$K_i$ 自然地嵌入到 $K_{i+1}$ 中，所以可以定义它们的并集 $K=\bigcup_{i=1}^\infty K_i$。容易验证，这也是域，而且 $K$ 上的任何多项式的系数必然全部包含在某个 $K_i$ 中，故而它的一个根必然出现 $K_{i+1}\subseteq K$ 中。这说明 $K$ 上的所有多项式都在 $K$ 上至少有一个根，所以，$K$ 是代数闭域。

最后，令 $K$ 中所有 $F$ 上的代数元组成的集合记作 $\overline F$。它显然是域；因为对于任何 $\alpha,\beta\in\overline F$，都有 $\alpha\pm\beta,\alpha\beta,\alpha/\beta\in F(\alpha,\beta)\subseteq\overline F$。它也是 $F$ 的代数扩张，因为它的元素都是 $F$ 上的代数元。对于 $F$ 上的多项式 $f(x)$，它的所有根都是 $F$ 上的代数元，故而也在 $\overline F$ 中，故而必然可以分裂为一次因子的乘积。这就说明 $\overline F$ 是 $F$ 上的代数闭包。

例子

实数域 $\mathbf R$ 的代数闭包是复数域 $\mathbf C$。
有理数域 $\mathbf Q$ 的代数闭包是全体代数数（即域扩张 $\mathbf C/\mathbf Q$ 中的代数元）的集合，记作 $\overline{\mathbf Q}$。

所有的代数闭包的代数扩张都是平凡的。这样的域称为代数闭域。

代数闭域

如果域 $F$ 上任意多项式 $f(x)$ 都至少有一个根 $\alpha\in F$，那么就称域 $F$ 为一个 代数闭域（algebraically closed field）。

事实上，它有如下等价定义：

定理

对于域 $F$，以下性质都是等价的：

域 $F$ 是代数闭域；
域 $F$ 上的所有多项式 $f(x)$ 都分裂；
域 $F$ 上的不可约多项式只有一次多项式；
域 $F$ 没有非平凡的代数扩张；
域 $F$ 没有非平凡的有限扩张；
域 $F$ 是某个域的代数闭包。

证明

前五条性质的等价性显然，考察定义即可。对于第六条，代数闭域显然是自身的代数闭包，因为它没有非平凡的代数扩张；反过来，要证明域 $F$ 的代数闭包必然是代数闭域。设 $\overline F$ 是域 $F$ 的代数闭包，且 $f(x)$ 是 $\overline F$ 上的多项式。设 $\alpha$ 是 $f(x)$ 的分裂域中 $f(x)$ 的一个根，且 $f(x)$ 的非零系数的集合是 $S\subseteq\overline F$。那么，因为 $F(S)(\alpha)=F(S\cup\{\alpha\})$ 是有限扩张，$\alpha$ 必然也是 $F$ 上的代数元，故而根据代数闭包的定义，$\alpha$ 在 $F$ 上的极小多项式在域 $\overline F$ 中分裂，故而 $\alpha\in\overline F$。这说明，$\overline F$ 上任意多项式都有至少一个根。

最后，代数基本定理 [^fundamental-algebra]说明，$\mathbf C$ 是代数闭域。实数域 $\mathbf R$ 上的不可约多项式至多是二次的，或者等价地，它上面的代数扩张至多是二次扩张，就是因为通过代数扩张能够得到的最大的域就是 $\mathbf C$。

可分扩张

分裂域的概念保证了对于任何域上的多项式，总有扩域能够包括它的所有根，且分裂域精确地给出了这样的最小的扩域。多项式的性质和它的分裂域的性质紧密联系。但是，如果希望通过多项式的分裂域来研究多项式的性质，那么首先要面临的一个问题就是，多项式的分裂域与多项式的根的重数无关。因而，如果有可能，应当考虑多项式的某种意义上的「最简表示」。受此启发，把在域的代数闭包中也没有重根的多项式称为可分多项式。

可分多项式

对于域 $F$ 上的多项式 $f(x)$，如果 $f(x)$ 在 $F$ 的代数闭包 $\overline F$ 中没有重根，即它分解成一次因子的乘积时没有重复因子，那么 $f(x)$ 称为 可分的（separable）。

因为总是要扩张到域 $F$ 的代数闭包上讨论，可分多项式的判断其实与域 $F$ 的选取无关。但是，因为多项式的系数在 $F$ 中，应当考虑给出一个判断方法，能够使得在域 $F$ 上就能判断多项式是否可分而不必显式地构造出其扩域。

熟悉分析学的读者知道，多项式函数的重根有无可以通过它的导数判断：多项式函数的重根同样是它的导数的根。虽然多项式和多项式函数并非一致的概念，但是判断多项式函数重根有无的方法可以类比地迁移到多项式上。多项式的导数可以形式地定义如下：

形式导数

域 $F$ 上的多项式

\[ f(x)=a_0+a_1x+a_2x^2+\cdots+a_{n-1}x^{n-1}+a_nx^n=\sum_{i=0}^na_ix^i \]

的 （形式）导数（derivative），记作 $Df(x)$，定义为多项式

\[ Df(x)=a_1+2a_2x+\cdots+(n-1)a_{n-1}x^{n-1}+na_nx^{n-1}=\sum_{i=1}^nia_ix^{i-1}. \]

这个定义对于所有域上的多项式都适用，不依赖于任何拓扑结构，此处的导数算子 $D$ 只是把一个多项式映射到了另一个多项式。而且，可以通过对比系数验证，常见的导数运算法则，比如 $D(f(x)g(x))=(Df(x))g(x)+f(x)(Dg(x))$ 等，对于形式导数依然成立。

进而，要检查多项式 $f(x)$ 和它的导数 $Df(x)$ 在分裂域中是否有相同的根，可以不显式地构造出这个分裂域，而是通过它们的最小公因子来判断；这是因为多项式的根总是出现在它的极小多项式中，重复的根意味着相应的极小多项式因子也重复。于是，有重根的判断法则如下：

定理

对于域 $F$ 上的多项式 $f(x)$，如果 $f(x)$ 有重根 $\alpha$，那么导数 $Df(x)$ 也有同样的根 $\alpha$。进而，多项式 $f(x)$ 可分的充分必要条件是 $f(x)$ 与它的导数 $Df(x)$ 互素，即 $\gcd(f(x),Df(x))=1$。

证明

首先，因为带余除法在扩域中依然保持，欧几里得算法的结果也和扩域的选取无关，所以只要在分裂域中讨论它们的公因子就好了。由此，设 $\alpha$ 是 $f(x)$ 的 $k>1$ 重根，则分裂域中有分解 $f(x)=(x-\alpha)^kg(x)$，于是它的导数 $Df(x)=k(x-\alpha)^{k-1}g(x)+(x-\alpha)^kDg(x)$ 必然也有根 $\alpha$。反过来，如果 $f(x)$ 和 $Df(x)$ 都有根 $\alpha$，那么对于分裂域中的分解 $f(x)=(x-\alpha)g(x)$，就有 $Df(x)=(x-\alpha)Dg(x)+g(x)$，故而 $\alpha$ 也是 $g(x)$ 的根，因而 $\alpha$ 是 $f(x)$ 的重根。这就说明定理的第一部分。进而，多项式 $f(x)$ 有重根 $\alpha$，等价于 $x-\alpha$ 是 $\gcd(f(x),Df(x))$ 的因子。所以，多项式 $f(x)$ 不可分，就等价于 $\gcd(f(x),Df(x))$ 次数大于等于一。

域上的多项式总是可以分解为若干个不可约多项式的乘积。因为（相伴意义下）不同的不可约多项式总是有着不同的根，根的重复自然联系到相应的多项式因子的重复。那么，如果多项式的分解中没有重复的不可约因子，是否就能判断多项式可分呢？换句话说，不可约的多项式是否都可分？很遗憾，在一般的情形下，无法得到肯定的答案。问题出现在有限特征的域。

对于域 $F$ 上的不可约多项式 $f(x)$，多项式 $\gcd(f(x),Df(x))$ 作为 $f(x)$ 的因子，只能有两种情形，即 $1$ 或者 $f(x)$。对于前一种情况，多项式 $f(x)$ 自然是可分的；问题出现在后一种情况。但是，由于导数的定义中已经保证 $Df(x)=0$ 或者 $\deg Df(x)<\deg f(x)$，多项式 $f(x)$ 成为 $Df(x)$ 的因子，只能说明 $Df(x)=0$。这在有限特征的域中是有可能的。

对于特征为 $p$ 的域 $F$，如果 $Df(x)=0$，则多项式的所有非零系数都只能出现在次数恰为 $p$ 的倍数的项上，即多项式 $f(x)$ 可以写作

\[ f(x)=a_0+a_px^p+a_{2p}x^{2p}+\cdots+a_{(k-1)p}x^{(k-1)p}+a_{kp}x^{kp}. \]

如果真的存在域 $F$ 上的多项式 $f(x)$ 既不可约也不可分，则它只能有这种形式。但是，如果域 $F$ 中的所有元素总有 $p$ 次根，即对每个系数 $a_{jp}$ 都存在 $b_j\in F$ 使得 $a_{jp}$ 可以写作 $b_j^p$ 的形式，那么，根据 Frobenius 自同态，总有

\[ \begin{aligned} f(x)&=a_0+a_px^p+a_{2p}x^{2p}+\cdots+a_{(k-1)p}x^{(k-1)p}+a_{kp}x^{kp}\\ &=b_0^p+b_1^px^p+b_2^px^{2p}+\cdots+b_{k-1}^px^{(k-1)p}+b_k^px^{kp}\\ &=\left(b_0+b_1x+b_2x+\cdots+b_{k-1}x^{k-1}+b_kx^k\right)^p. \end{aligned} \]

因而，这样的域 $F$ 上并不存在这种形式的不可约多项式。因而，这种域上，所有不可约多项式都是可分的。这种域称为完美域。

完美域

如果域 $F$ 上的所有不可约多项式都是可分多项式，就称它为 完美域（perfect field）。

对于完美域，可分多项式的概念和唯一分解中没有平方因子的多项式的概念是等同的。

定理

设域 $F$ 是完美域，则 $F$ 上的多项式可分，当且仅当它可以写作若干个（相伴意义下）不同的不可约多项式的乘积。

本节的讨论其实已经足够给出移除多项式中的重复因子的方法，它是对多项式的因式分解算法中的关键步骤。但这超出了本文范畴，有兴趣的读者可以参考文末的相关资料。

这些讨论其实也给出了完美域的刻画：

定理

域 $F$ 为完美域，当且仅当域 $F$ 的特征是零，或者域 $F$ 的特征是 $p$ 且任何元素 $x\in F$ 都有 $p$ 次根（即 Frobenius 自同态也是自同构）。

有理数域 $\mathbf Q$ 和下文会讨论的有限域 $\mathbf F_q$ 都是完美域。

对于域不是完美域的情形，的确存在不可分的不可约多项式。

例子

考虑 $\mathbf F_2$ 的有理分式域 $\mathbf F_2(t)$ 上的多项式 $x^2-t$。因为 $\mathbf F_2(t)$ 是唯一分解整环 $\mathbf F_2[t]$ 的分式域，且 $t$ 是 $\mathbf F_2[t]$ 中的素元，则对素元 $t$ 应用 Eisenstein 判别法可知 $x^2-t$ 在 $\mathbf F_2[t]$ 中不可约，故而在 $\mathbf F_2(t)$ 中也不可约。但是，它的导数为 $0$，因而 $x^2-t$ 并不可分。事实上，在扩域 $\mathbf F_2(t)(\sqrt t)$ 中，它有二重根 $\sqrt t$。

最后回到域的扩张的讨论。

可分扩张

对于代数扩张 $E/F$，如果对所有 $\alpha\in E$ 都有 $\alpha$ 的极小多项式是可分多项式，那么称域 $E$ 是域 $F$ 的 可分扩张（seperable extension）。

完美域上的代数扩张都是可分扩张。这也可以作为完美域的等价定义。

如果一个代数扩张既是正规扩张，也是可分扩张，它也称作 Galois 扩张。Galois 扩张中，任何不可约多项式都没有重根，且根的数目都恰好等于多项式的次数，因而对根的置换可以充分地反映域扩张和多项式的性质。这样的扩张提供了建立 Galois 理论的基石。有兴趣的读者可以参考文末的相关资料。

分圆域

作为域扩张的简单例子，本节讨论分圆域。另一个域扩张的简单例子是二次域。

单位根群

复数域 $\mathbf C$ 中，多项式 $x^n=1$ 的根称为 $n$ 次单位根（$n$-th root of unity）。记 $\zeta_n=\mathrm{e}^{2\pi\mathrm{i}/n}$。那么，全体 $n$ 次单位根就是集合 $C_n=\{\zeta_n^k:k\in\mathbf Z\}$。在乘法运算下，$C_n$ 构成 $n$ 次循环群，可以记作 $\langle\zeta_n\rangle$，称为 $n$ 次单位根群。群 $C_n$ 的生成元，也就是那些阶恰好为 $n$ 的元素，称为 $n$ 次本原单位根（primitive $n$-th root of unity）。$n$ 次本原单位根的集合 $P_n=\{\zeta_n^k:k\in\mathbf Z,k\perp n\}$，恰有 $\varphi(n)$ 个元素；其中，$\varphi(n)$ 是欧拉函数。将单位根群 $C_n$ 的元素按照它的阶分类，就得到如下分解：

\[ C_n=\bigcup_{d|n}P_d. \]

对两边元素计数，就得到恒等式 $n=\sum_{d\mid n}\varphi(d)$。

分圆域

分圆域是将单位根添加到有理数域中得到的扩域。

分圆域

将 $n$ 次复单位根 $\zeta_n=\mathrm{e}^{2\pi\mathrm{i}/n}$ 添加到有理数域 $\mathbf Q$ 中得到的扩域 $\mathbf Q(\zeta_n)$ 称为 $n$ 次分圆域（$n$-th cyclotomic field）。

因为全体 $n$ 次单位根在乘法运算下构成循环群 $\langle\zeta_n\rangle$，分圆域 $\mathbf Q(\zeta_n)$ 也包括所有这些 $n$ 次单位根。其实，$\mathbf Q(\zeta_n)$ 正是域 $\mathbf Q$ 上多项式 $x^n-1$ 的分裂域。

定理

分圆域 $\mathbf Q(\zeta_n)$ 是有理数域 $\mathbf Q$ 上多项式 $x^n-1$ 的分裂域。

证明

设 $F$ 为有理数域 $\mathbf Q$ 上多项式 $x^n-1$ 的分裂域。因为 $\mathbf Q(\zeta_n)$ 上有多项式 $x^n-1$ 的全体复根，所以 $F\subseteq\mathbf Q(\zeta_n)$。反过来，因为 $\zeta_n\in F$，就必然有 $\mathbf Q(\zeta_n)=F$。这就说明 $F=\mathbf Q(\zeta_n)$。

这可以作为分圆域的等价定义。其实，将任何 $n$ 次本原单位根添加到分圆域中都能够得到 $\mathbf Q(\zeta_n)$。

分圆多项式

分圆域 $\mathbf Q(\zeta_n)$ 是有理数域 $\mathbf Q$ 上的单代数扩张。根据上文的分析，这样的域总是同构于某个多项式环的商环。为了得到这样的同构，需要分析 $\zeta_n$ 的极小多项式 $f(x)$。因为 $\zeta_n$ 是 $x^n-1$ 的根，所以 $f(x)$ 必然是 $x^n-1$ 的某个因子。这说明，需要考察多项式 $x^n-1$ 在 $\mathbf Q[x]$ 内的因式分解。根据 Gauss 引理，它必然可以在 $\mathbf Z[x]$ 中分解为若干个不可约的首一多项式的乘积。

因为 $\mathbf Q(\zeta_n)$ 是分裂域，多项式 $x^n-1$ 有分解：

\[ x^n-1=\prod_{\zeta\in C_n}(x-\zeta)=\prod_{d\mid n}\prod_{\zeta\in P_d}(x-\zeta). \]

因为不同阶的单位根的代数性质不同，它们必然不会是同一个不可约多项式的根。因此，要考察 $\zeta_n$ 的极小多项式，只要考虑上述分解中的因子

\[ \Phi_n(x)=\prod_{\zeta\in P_n}(x-\zeta) \]

即可。单位根 $\zeta_n$ 的极小多项式，必然是 $\Phi_n(x)$ 的因子。而且，这样定义的 $\Phi_n(x)$ 有如下性质：

定理

$\Phi_n(x)$ 是整系数首一多项式，且在 $\mathbf Z[x]$ 中不可约。

证明

由定义，$\Phi_n(x)$ 显然是首一多项式。首先，要证明 $\Phi_n(x)\in\mathbf Z[x]$。根据 Gauss 引理，多项式 $x^n-1$ 在 $\mathbf Z[x]$ 和 $\mathbf Q[x]$ 中有着相同的分解，且每个因子都是整系数首一多项式。这个分解中，每个因子 $f(x)$ 都是 $\mathbf Q[x]$ 上不可约的，且在 $\mathbf Q(\zeta_n)$ 中分裂；它的所有根都是 $n$ 次单位根，且必然有着相同的阶，所以这些根必然全部属于某一个 $P_d$ 而不能分别存在于不同的 $P_d$。这意味着，每个因子 $f(x)$ 都是某个 $\Phi_d(x)$ 的因子。故而，$\Phi_n(x)$ 可以写成若干个的整系数首一多项式的乘积，必然也是整系数首一多项式。

接下来，要证明 $\Phi_n(x)$ 在 $\mathbf Z[x]$ 是不可约的。设它有分解 $f(x)g(x)$，且 $f(x)$ 在 $\mathbf Z[x]$ 中不可约，那么只要证明 $f(x)$ 包含所有 $n$ 次本原单位根即可。也就是说，设 $\zeta$ 是 $f(x)$ 的一个根，要证明对于所有 $k\perp n$，都有 $\zeta^k$ 也是 $f(x)$ 的根；由于 $k$ 总是可以分解为素数的乘积，所以只需要证明对于所有素数 $p\perp n$，$\zeta^p$ 是 $f(x)$ 的根就可以了。假设不然，$\zeta^p$ 是 $g(x)$ 的根。因而，$\zeta$ 是 $\mathbf Z[x]$ 中多项式 $f(x)$ 和 $g(x^p)$ 的共同的根。因为 $f(x)$ 是 $\zeta$ 在 $\mathbf Q$ 上的极小多项式，必然有 $f(x)$ 整除 $g(x^p)$；亦即存在 $h(x)\in\mathbf Z[x]$ 使得 $g(x^p)=f(x)h(x)$。等式两侧同时对 $p$ 取模，得到 $\mathbf F_p[x]$ 上的等式 $\overline{g}(x^p)=\overline{f}(x)\overline{h}(x)$。利用 Frobenius 自同态可知，$\overline{g}(x)^p=\overline{f}(x)\overline{h}(x)$。因为 $\mathbf F_p[x]$ 也是唯一分解整环，$\overline{g}(x)$ 和 $\overline{f}(x)$ 必然有不平凡的公因子，所以，$x^n-\overline 1=\overline{f}(x)\overline{g}(x)$ 在 $\mathbf F_p$ 上不可分。但是，因为 $p\perp n$，它的形式导数 $nx^{n-1}$ 与它自身互素，这与它不可分矛盾。故而，可以证明 $\zeta^p$ 必然还是 $f(x)$ 的根，因而 $f(x)$ 包含所有 $n$ 次本原单位根，它就是 $\Phi_n(x)$。

这就说明，它就是 $\zeta_n$ 的极小多项式，也称为 $n$ 次分圆多项式（$n$-th cyclotomic polynomial）。上面的定义式指出，它有 $\varphi(n)$ 个复根，且这些复根正是全体 $n$ 次本原单位根；其中，$\varphi(n)$ 是欧拉函数。这也说明，$\mathbf Q(\zeta_n)/\mathbf Q$ 是 $\varphi(n)$ 次扩张。

分圆域 $\mathbf Q(\zeta_n)$ 中的代数整数环是 $\mathbf Z[\zeta_n]$。另外，当 $\varphi(n)=2$ 时，分圆域是二次扩张。具体来说，$\mathbf Q(\zeta_4)$ 是二次域 $\mathbf Q(\sqrt{-1})$；$\mathbf Q(\zeta_3)$ 和 $\mathbf Q(\zeta_6)$ 相同，都是二次域 $\mathbf Q(\sqrt{-3})$。

利用分圆多项式，多项式 $x^n-1$ 在 $\mathbf Z[x]$ 中有唯一分解

\[ x^n-1=\prod_{d\mid n}\Phi_d(x). \]

因此，$(x^d-1)\mid(x^n-1)$ 当且仅当 $d\mid n$。而且，对此式应用 Möbius 反演可得

\[ \Phi_d(x)=\prod_{d\mid n}(x^d-1)^{\mu(n/d)}. \]

利用这个表达式，可以递归地计算出全部的分圆多项式。此处给出前几个分圆多项式的例子，便于读者熟悉。

分圆多项式

前 $10$ 个分圆多项式如下：

\[ \begin{aligned} \Phi_1(x) &= x-1,\\ \Phi_2(x) &= x+1,\\ \Phi_3(x) &= x^2+x+1,\\ \Phi_4(x) &= x^2+1,\\ \Phi_5(x) &= x^4+x^3+x^2+x+1,\\ \Phi_6(x) &= x^2-x+1,\\ \Phi_7(x) &= x^6+x^5+x^4+x^3+x^2+x+1,\\ \Phi_8(x) &= x^4+1,\\ \Phi_9(x) &= x^6+x^3+1,\\ \Phi_{10}(x) &= x^4-x^3+x^2-x+1. \end{aligned} \]

一个有趣的事实是，虽然看起来这些分圆多项式的系数都只能是 $0$ 和 $\pm1$，但是对于一般的 $n$，这个结论是不对的。第一个反例出现在 $\Phi_{105}(x)$，而且可以证明，随着 $n$ 的增大，它的系数可以取到任意大的值。

利用上文的 Möbius 反演式，可以总结出如下性质来简化 $\Phi_n(x)$ 的计算：

性质

对于分圆多项式 $\Phi_n(x)$，有：

如果素数 $p\mid n$，则 $\Phi_{pn}(x)=\Phi_n(x^p)$；
如果素数 $p\perp n$，则 $\Phi_{pn}(x)=\dfrac{\Phi_n(x^p)}{\Phi_n(x)}$；
特别地，如果 $n$ 是奇数，则 $\Phi_{2n}(x)=\Phi_n(-x)$；
对于素数 $p$，有 $\Phi_{p}(x)=1+x+\cdots+x^{p-1}$；
特别地，$\Phi_{2^k}(x)=x^{2^{k-1}}+1$。

这些性质说明，对分圆多项式的计算，重点在于那些次数是无平方因子的奇数的情形。而对于这种情形，可以用性质二逐个添加素因子；每个素因子的加入，只需要做一次多项式除法。

分圆多项式还有很多其它的性质。

定理

设 $\Phi_n(x)$ 为 $n>1$ 次分圆多项式，且多项式的次数是 $\varphi(n)$。于是，有：

多项式 $\Phi_n(x)$ 是回文多项式，它的 $j$ 次项系数和 $\varphi(n)-j$ 次项系数相同，即 $\Phi_n(x)=x^{\varphi(n)}\Phi_n(1/x)$；
多项式的 $\varphi(n)-1$ 次项系数等于 Möbius 函数 $-\mu(n)$；
如果 $n$ 是素数幂 $p^k$，那么 $\Phi_n(1)=p$；否则，$\Phi_n(1)=1$；
设 $b>1$ 且 $p$ 为 $\Phi_n(b)$ 的素因子，则 $p\mid n$，或者 $n$ 是乘法群 $(\mathbf Z/p\mathbf Z)^\times$ 中的 $b$ 的阶，且这两种情况不能同时发生。

证明

对于前三条性质，只需要利用 Möbius 反演即可。对于 1，直接考察 $\Phi_n(x)$ 的 Möbius 反演形式，即 $\Phi_d(x)=\prod_{d\mid n}(x^d-1)^{\mu(n/d)}$；对于 2，设 $\Phi_n(x)$ 的 $\varphi(n)-1$ 次项系数为 $f(n)$，则比较 $x^n-1=\prod_{d\mid n}\Phi_d(x)$ 等式两侧的 $n-1$ 次项系数可知，$\sum_{d\mid n}f(d)=-[n=1]$，再做 Möbius 反演；对于 3，在 $x^n-1=\prod_{d\mid n}\Phi_n(x)$ 两侧同时除以 $\Phi_1(x)=x-1$，再代入 $x=1$，即有 $n=\prod_{d\mid n,d\neq 1}\Phi_n(1)$，再做 Möbius 反演。

下面证明第四条性质。首先，如果 $n$ 是乘法群 $(\mathbf Z/p\mathbf Z)^\times$ 中的 $b$ 的阶，那么 $n$ 是满足 $p\mid b^n-1$ 的正整数中最小的，故而 $p\mid\Phi_n(b)$。反过来，如果 $p\mid\Phi_n(b)$，则有 $b^n\equiv 1\pmod p$；可如果 $n$ 不是乘法群 $(\mathbf Z/p\mathbf Z)^\times$ 中的 $b$ 的阶，那么设它的阶为 $k$，必然有 $k\mid n$ 且 $p\mid\Phi_k(b)$。此时，$\Phi_k(x)$ 和 $\Phi_n(x)$ 在域 $\mathbf F_p$ 中有公共根 $b$，这说明 $x^n-1$ 有重根 $b$。这说明 $p\mid n$；否则，$x^n-1$ 与它的导数互素，所以在 $\mathbf F_p$ 上可分，不可能有重根。因而，$\Phi_n(b)$ 的素因子 $p$ 只有两种情况：$p\mid n$，或者 $n$ 是乘法群 $(\mathbf Z/p\mathbf Z)^\times$ 中的 $b$ 的阶。这两种情况是互斥的，因为后者意味着 $n\mid p-1$。

分圆多项式还可以用于解决一些数论和代数问题。比如说分数在写成某个进制下的小数时的循环节长度，就和分圆多项式有密切的联系。对于这些具体的应用，有兴趣的读者可以参考文末的资料。

有限域

有限域（finite field），也称作 Galois 域（Galois field），就是只有有限多个元素的域。有限域的结构由其元素个数唯一确定，且它的元素个数必然是素数的幂。

定理

大小为 $q$ 的域存在，当且仅当 $q$ 具有素数幂 $p^n$ 的形式。而且，这样的域在同构意义下唯一，记作 $\mathbf F_q$。素数 $p$ 是域 $\mathbf F_q$ 的特征，正整数 $n$ 为域扩张 $\mathbf F_q/\mathbf F_p$ 的次数。最后，$\mathbf F_q$ 是 $\mathbf F_p$ 上多项式 $x^q-x$ 的分裂域，且恰好包括 $x^q-x$ 的 $q$ 个互异的根。

证明

设域 $F$ 是有限域。域 $F$ 的特征必然有限，记作 $p$；故而，域 $F$ 有素子域 $\mathbf F_p$。而且，域 $F$ 必然是 $\mathbf F_p$ 上的有限扩张，扩张次数记作 $n$。作为 $\mathbf F_p$ 上的 $n$ 维向量空间，域 $F$ 有 $q=p^n$ 个元素。域 $F$ 的全体非零元构成群 $F^\times$，它的阶为 $q-1$，所以有 $x^{q-1}=1$。因此，$F=F^\times\cup\{0\}$ 的所有元素都满足 $x^q=x$，即它们是多项式 $x^q-x$ 的 $q$ 个互异的根。因此，在域 $F$ 中多项式 $x^q-x$ 有因子 $\prod_{\alpha\in F}(x-\alpha)$，但是这个因子的次数已经是 $q$ 且最高次项系数就等于 $1$，所以有 $x^q-x=\prod_{\alpha\in F}(x-\alpha)$。这说明 $x^q-x$ 在 $F$ 中分裂。对于任何能够使 $x^q-x$ 分裂的域，由于 $x^q-x$ 有 $q$ 个相异的根，必然至少有 $q$ 个元素。这说明 $F$ 是使 $x^q-x$ 可以分裂的最小的域，即 $x^q-x$ 的分裂域。总而言之，大小为 $q$ 的有限域必然是它的素子域上的多项式 $x^q-x$ 的分裂域。因为分裂域在同构意义下唯一，所以大小为 $q$ 的域必然也唯一。

反过来，给定素数 $p$ 和它的幂 $q=p^n$，要说明 $\mathbf F_p$ 上的多项式 $x^q-x$ 的分裂域恰好有 $q$ 个元素，才能说明所有素数幂 $q$ 阶的域都存在。因为 $\mathbf F_p$ 上的多项式 $x^q-x$ 的分裂域总是存在，所以可以设该分裂域中多项式 $x^q-x$ 的全部根组成的集合为 $F$。现在要证明 $F$ 是域，因而它就是多项式 $x^q-x$ 的分裂域本身。但是，迭代 $n$ 次 Frobenius 自同态就可以知道 $x\mapsto x^q$ 也是自同态，因此对任意 $\alpha,\beta\in F$ 都有 $(\alpha\pm\beta)^q=\alpha^q\pm\beta^q$，$(\alpha\beta)^q=\alpha^q\beta^q$ 和 $(\alpha^{-1})^q=(\alpha^q)^{-1}$。因此，集合 $F$ 对加、减、乘、除都封闭，它是域。这就说明 $F$ 就是 $\mathbf F_p$ 上的多项式 $x^q-x$ 的分裂域。

推论

有限域 $\mathbf F_q$（$q>2$）中，全体非零元的和是 $0$，积是 $-1$。

证明

有限域的全体非零元恰好是多项式 $x^{q-1}-1$ 的 $q-1$ 个根，应用 Vieta 定理即可。

在素域 $\mathbf F_p$ 中，这个推论关于积的结论正是数论中的 Wilson 定理（的一部分）。

乘法结构

有限域的乘法群 $\mathbf F^\times=\mathbf F\setminus\{0\}$ 一定是循环群。

定理

域 $F$ 的乘法群的有限子群一定是循环群。

证明

设 $G$ 为域 $F$ 的乘法群的子群且 $|G|=n$。因而，$G$ 是有限 Abel 群。根据有限 Abel 群基本定理，群 $G$ 有不变因子分解 $C_{n_1}\times\cdots\times C_{n_s}$ 且 $n_1\mid\cdots\mid n_s$。所以，对于 $G$ 中的所有元素 $x$，都有 $x^{n_s}=1$。也就是说，群 $G$ 中的元素都是域 $F$ 上多项式 $x^{n_s}-1$ 的根。但是，多项式 $x^{n_s}-1$ 至多有 $n_s$ 个相异的根，即 $n\le n_s$。但是，$n_s\le n$，所以其实有 $n_s=n$。这说明 $G\cong C_{n_s}$，即群 $G$ 是循环群。

推论

有限域 $\mathbf F_q$ 的乘法群 $\mathbf F_q^\times\cong C_{q-1}$。

循环群 $\mathbf F_q^\times$ 中有 $\varphi(q-1)$ 个生成元，它们称为有限域的本原元；其中，$\varphi(n)$ 是欧拉函数。

本原元

有限域 $\mathbf F_q$ 的乘法群的生成元，称为 $\mathbf F_q$ 的 本原元（primitive element）。

单扩张中的本原元和有限域中的本原元并不相同

尽管单扩张中的本原元和有限域中的本原元的名称一致，两者并不相同。单扩张中的本原元是相应的单扩张的生成元，而有限域中的本原元是相应的乘法群（作为循环群）的生成元。有限域作为它的素子域的单扩张的本原元，未必是有限域本身的本原元。例如，$\mathbf F_{25}\cong\mathbf F_5[x]/(x^2+x+1)$ 中，$\overline x$ 是域扩张的本原元，但是并不是域 $\mathbf F_{25}$ 的本原元，因为它的阶数是 $3$。

$\mathbf F_{q}$ 中的本原元和模 $q$ 的原根也不相同

对于奇数特征的有限域 $\mathbf F_{q}$，总是存在模 $q$ 的原根（primitive root）。但是，不应将它与有限域 $\mathbf F_{q}$ 中的本原元（primitive element）混淆。虽然它们都是相应的乘法结构作为循环群时的生成元，但是 $(\mathbf Z/q\mathbf Z)^\times$ 和 $\mathbf F_q$ 在 $q$ 本身不是素数的情况下并不相同。比如，前者的阶是 $\varphi(q)$ 而后者的阶是 $q-1$，两个乘法群的大小就不相同。

设 $\alpha$ 是有限域 $\mathbf F_q$ 的一个本原元。那么，对于所有 $x\in\mathbf F_q$ 都存在唯一的自然数 $k

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用