设$R$是 integral domain，并且存在一个赋值$\delta$，满足$\forall a,b\in R,b\ne 0\implies\exists q,r\in R,a=bq+r$，且要么$r=0$，要么$\delta(r)<\delta(b)$。构造一个赋值$\phi$使得$R$是 Euclidean domain。
这可以说是众所周知的东西了，英文wiki中很醒目的地方都写着。但是，我做作业做到这道题的时候却偏偏不知道这个构造，因此想了很久，最后自己想出来了（这是意料之外的）。我发现思维过程还挺有趣的，而且貌似和常规思路不太一样，就专门写了一篇博客。
首先，注意到$\delta$恰已满足了欧氏赋值（Euclidean function）的性质1，于是最自然的想法就是，看看$\delta$为何可能违反性质2，即$\forall a,b\in R^{*},\delta(a)\le \delta(ab)$。于是我们假设$\exists a,b\in R^{*},\delta(a)>\delta(ab)$。这能推出什么呢？由于我们对于$\delta$除了性质1之外一无所知，只能尝试对某两个元素使用性质1。而如果设$ab=aq+r$，就直接有$q=b,r=0$满足条件了，因此毫无帮助。而设$a=(ab)q+r$是一条看起来比较有希望的路：我们希望尽量能让$r\ne 0$，这样才能用到$\delta(r)<\delta(b)$，不然无法和$\delta(a)>\delta(ab)$联系起来。
而如果$a=(ab)q+r$中$r=0$，会怎么样呢？因此有$a=abq$，由于$R$是 integral domain，就有$bq=1$，于是$b$是一个单位（可逆元）。这在一个环里是非常不平凡的情况，因此很有希望。于是我们假设$b$不是单位，就必有$r\ne 0$，$\delta(r)<\delta(ab)$。同时$a=(ab)q+r\implies r=a(1-bq)$，根据我们的假设，$1-bq$仍然是非零元；因此我们可以把$1-bq$作为新的$b$，重复前面的全部推理！
但这有什么用呢，不是困在死循环里了吗？但注意到，我们的$\delta(ab)$在每次迭代中都会严格减少（$\delta(ab_{n+1})=\delta(a(1-b_nq))=\delta(r)<\delta(ab_n)$），但是这是一个只能取自然数值的函数，不可能无限减少下去！因此，迭代是有限的；而唯一跳出迭代的条件，就是$b$是单位。因此我们证明了，如果存在$\delta(a)>\delta(ab)$，就一定有至少一个可逆的$b$，满足$\delta(a)>\delta(ab)$。
定义$x\sim y\iff \exists \mu$为单位，$x=\mu y$。众所周知，这是一个等价关系。因此一旦有两个元素不满足性质2，就会有同一等价类中的两个元素违背性质2。这是一个很有希望修复的事情：很直观的想法是把每个等价类中的全部元素的$\delta$赋值成其代表元的$\delta$（又是该死的选择公理），就肯定满足性质2了。我们只需要验证，如此构造的$\phi$仍然满足性质1即可。看起来离成功不远了！
我们的目的是构造$a=bq+r$的$q$和$r$，而注意到如果这个式子中的全部元素都已经是各自等价类中的代表元，那么$\phi$就直接满足了（因为它压根就是$\delta$）。但不一定总是如此，因此我们需要从代表元的情况构造普通情况。设$a=\mu_1\bar{a},b=\mu_2\bar{b}$，其中$\bar{a},\bar{b}$是$a,b$所在等价类各自的代表元。因此有$\bar{a}=\bar{b}q+r$，并且要么$r=0$，要么$\delta(r)<\delta(\bar{b})$。
\[\bar{a}=\bar{b}q+r \implies \mu_1^{-1}a=\mu_2^{-1}bq+r\implies a=b(q\mu_1\mu_2^{-1})+\mu_1r\]如果$\mu_1 r=0$，已经满足；如果$\mu_1 r\ne 0$，必有$r\ne 0$，因此$\delta(r)<\delta(\bar{b})$。只需要说明$\phi(\mu_1r)<\phi(b)$。注意到$\bar{b}$是代表元，已经有$\phi(b)=\delta(\bar{b})$了；可我们猛然发觉，对于左半边，目前还毫无约束：只知道$\phi(\mu_1 r)=\delta(\overline{\mu_1 r})=\delta(\overline{r})$，可$\delta(\bar{r})$与$\delta(r)$毫无关系！
所幸，这个bug是可以修的。一个自然的想法就是，我们如果把$\bar{r}$定义成$r$的等价类之中“$\delta$最小的元素”，于是就能保证$\phi(\mu_1 r)=\delta(\bar{r})\le \delta(r)<\delta(\bar{b})=\phi(b)$，因此就得证了性质1。我们回顾一下，只要一个函数$f$满足性质1，无论它是$\delta$还是$\phi$，一旦有$f(a)>f(ab)$，就必存在一个可逆的$b$，使得$f(a)>f(ab)$。因此如果$\phi$不满足性质2，就存在$a,\mu\in R$，$\mu$是单位，$\phi(a)>\phi(\mu a)$。可按照$\phi$的定义，它们都等于$\delta(\bar{a})$，因此是不可能的。因此这个$\phi$真的是一个 Euclidean function。大功告成了？
且慢！所谓“$\delta$最小的元素”真的是一个良定义吗？一个等价类完全可以是无限集，谁又能保证存在最小的元素呢？我们的救命稻草还是$\delta$只能取自然数值：一个非空的自然数集是必定存在最小元素的！因此在$r$的等价类中，确实存在一个元素$\bar{r}$，使得$\forall r\sim s,\delta(\bar{r})\le \delta(s)$。这样就彻底做完了（或者有什么我尚未察觉的疏漏）。
