Prove that in a Euclidean ring with degree function d

gcd(a, b)

can be found as follows:

b= q(o)*a + r(1),where d(r(1)) < d(a)

a= q(1)*r(1) + r(2), where d(r(2)) < d (r(1))

r(1)= q(2)*r(2) + r(3), where d(r(3)) < d(r(2))

.

.

.

r(n-1) =q(n)*r(n)

and

r(n)=gcd(a, b).