# Showing that the elements $6$ and $2+2\sqrt{5}$ in $\mathbb{Z}[\sqrt{5}]$ have no gcd

In showing that the elements $6$ and $2+2\sqrt{5}$ in $\mathbb{Z}[\sqrt{5}]$ have no gcd, I was thinking of trying the following method.

If the ideal $(6)$ + $(2+2\sqrt{5})$ is not principle in $\mathbb{Z}[\sqrt{5}]$ then there does not exist a $d \in \mathbb{Z}[\sqrt{5}]$ such that $(6)$ + $(2+2\sqrt{5}) = (d)$ and therefore there is no gcd.

However this uses the lemma that if gdc(x,y) = d then $(x) + (y) = (d)$, is this true?

-

One easy way to deduce that gcds do not exist is due to failure of Euclid's Lemma. Let's recall it.

Lemma $\rm\ \ (a,b)\ =\ (ac,bc)/c\quad$ if $\rm\ (ac,bc)\$ exists.

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

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 Lemma. $\ \$ QED

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 $\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{-5}\ \in\ \mathbb Z[\sqrt{-5}]\$ we have atom $\rm\: 2\ |\ \omega'\:\! \omega = 6\:,\:$ but $\rm\ 2\nmid \omega',\:\!\omega,\:$ so $\rm\:2\:$ is not prime. Therefore we deduce that the gcd $\rm\: (2\:\!\omega,\:\! \omega'\omega)\ =\ (2+2\sqrt{-5},\:6)\$ fails to exist in $\rm\ \mathbb Z[\sqrt{-5}]\:$.

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.

-

It is not true in general that if $gcd(x,y)=d$ then $(x)+(y)=(d)$. In particular, if $R=\mathbb{Z}[x]$ (the ring of polynomials over $\mathbb{Z}$ in the indeterminate $x$), then $gcd(2,x)=1$ (since any divisor of 2 in $R$ must be an integer, and the only integers that divide $x$ in $R$ are $\pm 1$), however $(2,x)=(2)+(x)\subsetneq R$.

More generally, integral domains for which gcds can be written as a linear combination are known as Bézout domains--domains where every finitely generated ideal is principal.

As Bill mentions in his answer, GCD domains (ie integral domains in which every pair of nonzero elements has a gcd) satisfy the property that every irreducible is prime. In particular, if $R$ is an integral domain in which every nonzero nonunit can factor into irreducibles, then $R$ is a GCD domain if and only if $R$ is a UFD.

As for showing that 6 and $2+2\sqrt{-5}$ have no gcd, this can also be done easily enough using the norm function $N:\mathbb{Z}[\sqrt{-5}]\rightarrow\mathbb{N}\cup\{0\}$ defined by $N(a+b\sqrt{-5})=a^2+5b^2$. In particular for all $\alpha,\beta\in R$, $N(\alpha\beta)=N(\alpha)N(\beta)$, $N(\alpha)=0$ if and only if $\alpha=0$, and $N(\alpha)=1$ if and only if $\alpha\in U(R)$ (proving this is a canonical abstract algebra exercise). So, if there is a gcd of 6 and $2+2\sqrt{-5}$, then there must be a common divisor of 3 and $1+\sqrt{-5}$ (since 2 divides both 6 and $2+2\sqrt{-5}$ in $R$).

Thus, there exists $\alpha\in R$ such that $\alpha \vert 3$ and $\alpha \vert 1+\sqrt{-5}$. Taking the norm (and using the norm properties above), we have $N(\alpha)\vert 9$ and $N(\alpha) \vert 6$. Therefore, it follows that either $N(\alpha)=1$ or $N(\alpha)=3$. However, the fact that there are no integer solutions to the equation $a^2+5b^2=3$ (why?) implies that there is no element in $R$ having a norm of 3. Therefore $N(\alpha)=1$ and $gcd(3,1+\sqrt{-5})=1$.

Now suppose that 6 and $2+2\sqrt{-5}$ have a gcd. Then we have $2=2gcd(3,1+\sqrt{-5})=gcd(6,2+2\sqrt{-5})$. However, we reach a contradiction as $1+\sqrt{-5}$ is a common divisor of both 6 and $2+2\sqrt{-5}$, but $1+\sqrt{-5}$ does not divide 2 (Hint: suppose it does and use the norm). Therefore $gcd(6,2+2\sqrt{-5})$ does not exist.

-

Yes, as each is contained in the other. There exist integers $a,b$ such that $ax+by=d$, so $d\in(x)+(y)$, and as $x\in(d)$ and $y\in(d)$, the reverse inclusion also holds.

Edit: It seems I was mistaken in thinking you could always express $\gcd(x,y)$ as a linear combination of $x$ and $y$ (and I imagine in hindsight that the page I looked this up on said somewhere near the top that it was talking about integers). The above proof works in Bézout domains as pointed out by Jack. (For this reason I'll keep the answer here for now, even though the question is about the non-Bézout domain $\mathbb{Z}[\sqrt{5}]$ - if people think it should go then please comment to that effect).

-
Ah ok, thank you. Proving $(6)$ + $(2+2\sqrt{5})$ is not principle in $\mathbb{Z}[\sqrt{5}]$ is more difficult that I thought; any hints? – user26069 May 22 '12 at 14:57