# 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 principal in $\mathbb{Z}[\sqrt{5}]$ then there does not exist $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 $\gcd(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.

-
@user26857 Any further harassment will be reported to the SE team. You do know they can see deleted comments. Not good for you, considering your long track record of harassing users. I have them all archived. – Bill Dubuque Jul 23 at 19:39
@user26857 Please do not ping me any further on any of these matters. You've already wasted far too much of my time with your nonsense. Post your own answer if you deem it so important (and not to worry, unlike you, I'm not going to make rude accusations that your failure to do so implies that you don't know how - how childish, and rude). And archiving takes 2 keystrokes, so you're wrong on that too. – Bill Dubuque Jul 23 at 19:50
@user26857 For the last time, I have no interest in any of this, whether it be your guesses on old history, your voting strategies, your guesses about my motivations, etc. This is a site for mathematics, not soap operas. Please don't ping me any further. – Bill Dubuque Jul 23 at 20:00

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 \mid 3$ and $\alpha \mid 1+\sqrt{-5}$. Taking the norm (and using the norm properties above), we have $N(\alpha)\mid 9$ and $N(\alpha) \mid 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=2\gcd(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