Results 1 to 4 of 4
Like Tree2Thanks
  • 1 Post By johnsomeone
  • 1 Post By Deveno

Math Help - Existence of Greatest Common Divisors - Dummit and Foote Ch8

  1. #1
    Super Member Bernhard's Avatar
    Joined
    Jan 2010
    From
    Hobart, Tasmania, Australia
    Posts
    558
    Thanks
    2

    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
    Attached Files Attached Files
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    146

    Re: Existence of Greatest Common Divisors - Dummit and Foote Ch8

    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.
    Last edited by johnsomeone; October 13th 2012 at 10:04 AM.
    Thanks from Bernhard
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,386
    Thanks
    752

    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.
    Last edited by Deveno; October 13th 2012 at 01:42 PM.
    Thanks from Bernhard
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Bernhard's Avatar
    Joined
    Jan 2010
    From
    Hobart, Tasmania, Australia
    Posts
    558
    Thanks
    2

    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Rings and Subrings - Dummit and Foote Chapter 7
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: August 31st 2012, 03:18 PM
  2. greatest common divisors
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 18th 2012, 08:19 AM
  3. Replies: 7
    Last Post: March 17th 2012, 10:53 PM
  4. Orbits - Dummit and Foote and Fraleigh
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: December 24th 2011, 01:20 PM
  5. General Linear Group - Problem from Dummit and Foote
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: October 11th 2011, 09:07 AM

Search Tags


/mathhelpforum @mathhelpforum