On this Wiki page it is written:

A GCD domain is an integral domain $R$ with the property that any two non-zero elements have a greatest common divisor (GCD). Equivalently, any two non-zero elements of $R$ have a least common multiple (LCM).

How to prove last statement that is equivalence of GCD and LCM for all elements? (I am able to prove in Bezout ring but I am not able to prove in general GCD ring.)

Does the existence of gcd of two elements implies existence of lcm and conversely in any integral domain?

  • $\begingroup$ See this answer (and its comments): math.stackexchange.com/a/81580/1242 $\endgroup$ – Hans Lundmark Sep 26 '15 at 8:35
  • 2
    $\begingroup$ If $a$ and $b$ have an LCM $m$, it's not too difficult to check that $d=ab/m$ is a GCD of $a$ and $b$. But the argument doesn't work the other way around. A classical counterexample: let $R$ be the subring of $\mathbf{Z}[X]$ consisting of the polynomials $\sum c_k X^k$ such that $c_1$ is an even number. Then $d=1$ is a GCD of $a=2$ and $b=2X$ in $R$ (note that $b$ is not divisible by $2$ in $R$), but $a$ and $b$ have no LCM (both $4X$ and $2X^3$ are multiples of $a$ and $b$, but they have no factor in common that is a multiple of both $a$ and $b$). $\endgroup$ – Hans Lundmark Sep 26 '15 at 8:47
  • $\begingroup$ @HansLundmark How to prove that $ab$ is a multiple of $m$? $\endgroup$ – user150248 Sep 3 '18 at 1:25
  • 1
    $\begingroup$ @user150248, isn't it just the definition of lcm? I.e., $ab$ is a common multiple of $a$ and $b$, so it's divisible by their least common multiple $m$ (provided the lcm exists). See en.wikipedia.org/wiki/… $\endgroup$ – Barry Cipra Sep 3 '18 at 2:45

The result that is given in Wikipedia without proof is an immediate corollary of the following:

Theorem: Let $D$ be a domain and $a,b\in D$. TFAE $\colon$

i) $\text{lcm}(a,b)$ exists.

ii) For all $r\in D\setminus\{0\}$, $\gcd(ra,rb)$ exists.

Proof: i)$\implies$ ii) Let's call $\text{lcm}(a,b)=m$. We have $a\mid ab$ and $b\mid ab$, then $m\mid ab$. We claim that $\gcd(a,b)=ab/m$. Indeed, $$a=\frac{ab}{m}\frac{m}{b}\implies \frac{ab}{m}\mid a,$$ $$b=\frac{ab}{m}\frac{m}{a}\implies \frac{ab}{m}\mid b.$$

Thus, $ab/m$ is a common divisor of $a$ and $b$.

Let $e\in D$ such that $e\mid a$ and $e\mid b$. Then, $e \mid ab$, so that $ab/e$ is an integer. Moreover, $a \mid ab/e$ (since $e \mid b$) and $b \mid ab/e$ (likewise), whence $m \mid ab/e$. That is, $em\mid ab$. Hence $e\mid ab/m$, and this shows that $\gcd(a,b)=ab/m$.

Set $\gcd(a,b)=ab/m=d$. Given $r\neq 0$, we claim that $\gcd(ra,rb)=rd$. Indeed, $d\mid a$ and $d\mid b$ implies that $rd\mid ra$ and $rd\mid rb$. Let $s\in D$ such that $s\mid ra$ and $s\mid rb$. Then, $rab/s$ is an integer and satisfies $a \mid rab/s$ (since $s \mid rb$) and $b \mid rab/s$ (likewise), so that $m \mid rab/s$. Hence, $sm\mid rab$. Therefore $s\mid rab/m=rd$. This proves that $\gcd(ra,rb)=rd$.

ii)$\implies$ i) We claim that $$\text{lcm}(a,b)=\frac{ab}{\gcd(a,b)}.$$

Indeed, set $d=\gcd(a,b)$, then $$\frac{ab}{d}=a\frac{b}{d},$$ $$\frac{ab}{d}=b\frac{a}{d}.$$

