# 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.

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.

• Thanks. ${\Bbb Z}[x]$ is a trivial domain that I missed. Can you give an example of a domain which has finite elements? Oct 4, 2018 at 12:16
• @AtivJoshi Every finite integral dpmain is a field. Oct 4, 2018 at 12:21

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.

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!

• That's not a particularly evil example: $1$ is a gcd. Oct 15, 2018 at 22:00
• @Arturo So what are the Euclidean steps in which the norm of the remainder is always less than the norm of the divisor? e.g., $1 + \sqrt{-5} = 2m + r$, with $r < 4$? Oct 16, 2018 at 0:20
• @ArturoMagidin It's not the only potential choice, but it is the one the answerer gave. Sure, you can contrive a function $f(n)$ such that the $r$ in $2m + r$ or $(1 + \sqrt{-5})m + r$ satisfies $f(r) < f(2)$ or $f(r) < f(1 + \sqrt{-5})$, but can you contrive a function that will enable the Euclidean algorithm for any pair of numbers in this domain? Oct 16, 2018 at 15:30
• @ArturoMagidin I could be wrong, but I think he meant to write "compute $\gcd(2, 1 + \sqrt{-5})$ using the Euclidean algorithm." Oct 16, 2018 at 16:53
• I think he meant for the two of you to argue rancorously about some minor detail, carried away by your testosterone. It looks like he succeeded.
– Lisa
Oct 16, 2018 at 21:31

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.