1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The GCD forms a subgroup of the integers

  1. Jun 13, 2012 #1
    Let r and s be positive integers. Show that {nr + ms | n,m ε Z} is a subgroup of Z

    Proof: ---- "SKETCH" -----

    Let r , s be positive integers. Consider the set {nr + ms | n,m ε Z}. We wish to show that this set is a subgroup of Z.

    Closure

    Let a , b ε {nr + ms | n,m ε Z}. Then, a = n1r1 + m1s1 and b = n2r2 + m2s2. Computing a + b (since we are considering Z under additon?), we get

    a + b = n1r1 + m1s1 + n2r2 + m2s2.

    .... All of these elements are integers and our result will again be an integer, and hence a+b will be in our set.

    Identity

    If we take n,m = 0, we will have 0 ε {nr + ms | n,m ε Z}.... Thus, the identity exists.

    Inverses
    Let a = nr + ms. Take a-1= -nr+-ms since -n,-m ε Z
    .... Hence, inverses exist our set.

    QED


    Any huge mistakes?
     
  2. jcsd
  3. Jun 13, 2012 #2

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    For closure, you need to show a+b is in the set, not that it's an integer. Also, there's only one r and one s, so there's no need for subscripts on them.
     
  4. Jun 13, 2012 #3
    Vela, so I have to show that a+b can be written as nr + ms for some integers n,m?

    The sum a+b = r (n1 + n2) + s (m1+m2)

    Then, n1 + n2 and m1+m2 are both integers. Let n1 + n2= n' and m1+m2=m'.

    Thus,

    a + b = rn' + sm' for n' , m' ε Z and our set is closed.

    How this? :) Thanks for your help!
     
  5. Jun 13, 2012 #4

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    Looks good.

    All you need to show is closure and that the set contains inverses for its elements to prove it's a subgroup. From those two, it follows that the identity is in the set, and associativity is inherited from the group.

    The other approach is to show if a and b are in the set, that a-b is in the set.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook