简单代数扩张的精确运算

Euclid 为什么同时产出逆元 ​

沿欧几里得整环理路欧几里得整环Euclidean domain带有允许带余除法并严格下降的欧几里得函数的整环。中的带余除法，从 $r_0=m,r_1=g$ 出发反复除法：

非零余式的次数严格下降，所以有限步后停止。相邻两项的公因子与下一对相同，因此最后非零项是 gcd 的一个非零常数倍。

为了把它写回输入，给每项保留 $r_i=A_{i}m+B_{i}g$。初值为

每次更新

这条关系由余式公式直接推出，所以每一步的表示都正确。如果末个非零余式为常数 $c\ne 0$，把全部系数除以 $c$，得到 $1=(A_i/c)m+(B_i/c)g$，逆元取 $B_i/c$。这里归一化不可漏掉：末项若是 $2$，原回代式只证明乘积为 $2$，还不是逆元。

一个完整的三次除法 ​

取 $F=\mathbb{Q}$、$m=x^3-x-1$。它的有理根只能是 $\pm 1$，而两处取值都是 $-1$，因此三次式不可约。令 $g=x^2+x+1$，做两轮除法：

第二式给 $1=g+(x+1)(-x)$；再用第一式中的 $-x=m-(x-1)g$ 回代，得到

所以

乘回也可以不用信任 Euclid 的过程。展开

用 $x^3\equiv x+1$、$x^4\equiv x^2+x$ 模 $m$ 约简，结果恰为 $1$。求逆与验逆是不同任务；验逆只需一次乘法和一次取余。

可约模多项式不会让所有元素失去逆元 ​

若把不可约的 $m$ 换成任意首一正次数多项式 $h$，唯一低次余式、加法和乘法仍然成立；但商环未必是域。此时 $g+(h)$ 可逆的准确条件是

充分性仍由 Bézout 证书给出。必要性则来自：若 $sg\equiv 1(\mathrm{mod}h)$，便有 $sg+th=1$，任何公共因子都必须整除 $1$。

例如在 $\mathbb{Q}[x]/(x^2-1)$ 中，$x-1$ 非零，却与同样非零的 $x+1$ 相乘为零；其 gcd 为 $x-1$，不能求逆。另一方面，$x$ 是单位，因为 $x^2\equiv 1$。因此检测到模多项式可约，意味着“不能保证每个非零元素可逆”，并不意味着每个非零元素都不可逆。

同一扩域中的逆元也不一定留在整数系数生成的子环中。在 $\mathbb{Q}(\sqrt{2})$ 内，$1/2$ 是 $2$ 的逆元，但不属于 $\mathbb{Z}[\sqrt{2}]$。本页运算的系数域是 $F$；不要将 $F[\alpha ]$ 与某个整系数子环混为一谈。

运算成本与一次迁移检查 ​

把一次 $F$ 中的加、减、乘、除计为一个域运算，且输入已经约简到次数小于 $d$。朴素加法需要 $O(d)$ 个域运算；朴素乘法加上长除法取余需要 $O(d^2)$ 个域运算。Euclid 至多进行 $d$ 轮非零余式下降，系数回代多项式的次数也不超过 $d$，因此按每轮至多 $O(d^2)$ 估算，得到保守的 $O(d^3)$ 求逆上界。这里没有声称这是最锐界。

这个计数把域运算当作原子操作。在 $F=\mathbb{Q}$ 中，分子分母的位数会增长，真实位复杂度还需计入整数运算与约分成本；若原输入次数远大于 $d$，最开始的约简成本也要另算。

自测：在同一个可约商环 $\mathbb{Q}[x]/(x^2-1)$ 中，$x+2$ 能求逆吗？能，因为

故逆元为 $(2-x)/3$。这里既展示了可约商环中的单位，也说明回代所得非零常数必须先归一化。

回到四次根式的运算证书 ​

已知 $\theta =\sqrt{2}+\sqrt{3}$ 的极小多项式为 $m=x^4-10x^2+1$，则

因此 ${\theta }^{-1}=10\theta -{\theta }^3$。原有根式恢复公式遂可以完全写成幂基坐标：

这些不是重新证明极小多项式；不可约性与次数已在原例理路极小多项式Minimal polynomial以给定代数元为根的首一不可约多项式。中完成。这里获得的是统一的算法接口：给定任意 $g(\theta )\ne 0$，都能用同一种 Euclid 过程求逆，而不必为每个分母单独猜一个根式共轭。