So $a\mid ab/d$ and $b\mid ab/d$. Let $n\in D$ such that $a\mid n$ and $b\mid n$, thus $ab\mid nb$ and $ab\mid na$. It follows that $ab\mid \gcd(na,nb)=n\gcd(a,b)$, i.e., $ab\mid nd$ and then $\frac{ab}{d}\mid n$. Hence, $\text{lcm}(a,b)=ab/d$.

The above theorem is used in this paper (Dinesh Khurana, On GCD and LCM in domains -- A conjecture of Gauss, Resonance, 8(6), 72–79) by D. Khurana where he proves that for every $n\ge 3$ non-square $\Bbb{Z}[\sqrt{-n}]$ is not a GCD-domain, and hence not a UFD. More exactly, he shows that if $n+1=pk$ for some prime $p$ and $k\ge 2$, then $\text{lcm}(p,1+\sqrt{-n})$ doesn't exist; and if $n+1$ is prime then $\text{lcm}(2,2+\sqrt{-n})$ doesn't exist. So we have an alternative proof to the fact that $\Bbb{Z}[\sqrt{-n}]$ is not a UFD for $n\ge 3$.

| cite | improve this answer | |
  • 2
    $\begingroup$ When you are proxing that ii) follows from i) you have used that $\text{lcm}(ea,eb)=e\text{lcm}(a,b)$. Could you clarify it, please? $\endgroup$ – ZFR May 25 '18 at 9:19
  • 1
    $\begingroup$ @ZFR and Xam: I've fixed the uses of lcm's other than of $a$ and $b$ (it's been mostly a notational issue). $\endgroup$ – darij grinberg Aug 15 '19 at 21:25
  • $\begingroup$ While I do understand the proof of i) $\Longrightarrow$ ii) now, here's a question on the other direction: Why is $\gcd\left(na,nb\right) = n\gcd\left(a,b\right)$ ? I am used to proving this using Bezout's identity. $\endgroup$ – darij grinberg Aug 15 '19 at 22:23
  • 1
    $\begingroup$ Ah, I see. From $n \mid na$ and $n \mid nb$, we obtain $n \mid \gcd\left(na,nb\right)$, and thus $\gcd\left(na,nb\right) = nu$ for some $u \in D$. Now, $nu = \gcd\left(na,nb\right) \mid na$, so that $u \mid a$ and similarly $u \mid b$. Hence, $u \mid \gcd\left(a,b\right)$. Thus, $nu \mid n\gcd\left(a,b\right)$. Hence, $\gcd\left(na,nb\right) = nu \mid n\gcd\left(a,b\right)$. Combining this with $n\gcd\left(a,b\right) \mid \gcd\left(na,nb\right)$ (which follows from the obvious divisibilities $n\gcd\left(a,b\right) \mid na$ and $n\gcd\left(a,b\right) \mid nb$), we ... $\endgroup$ – darij grinberg Aug 15 '19 at 22:25
  • $\begingroup$ ... obtain $\gcd\left(na,nb\right) = n\gcd\left(a,b\right)$ (up to unit factors). $\endgroup$ – darij grinberg Aug 15 '19 at 22:25

I want to make a few supplements to the above good answer by Xam. If $R$ is an integral domain and $gcd(a,b)$ exists, then $lcm(a,b)$may not exist.

Consider $Z[\sqrt{-3}]$. Let $a = 2$ and $b = 1+\sqrt{-3}$. If $lcm(2,1+\sqrt{-3})$ exists, then $lcm(2,1+\sqrt{-3})$ $\mid$ $2(1+\sqrt{-3})$ and $lcm(2,1+\sqrt{-3})$ $\mid$ $2(1-\sqrt{-3})$(because $2(1-\sqrt{-3}) = -(1+\sqrt{-3})(1+\sqrt{-3})$). However, the factors of $2(1+\sqrt{-3})$ are $2, (1+\sqrt{-3})$ and $(1-\sqrt{-3})$.

Thus $lcm(2,1+\sqrt{-3})$ must be equal to $2(1+\sqrt{-3})$. In the same way, according to $lcm(2,1+\sqrt{-3})$ $\mid$ $2(1-\sqrt{-3})$, we have $lcm(2,1+\sqrt{-3})$ must be equal to $2(1-\sqrt{-3})$. This is a contradiction.

Actually, $gcd(4,2(1+\sqrt{-3}))$ doesn't exist,but$gcd(2,1+\sqrt{-3}) =1$

| cite | improve this answer | |

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.