I have the following example of an integral domain with two elements that do not have a gcd from wikipedia:

$R = \mathbb{Z}\left[\sqrt{-3}\,\,\right],\quad a = 4 = 2\cdot 2 = \left(1+\sqrt{-3}\,\,\right)\left(1-\sqrt{-3}\,\,\right),\quad b = \left(1+\sqrt{-3}\,\,\right)\cdot 2.$

The elements $2$ and $1 + \sqrt{−3}$ are two "maximal common divisors" (i.e. any common divisor which is a multiple of $2$ is associated to $2$, the same holds for $1 + \sqrt{−3}$), but they are not associated, so there is no greatest common divisor of a and b.

I can understand it, but how can I prove or strictly explain that $2$ and $1 + \sqrt{−3}$ are two "maximal common divisors" and they are not associated?

  • 2
    $\begingroup$ What can the norm of a common divisor be? What elements have those norms? $\endgroup$ – Qiaochu Yuan May 5 '11 at 2:21
  • $\begingroup$ @Yuan I found the concept of multiplicative norms, defined by $N(a+b\sqrt{-3})=a^2+3b^2$ in here. Do you mean this? $\endgroup$ – Gobi May 8 '11 at 5:11

A simple but general way to deduce that this gcd fails to exist is by failure of Euclid's Lemma.

Lemma $\rm\ \ (a,b) = (ac,bc)/c\ \ $ if $\rm\ (ac,bc)\ $ exists $\rm\quad$ [GCD distributive law]

Proof $\rm\quad d\ |\ a,b\iff dc\ |\ ac,bc\iff dc\ |\ (ac,bc)\iff d\mid (ac,bc)/c$

But generally $\rm\ (ac,bc)\ $ need not exist, as is most insightfully viewed as failure of

Euclid's Lemma $\rm\quad a\ |\ bc\ $ and $\rm\ (a,b)=1\ \Rightarrow\ a\ |\ c\ \ $ if $\rm\ (ac,bc)\ $ exists.

Proof $\ \ $ If $\rm\ (ac,bc)\ $ exists then $\rm\ a\ |\ ac,bc\ \Rightarrow\ a\ |\ (ac,bc) = (a,b)\,c = c\ $ by the Lemma.

Hence if $\rm\, a,b,c\, $ fail to satisfy the Euclid Lemma $\Rightarrow,\,$ namely if $\rm\ a\ |\ bc\ $ and $\rm\ (a,b) = 1\ $ but $\rm\ a\nmid c\,$, then one immediately deduces that the gcd $\rm\ (ac,bc)\ $ fails to exist.$\,$ For the special case that $\rm\,a\,$ is an atom (i.e. irreducible), the implication reduces to: atom $\Rightarrow$ prime. So it suffices to find a nonprime atom in order to exhibit a pair of elements whose gcd fails to exist. This task is a bit simpler, e.g. for $\rm\ \omega = 1 + \sqrt{-3}\ \in\ \mathbb Z[\sqrt{-3}]\ $ we have that the atom $\rm\, 2\ |\ \omega' \omega = 4,\,$ but $\rm\ 2\nmid \omega',\omega,\,$ so $\rm\,2\,$ is not prime. Therefore your gcd $\rm\, (2\omega,\, \omega'\omega) = (2+2\sqrt{-3},\,4)\ $ fails to exist in $\rm\ \mathbb Z[\sqrt{-3}]\,$.

Note that if the gcd $\rm\, (ac,bc)\ $ fails to exist then this implies that the ideal $\rm\ (ac,bc)\ $ is not principal. Therefore we've constructively deduced that the failure of Euclid's lemma immediately yields both a nonexistent gcd and a nonprincipal ideal.

That the $\Rightarrow$ in Euclid's lemma implies that Atoms are Prime $\rm(:= AP)$ is denoted $\rm\ D\ \Rightarrow AP\ $ in the list of domains closely related to GCD domains in my post here. There you will find links to further literature on domains closely related to GCD domains. See especially the referenced comprehensive survey by D.D. Anderson: GCD domains, Gauss' lemma, and contents of polynomials, 2000.

See also my post here for the general universal definitions of $\rm GCD,\, LCM$ and for further remarks on how such $\iff$ definitions enable slick proofs, and see here for another simple example of such.

  • $\begingroup$ Thanks for your great answer! I understood this and knew some other interesting concepts. Later I want to study them. $\endgroup$ – Gobi May 8 '11 at 5:05

I don't understand the concept ''maximal common divisors''. But I prove it directly.

Suppose that $d=\gcd{(4, 2(1+\sqrt{-3})}$ exists. Since $4=2\cdot 2=(1+\sqrt{-3})(1-\sqrt{-3})$, we get that $2$ and $1+\sqrt{-3}$ both are common divisor of $4$ and $2(1+\sqrt{-3})$. Thus, $2\mid d$ and $(1+\sqrt{-3})\mid d$.

Note that $2\mid d$ and $d\mid 4$ follows that $d\in\{\pm 1, \pm 2\}$. These $d$ can't satisfy $(1+\sqrt{-3})\mid d$.


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.