Is it possible for the Euclidean algorithm to fail by not terminating in finite time in non-Euclidean domains? In $\mathbb{Z}[X]$ it can fail by going out of the ring, ie one gets a non integer element.
I asked my prof, and he told me his intuition told him they should but he couldn't think up an example on the spot. Does anybody know of an explicit example?
In a Euclidean domain $R$ you require the existence of a function $f : R \setminus \{ 0 \} \to \Bbb{N}$ such that for $a, b \in R$, $b \ne 0$, there exist $q, r \in R$ such that $a = b q + r$, and either $r = 0$, or $f(r) < f(b)$.
If this is the case, then one could construct a fairly pathological example by taking $R = \Bbb{Q}[x]$, and letting $f = \deg$ take values in $\Bbb{N}$ with the reverse ordering (except for zero, perhaps), that is, division takes the form $$ a = b q + r,\qquad \text{with $\deg(r) > \deg(b)$}. $$ So when you divide the degree of the remainder increases each time, and there's no chance of stopping. For instance with $a = x$, $b = x^2$, a legal division would be $$ x = x^2 \cdot x + (x - x^3), $$ where $q = x$ and $r = x - x^3$.