The GCD forms a subgroup of the integers

[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 = n₁r₁ + m₁s₁ and b = n₂r₂ + m₂s₂. Computing a + b (since we are considering Z under additon?), we get

a + b = n₁r₁ + m₁s₁ + n₂r₂ + m₂s₂.

... 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?

 

[vela]

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.

 

[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 (n₁ + n₂) + s (m₁+m₂)

Then, n₁ + n₂ and m₁+m₂ are both integers. Let n₁ + n₂= n' and m₁+m₂=m'.

Thus,

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

How this? :) Thanks for your help!

 

[vela]

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.