Breath Math

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₁ + bm₁

y = al₂ + bm₂, where l₁, m₁, l₂, m₂ ϵ Z

x – y = al₁ + bm₁ – (al₂ + bm₂) ϵ az + bz, where l₁ – l₂ ϵZ and m₁ – m₂ ϵ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₁, for some k₁ ϵ Z

⇒ d|a

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

⇒ bϵ dz

b = dz₂, for some k₂ ϵ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)