**If a and b are integers not both zero (a≠0, b≠0) then, az + bz = dz where d = gcd(a, b)**

**Proof: **

We define az + bz = {al + bm| l,m ϵ Z}

Let x, y ϵ az + bz

Then,

x = al_{1} + bm_{1}

y = al_{2} + bm_{2}, where l_{1}, m_{1}, l_{2}, m_{2} ϵ Z

x – y = al_{1} + bm_{1} – (al_{2} + bm_{2}) ϵ az + bz, where l_{1} – l_{2} ϵZ and m_{1} – m_{2} ϵZ

But, every subgroup of Z is of the form az, where a is a non-negative integer (a≥0)

Show that, d = gcd(a, b)

We have, a = a.1 + b.0 ϵ az + bz = dz

⇒a ϵ dz

a = dk_{1}, for some k_{1} ϵ Z

⇒ d|a

Also, b = a.0 + b.1 ϵ az + bz = dz

⇒ bϵ dz

b = dz_{2}, for some k_{2} ϵZ

⇒d|b

Also, d = d.1 ϵdz = az + bz

d ϵ az + bz

d = al + bm, where l, m ϵ Z …………………(*)

Let C be any other common divisor of a and b

i.e., c|a and c|b

But then c|al and c|bm

c|(al+bm)

c|d [from equation(*)]

Therefore, d = gcd(a, b)