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)