$\gcd(a,b)$ in non-Euclidean domains.

Question

I wanted to enquire about the nature of the greatest common divisors of two elements in an integral domain $D$.

Let $a,b\in D$. My book has led me to believe there can be multiple $\gcd(a,b)$.

1. How do we find $\gcd(a,b)$ in non-Euclidean domains?

2. Is $\gcd(a,b)$ unique up to units? I feel so. Because if $m$ and $n$ are two gcds of $a$ and $b$, then $m|n$ and $n|m$.

Thanks in advance!

Answer 1

We can define a greatest common divisor of $a,b\in D$, where $D$ is a (commutative) integral domain:

$d\in D$ is a gcd of $a$ and $b$ when the following conditions hold

1. $d\mid a$ and $d\mid b$
2. For all $c\in D$, if $c\mid a$ and $c\mid b$, then $c\mid d$

Writing $x\mid y$ means there exists $z$ such that $y=xz$; in the sequel, everything is supposed to be in $D$.

Lemma. If $x\mid y$ and $y\mid x$, then there exists $u$ invertible such that $y=ux$.
Proof. From $y=xz$ and $x=yz'$ we can deduce $x=xzz'$; since we are in a domain, we have two cases: $x=0$ or $zz'=1$. If $zz'=1$, the thesis is proved. If $x=0$, then $y=xz=0z=0=1x$.$\quad\square$

In this case we say $x$ and $y$ are associate with each other.

Proposition. If $d_1$ and $d_2$ are both gcd of $a$ and $b$, then they are associate.
Proof. Just use the definition, first with $d=d_1$ and $c=d_2$, then with $d=d_2$ and $c=d_1$, to conclude that $d_2\mid d_1$ and $d_1\mid d_2$.$\quad\square$

Thus the gcd, if it exists, is unique up to multiplication by invertible elements.

However, the gcd may fail to exist and the example $D=\mathbb{Z}[\sqrt{-5}]$ is perhaps the easiest. It exists when $D$ is a unique factorization domain, by applying the well known method of considering the common irreducible factor with their minimum exponent (no common irreducible factor means $1$ is a gcd). How do you find it? There is no general method except in Euclidean domains, where Euclid's algorithm returns a gcd.

Note that being associate defines an equivalence relation $\sim$ on $D$ and, on the quotient set $D/~$ the relation $$ [a]_\sim\le[b]_\sim\qquad\text{if and only if}\qquad a\mid b $$ is an order relation ($[a]_\sim$ denotes the equivalence class of $a$). In this order relation, the (equivalence class of a) gcd of $a$ and $b$ is just the greatest lower bound of (the equivalence classes of) $a$ and $b$.

Answer 2

Unfortunately, there may be no gcd in a ring if it does not have unique factorisation.

A standard example is given by the following facts:

In the ring $\Bbb{Z}[\sqrt{-5}]$, the numbers $6$ and $2(1+\sqrt{-5})$ both have factors $2$ and $1+\sqrt{-5}$, and so have no greatest common divisor.

Answer 3

In some integral domains there need not even exist a gcd in general. For example, take $D=\mathbb{Z}[\sqrt{-3}]$, and $a=4$, $b=2+2\sqrt{-3}$. Then there is no gcd of $a$ and $b$.