GCD in arbitrary domain

Well, the Euclidean algorithm may not work in the integral domain ${\Bbb Z}[x]$, since in order to form the division of $f$ by $g$, the divisor $g$ need to be monic (or more generally, the leading coefficient must be invertible, here $\pm 1$).

Moreover, the gcd of $2$ and $x$ is 1, but has no representation $$2a+xb=1$$ for some $a,b$. The reason is that the polynomial on the left-hand side has constant coefficient divisible by 2.

SOME EXAMPLES OF PRINCIPAL IDEAL DOMAINS WHICH ARE NOT EUCLIDEAN AND SOME OTHER COUNTEREXAMPLES.

Abstract. It is well known that every Euclidean ring is a principal ideal ring. It is also known for a very long time that the converse is not valid. Counterexamples exist under the rings $R$ of integral algebraic numbers in quadratic complex fields $Q[\sqrt{D}]$ for $D =19, 43,67$, and $163$.

http://www.kurims.kyoto-u.ac.jp/EMIS/journals/NSJOM/Papers/38_1/NSJOM_38_1_137_154.pdf

At least in quadratic integer rings with unique factorization, if the Euclidean algorithm doesn't work, you can always just look at the prime factorization.

For example, of the infinitely many imaginary quadratic integer rings, only nine have unique factorization, and of those nine, only five are Euclidean.

In an answer to What is a concrete example to demonstrate that $\mathcal{O}_{\mathbb{Q}(\sqrt{-19})}$ is NOT a norm-Euclidean domain? I gave the example of $$\gcd\left(\frac{3}{2} + \frac{\sqrt{-19}}{2}, 10\right),$$ which by prime factorization of norms we can already tell is equal to 1.

But to try to do it by the Euclidean algorithm, we immediately run into trouble: $$\frac{10}{\frac{3}{2} + \frac{\sqrt{-19}}{2}} = \frac{15}{7} - \frac{5 \sqrt{-19}}{7}.$$

Rounding "down" (that is, towards 0), we get $$\frac{5}{2} - \frac{\sqrt{-19}}{2},$$ but then $$10 = \left(\frac{3}{2} + \frac{\sqrt{-19}}{2}\right)\left(\frac{5}{2} - \frac{\sqrt{-19}}{2}\right) + \left(\frac{3}{2} - \frac{\sqrt{-19}}{2}\right).$$ Almost as frustrating as some examples in non-UFDs.