# Existence of Greatest Common Divisors - Dummit and Foote Ch8

• October 12th 2012, 08:44 PM
Bernhard
Existence of Greatest Common Divisors - Dummit and Foote Ch8
I am reading Dummit and Foote Ch 8 - Euclidean, Prinipal Ideal and Unique Factorization Domains.

On page 274 D&F write: (see attached)

"Thus a greatest common divisor (if such exists) ... ..."

Even when two elements of a ring are prime a gcd exists ... ???

Can anyone give me examples of cases where a gcd does not exist for two elements of a ring?

Peter
• October 13th 2012, 09:55 AM
johnsomeone
Re: Existence of Greatest Common Divisors - Dummit and Foote Ch8

(Aside: I don't know if this is true or not - you can try to prove it or disprove it if you like, but, in my mental picture of this stuff, everything having a gcd, and being a UFD, are the same condition for an integral domain.)

Continuing with the example from yesterday: What about $9$ and $3(2+\sqrt{-5})$ in $\mathbb{Z}[\sqrt{-5}]$?

You should double check this - I might have err'd somewhere.

ASSUME they have a gcd in R = $\mathbb{Z}[\sqrt{-5}]$.

1st) 3 is irreducible in R.
proof:
Suppose 3 = gh for some g, h in R, neither of which is a unit. Then N(3) = 9 and N(g), N(h) both not 1.
Then 9 = N(3) = N(gh) = N(g)N(h), so must have N(g) = N(h) = 3. But there are no elements having norm 3.

2nd) 2+sqrt(-5) is not a unit. 2-sqrt(-5) is not a unit.
Proof:
N(2+sqrt(-5)) = N(2-sqrt(-5)) = 9.

3rd) 3 = r(2+sqrt(-5)) has no solution for r in R. Likewise for 2-sqrt(-5).
Proof:
3 irreducible, so either r or 2+sqrt(-5) is a unit. But 2+sqrt(-5) isn't a unit.
Therefore r is a unit.
Therefore r = 1 or r = -1, since those are the only two elements of norm 1.
But clearly neither choice of r is a solution. Thus there are no solutions.
Same for 2-sqrt(-5)

4th) Every gcd is of the form gcd = 9u or gcd = 3u for some unit u in R.
proof:
3 divides both, so 3 divides any gcd. Examine d = gcd = 3q, where q in R. Then d divides 9 so ds = 9 for some s in R.
Thus 3qs = 9, so qs = 3, so (q = 3u, s=u*) or (q=u, s=3u*) for some unit u in R.
Therefore d = 9u or d = 3u for some unit u in R.

5th) 3 is a gcd
Let d be a gcd. Then since d divides 3(2+sqrt(-5)), there exists some t in R such that td = 3(2+sqrt(-5)).
If d = 9u, then 9tu = 3(2+sqrt(-5)) for some t in R, so 3tu = (2+sqrt(-5)),
so 3(2-sqrt(-5))tu = (2+sqrt(-5))(2-sqrt(-5)) = 9, and so (2-sqrt(-5))(tu) = 3.
But have established that no such (tu) in R can ever make that hold.
Therefore d = 3u for some unit u in R.
Therefore d' = du* = 3uu* = 3 is another gcd.
Therefore 3 is a gcd.

6th) 3 cannot be a gcd:
proof:
Since (2+sqrt(-5)) divides both 9=(2+sqrt(-5))(2-sqrt(-5)) and 3(2+sqrt(-5)),
have that (2+sqrt(-5)) divides every gcd.
If 3 is a gcd, the (2+sqrt(-5)) divides 3, so there exists r in R such that (2+sqrt(-5))r = 3.
But have already established that that equation has no solutions for any r in R.
Therefore 3 cannot be a gcd.

Thus the assumption that a gcd exists has led to the conclusion that 3 both is, and is not, a gcd, with is a contradiction.
Therefore, those two elements have no gcd in R.
• October 13th 2012, 01:32 PM
Deveno
Re: Existence of Greatest Common Divisors - Dummit and Foote Ch8
the existence of an ordering on Z allows us to conclude there is a greatest common (positive) divisor of two integers. the existence of a euclidean function d in a ring R lets us profitably extend this notion to rings that lack a total order (first we order by d, and if we have 2 common divisors with greatest d value, we order by divisibility...since euclidean domains are unique factorization domains the gcd is unique "up to units").

There are rings, called GCD domains, in which gcd's exist. There is the following chain of inclusions:

Commutative Rings > Integral domains > GCD domains > UFDs > PIDs > Euclidean domains > Fields

johnsomeone's post shows that Z[√(-5)] is not a GCD domain, which in turn means it CANNOT be a UFD or a PID, let alone euclidean. In this regard, it is a sharper result than all of the previous discussion.

It is possible to say, for Z[√k], what kind of ring we have based on the integer k alone, but this problem is not as easy as it seems. The reason being, we might have several ways to define a function d that could serve as a euclidean function. If the field norm works, great, but sometimes some other norm will do. for example:

Z[√(-3)] has the euclidean function d(a + b√(-3)) = a2 + 3b2...this is the field norm
Z[√2] has the euclidean function d(a + b√2) = |a2 - 2b2|...this is NOT the field norm.

As incredulous as it may sound, the examples you are being given in Dummit & Foote are "the easy ones", establishing that Z[√6] is euclidean is not as simple as it may seem.
• October 13th 2012, 02:51 PM
Bernhard
Re: Existence of Greatest Common Divisors - Dummit and Foote Ch8
Johnsomeone, Deveno

Thank you for those helpful posts ... Now have the confidence to proceed further with D&F Ch 8!

Peter