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

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 = al1 + bm1

y = al2 + bm2, where l1, m1, l2, m2 ϵ Z

x – y = al1 + bm1 – (al2 + bm2) ϵ az + bz, where l1 – l2 ϵZ and m1 – m2 ϵ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 = dk1, for some k1 ϵ Z

⇒ d|a

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

⇒ bϵ dz

b = dz2, for some k2 ϵ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)