# Homework Help: The GCD forms a subgroup of the integers

1. Jun 13, 2012

### jmjlt88

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. Jun 13, 2012

### vela

Staff Emeritus
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.

3. Jun 13, 2012

### jmjlt88

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!

4. Jun 13, 2012

### vela

Staff Emeritus
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.