欧几里得整环

欧几里得函数给非零余数一个严格下降的“尺寸”，保证不断除法不会无限进行，并把理想中的最小元素变成生成元。Euclid 整环把整数除法算法抽象成一种可下降的“大小”函数。对任意 $a,b\ne 0$，都能写成 $a=bq+r$，且余数为零或比 $b$ 更小；反复下降后必然终止。真正重要的是这种可终止的除法过程，而不是大小函数必须像绝对值那样满足所有直觉性质。

$\mathbb{Z}$ 以 $\delta (n)=|n|$ 为欧几里得函数；域 $F$ 上的 $F[x]$ 以次数为函数。任意域也可视为欧几里得整环，因为除法余数总可取 $0$。高斯整数 $\mathbb{Z}[i]$ 可用范数 $a^2+b^2$。定义只要求存在某个 $q,r$，不要求商余唯一；在 $\mathbb{Z}$ 中不同余数约定仍可满足下降。所有欧几里得整环都是 PID，但存在 PID 不是欧几里得整环，所以逆命题不成立。仅有“可计算某种除法”而无良基下降，也不能推出算法终止。

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

对 $\alpha ,\beta \ne 0$，把复数 $\alpha /\beta$ 的实部、虚部分别舍入到最近整数，得到 $q\in \mathbb{Z}[i]$，余数 $r=\alpha -\beta q$ 满足 $N(r)<N(\beta )$。因此 Euclid 算法不仅适用于整数和一元多项式，也适用于某些二维格点环。商与余数不必唯一；定义只要求总能选到严格下降的余数。

欧几里得结构提供gcd 算法、模逆、Bézout 恒等式和多项式因式分解的基础，并建立 ED⇒PID⇒UFD 的分解层级。Euclid 算法使每个有限生成理想化为一个生成元，因此 Euclid 整环公理库整环Integral domain含单位元 1≠0、无零因子的交换环。必为 主理想整环公理库主理想整环Principal ideal domain · PID每个理想都由单个元素生成的整环。，进而是 唯一分解整环公理库唯一分解整环Unique factorization domain · UFD每个非零非单位元素都能唯一地分解为不可约元乘积的整环。。这条链解释了为何 gcd、Bézout 等式和不可约分解在整数与一元多项式中都可有效计算。