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!

  • $\begingroup$ There is a class of rings called "GCD Domains" or "GCD Rings" that may interest you. Look it up. $\endgroup$ – user96815 Oct 18 '13 at 10:37
  • $\begingroup$ you said that there can be multiple $\gcd(a,b)$. Could you provide an example of a ring with this property? $\endgroup$ – KirkLand Oct 29 '17 at 18:26

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


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.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.