# Does Euclid lemma hold for GCD domains?

Exercise $10$ of Section $3$ of Chapter III of Hungerford’s Algebra states that if $R$ is a UFD and if $a,b$ are relatively prime, then $a | bc$ implies $a | c$, something that is easy to prove using the uniqueness of factorization into irreducibles. So I want to ask whether this holds if $R$ is just an integral domain (in order for divisibility to make sense) such that $\gcd(a,b)$ exists for all $a,b \in R$.

I can prove this property if I could show that $\gcd(x,y)\gcd(x,z)=\gcd(x,zy)$ or showing that $\gcd(x,y)=1=\gcd(x,z)$ implies $\gcd(x,zy)=1$, this is the part where I've been stuck.

Thanks.

-
"an integral domain such that gcd(a,b) exists for all a,b" what does that mean? If it means anything close to what I think it does, then $R$ is a PID and hence a UFD and so you're done. –  Dylan Wilson Feb 24 '13 at 21:50

Yes, Euclid's Lemma is true in gcd domains (domains where any two nonzero elements have a gcd), but the lemma may fail in domains where some gcds fail to exist (e.g. below). Below is some general discussion on this and related matters in an arbitrary integral domain.

Lemma $\rm\ \ (a,b)\ =\ (ac,bc)/c\quad$ 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|(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\quad$ 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.

Therefore 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 the 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 this post. 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 this post 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.

-

This holds true if all pairs of elements have a $\gcd$, in other words in a gcd-domain. However it fails if just $\gcd(a,b)$ is required to be defined.

To see the latter point, consider your favorite non-UFD, like $\mathbf Z[\sqrt{-5}]$ where $(1+\sqrt{-5})(1-\sqrt{-5})=6=2\times3$ are two distinct factorizations into irreducibles. Now with $a=2$, $b=1+\sqrt{-5}$ and $c=1-\sqrt{-5}$, one has $2=a\mid bc=6$ and $\gcd(a,b)=1$, but $a\not\mid c$.

That existence of all $\gcd$s implies that the implication is valid is explained in the other answers: supposing that $a\mid bc$, then since also $a\mid ac$ it follows that $a\mid\gcd(bc,ac)=\gcd(a,b)c=c$. Here the equality $\gcd(bc,ac)=\gcd(a,b)c$ (in the quotient set $R/{\sim}$, where $\sim$ is the equivalence relation of multiplication by invertible elements, because it is only there that $\gcd$ expression have a well-defined meaning) holds because on one hand $\gcd(a,b)c$ is a common divisor of $bc$ and $ac$, and on the other hand $\gcd(bc,ac)$, which is assumed to exist, divides $\gcd(a,b)c$: it is a multiple $xc$ of the common divisor $c$ of $ac$ and $bc$, and now $x$ must divide both $a$ and $b$ (since $xc$ divides $ac$ and $bc$) and therefore $x\mid\gcd(a,b)$.

By the way existence of all $\gcd$s does not imply that $R$ us a UFD, since it does not imply that factorisations into irreducibles exist in the first place.

Added. It may also be interesting to note if we replace the hypothesis $\gcd(a,b)=1$ for "$a,b$ are relatively prime" by the condition that $ab$ is a least common multiple of $a$ and $b$, then we get this instance of Euclid's lemma without having to require the existence of other $\def\lcm{\operatorname{lcm}}\lcm$s or $\gcd$s: from $a\mid bc$ and the obvious $b\mid bc$ follow $ab=\lcm(a,b)\mid bc$, and then by simplification by $b$ on gets $a\mid c$.

-
I've extended the sentence a bit to explain. –  Marc van Leeuwen Feb 25 '13 at 7:40

Let $R$ be a GCD domain and $x,y,z\in R$. Then $(xy,xz)=x(y,z)$.

Set $d=(y,z)$. Then $y=dy'$ and $z=dz'$ with $(y',z')=1$. Let $\delta=(xy,xz)$. Obviously $dx\mid\delta$, so $\delta=dxw$. Since $xy=\delta u$, $xz=\delta v$, it follows $dxy'=dxuw$ and therefore $y'=uw$. Similarly one gets $x'=vw$. Now it follows that $w=1$.

Let $R$ be a GCD domain and $x,y,z\in R$. If $(x,y)=1$ and $(x,z)=1$, then $(x,yz)=1$.

Take $\alpha$ a common divisor of $x$ and $yz$. Obviously $\alpha$ is a commun divisor of $xz$ and $yz$, so $\alpha\mid z$, and therefere it is $1$ because $(x,z)=1$.

Let $R$ be a GCD domain. Then $(a,b)=1$ and $a\mid bc$ implies $a\mid c$.

If $d=(a,c)$, then $a=da_1$, $c=dc_1$ and $(a_1,c_1)=1$. Since $a\mid bc$ we have $a_1\mid bc_1$. But $(a_1,b)=1$ and $(a_1,c_1)=1$, and thus $(a_1,bc_1)=1$. This shows that $a_1=1$, so $a\mid c$.

-
@Camilo The proofs are much clearer using the universal property/definition of gcd - see my answer. –  Math Gems Mar 3 '13 at 20:48
@YACP,what is your problem? –  Camilo Arosemena Mar 20 '13 at 20:21