欧几里得整环

在整数中，用余数替换原来的数会让绝对值下降；在多项式中，同一过程让次数下降。欧几里得函数把这两种“越除越小”放在同一个框架下：每次非零余数的尺寸都严格减小，直到余数为零。

带余除法还保持共同因子，因为 $r=a-bq$ 与 $a=bq+r$ 可以互相还原。因此终止时得到的最后一个非零项是最大公因子，回代则给出 Bézout 表示。这里的尺寸只负责衡量下降，可以是绝对值、次数或另一个合适的量。

$\mathbb{Z}$ 使用 $\delta (n)=|n|$，域 $F$ 上的 $F[x]$ 使用多项式次数。域本身也满足定义：对 $b\ne 0$，取 $q=a/b$、$r=0$，一次除法就结束。

在高斯整数 $\mathbb{Z}[i]$ 中使用范数

对 $\beta \ne 0$，把复数 $\alpha /\beta$ 的实部、虚部分别舍入到最近整数，得到格点 $q\in \mathbb{Z}[i]$。两个方向的舍入距离都不超过 $1/2$，所以

这就构造了尺寸严格下降的余数。若某个坐标恰在两个整数中间，向两侧舍入都可以，商余未必唯一；算法只需选定其中一组即可继续。

欧几里得整环的每个理想理路理想Ideal对加法成子群且吸收环乘法的子集。都由一个元素生成。证明时，在非零理想 $I$ 中选取 $\delta$ 最小的非零元素 $b$。对任意 $a\in I$ 做带余除法，余数 $r=a-bq$ 仍在 $I$ 中；若 $r\ne 0$，其尺寸比 $b$ 小，与选择矛盾。因此 $r=0$，所有 $a$ 都是 $b$ 的倍数，即 $I=(b)$。零理想则由 $0$ 生成。

于是得到“欧几里得整环 ⇒ 主理想整环理路主理想整环Principal ideal domain · PID每个理想都由单个元素生成的整环。 ⇒ 唯一分解整环理路唯一分解整环Unique factorization domain · UFD每个非零非单位元素都能唯一地分解为不可约元乘积的整环。”的层级。存在不是欧几里得整环的主理想整环，因而第一步不能反推。欧几里得结构的额外价值在于给出求 gcd 和 Bézout 系数的带余除法路线；在整数、多项式等具有可执行算术的表示中，这条路线又成为模逆和因式分解算法的工具。

高斯整数的最近格点除法还可以落实为完整的计算证书。高斯整数精确算术理路高斯整数的精确算术Gaussian integers · 高斯整数 · Gaussian integer arithmetic把整数格点看成可整除的复数，用范数下降计算GCD与Bézout系数，并以显式核验完成高斯商环中的约简和求逆。用两次除法求出29与12+i的GCD，保留Bézout等式，并把模5−2i的求逆化成普通模29运算。这里复用本页已经证明的范数下降，不另假设余数唯一。