GCD in arbitrary domain

Is there a domain where computing GCD of two elements is not trivial (i.e. Euclid's algorithm will not work)? AFAIK we can always use the Euclid's algorithm in a Euclidean Domain.

Solution 1:

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.

Solution 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

Solution 3:

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.

Solution 4:

AFAIK we can always use the Euclid's algorithm in a Euclidean Domain.

Well, yeah, that is kind of the definition. Surely then you know about non-Euclidean domains. The Euclidean algorithm will not work on those.

Do you know about the domain $\mathbb{Z}[\sqrt{-5}]$, consisting of numbers of the form $a + b \sqrt{-5}$, where $a$ and $b \in \mathbb{Z}$? Sorry to give such a hackneyed example, but try to compute $\gcd(2, 1 + \sqrt{-5})$. The Euclidean function is $a^2 + 5b^2$. Good luck. Mwahahahahahahahahahahahaha!

Solution 5:

Some dictionary definitions might be helpful.

A number $a$ in a ring $R$ is said to be an associate of a number $n \in R$ if there is a unit $u \in R$ such that $a = un$.

For example, in $\mathbb Z[i]$, $-7i$ is an associate of 7 since $-7i = (-i) \times 7$. Okay, this might not seem too relevant just yet.

A ring $R$ is said to be a unique factorization domain if every nonzero number $n$ has a factorization into units and prime factors, and the combination of prime factors is distinct and unique to $n$ and its associates (ordering is irrelevant if multiplication is commutative).

A unique factorization domain might also be a Euclidean domain, or it might not be. For now I'll skip over the concept of principal ideal domains.

A ring $R$ is said to be a Euclidean domain if there exists at least one function $f$, satisfying the requirements for use in the Euclidean algorithm, such that for any pair of nonzero numbers, the Euclidean algorithm using $f$ can be completed to a result.

These are the requirements for a function $f$ to be used in the Euclidean algorithm:

• $f(n) = 0$ if and only if $n = 0$, otherwise $f(n) > 0$ and $f(n) \in \mathbb Z$.
• If $d$ is a non-associate divisor of non-unit $n$, then $f(d) < f(n)$ (I think it's required that if $a$ is an associate of $n$ then $f(n) = f(a)$).

In good ol' $\mathbb Z$, the usual choice is the absolute value function. It is the best choice, in my opinion. But there are many other functions that will do just fine, at least in theory if not practicality, like $f(n) = 1729n^4$.

In many domains of algebraic integers, like imaginary quadratic integer rings, the norm function is a frequent choice, leading to this definition:

An Euclidean domain $R$ is said to be a norm-Euclidean domain if the domain is Euclidean for the norm function (or the absolute value of the norm function, if the norm function in $R$ can give negative values).

So here are some examples of domains that fall at different places in the Venn diagram drawn from the preceding definitions:

• Norm-Euclidean and unique factorization domain: $\mathbb Z[\sqrt 2]$, since this domain is Euclidean for the absolute value of the norm function.
• Euclidean and unique factorization domain, but not norm-Euclidean: $\mathcal O_{\mathbb Q(\sqrt{69})}$, since this domain is not Euclidean for the absolute value of the norm function, e.g. $$\gcd\left(\frac{23}{2} + \frac{3 \sqrt{73}}{2}, 18 + 2 \sqrt{73}\right),$$ but it is Euclidean for a specially adjusted norm function. As a matter of practicality, it is best to just do GCD by prime factorization in this domain.
• Unique factorization domain but not Euclidean: $\mathcal O_{\mathbb Q(\sqrt{-19})}$, which I mention in antoher answer.
• Neither Euclidean nor unique factorization domain: $\mathbb Z[\sqrt{10}]$, try to resolve $\gcd(2, \sqrt{10})$ by the Euclidean algorithm with whatever suitable function you can think of. If you find one that works for that pair, let me know in the comments. Of course it won't work for some other pair.