Results 1 to 14 of 14

Math Help - uniquness proof

  1. #1
    Newbie
    Joined
    Jul 2009
    Posts
    7

    uniquness proof

    Hello everyone, im having a little trouble on this problem...

    "Show that greatest common divisor of two integers, which are not both
    zero, is unique."

    i came across this website: Greatest Common Divisors

    any help would be aprreciated

    thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Quote Originally Posted by matt23721 View Post
    Hello everyone, im having a little trouble on this problem...

    "Show that greatest common divisor of two integers, which are not both
    zero, is unique."
    That's a weird question: a "greatest" element of anything is always unique. It should seem obvious to you when you think of the set of the common divisors: this is a finite set of integers, it must have a greatest element, and I can't see how one may wonder if it is unique. Here's a proof anyway.
    Suppose a is a greatest element of a nonempty set A (here, A is the set of common divisors of two non-zero integers, it is nonempty since it contains 1). Then if b is another greatest element, we would have both a\geq b (because a is larger than any element of A) and b\geq a (because b is larger than any element of A), hence a=b.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jun 2009
    Posts
    220
    Thanks
    1
    The gcd of two integers, x and y, is an integer g satisfying


    1. g>0
    2. g | x and g | y
    3. If z | x and z | y then z | g

    While I'm not disagreeing with Laurent's proof, the property of 'greatest' can only be inferred from these.

    As a more specific proof of the uniqueness of such an integer, let g and \tilde{g} both satisfy properites 1, 2 and 3 above.

    Then property 3 \Rightarrow ~ g|\tilde{g} , \tilde{g}|g ~ \Rightarrow  ~ g = \pm \tilde{g}

    Property 1 \Rightarrow ~ g,\tilde{g} > 0 ~ \Rightarrow ~ g = \tilde{g}
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Apr 2009
    From
    México
    Posts
    721
    Quote Originally Posted by Laurent View Post
    a "greatest" element of anything is always unique.
    Not true. In a ring (for example a unique factorization domain) in which you define a gcd (by the two last propierties pomp gave and that it be nonzero or a unit) this element is not unique since if we multiply it by a unit the new element is also a gcd, and there may not be an order that let's you decide which is 'the one'.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jul 2009
    Posts
    7
    thanks... starting to make some sense... how would i formulate that into a proof though? I sort of understand it in words... just writing it out in "math language" is a whole other story
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Jun 2009
    Posts
    220
    Thanks
    1
    Sorry if they didn't help, but both mine and Laurent's proofs were 'mathematical'. Was there something more you were looking for?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Jul 2009
    Posts
    7
    sorry i did not meant to sound rude! what i guess i meant to say is how to a go about showing its uniqueness
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Jun 2009
    Posts
    220
    Thanks
    1
    Quote Originally Posted by matt23721 View Post
    sorry i did not meant to sound rude! what i guess i meant to say is how to a go about showing its uniqueness
    No worries.
    Usualy in mathematics, if you're asked to prove something is unique, you assume it isn't. Then, you show that assuming this, you arrive at a contradiction.
    This is what I did in my post when I assumed that g and \tilde{g} were both gcd's.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Jul 2009
    Posts
    7
    oh ok .. i follow you... instead of using g and g- could i use say one is g and the other "g" is say f??
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    Jun 2009
    Posts
    220
    Thanks
    1
    Quote Originally Posted by matt23721 View Post
    oh ok .. i follow you... instead of using g and g- could i use say one is g and the other "g" is say f??
    Yeh. You can call it shilrley if you want
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie
    Joined
    Jul 2009
    Posts
    7
    haha thanks mate.. i appreciate it tons.. message me ur aim sn or facebook name if ud like, i might have a few questions later if u wouldnt mind helpn
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Newbie
    Joined
    Jul 2009
    Posts
    7
    hey pomp... real quick, whatd u mean by z where did that come from?
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Member
    Joined
    Jun 2009
    Posts
    220
    Thanks
    1
    Quote Originally Posted by matt23721 View Post
    hey pomp... real quick, whatd u mean by z where did that come from?
    z is just any old integer. So property 3 is just saying that if there is any old integer z, such that z divides both x and y, the z must also divide the gcd of x and y.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Newbie
    Joined
    Jul 2009
    Posts
    7
    thanks man! i understand.... i sent u a message on fb
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: October 19th 2010, 10:50 AM
  2. Uniquness of integer values between a rational
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: September 30th 2010, 12:58 AM
  3. [SOLVED] direct proof and proof by contradiction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 27th 2010, 10:07 PM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 01:20 PM
  5. proof that the proof that .999_ = 1 is not a proof (version)
    Posted in the Advanced Applied Math Forum
    Replies: 4
    Last Post: April 14th 2008, 04:07 PM

Search Tags


/mathhelpforum @mathhelpforum