Let a,b be an element in Z with a = b = 0, let d := gcd(a,b) and assume d 0.

Suppose that on input a,b, Eculid's algorithm performs lambda division steps, and computes the remainder sequence {r_i}^{lambda + 1}_{i=0} and the quotient sequence {q_i}^{lambda}_{i=1}.

Now suppose we run Euclid's algorithm on input a/d, b/d. Show that on these inputs, the number of division steps performed is also lambda, the remainder sequence is {r_i/d}^{lambda + 1}_{i=0} and the quotient sequence is {q_i}^{lambda}_{i=1}.

Not really sure how to approach

Question

Let a,b be an element in Z with a >= b >= 0, let d := gcd(a,b) and assume d > 0.

Suppose that on input a,b, Eculid's algorithm performs lambda division steps, and computes the remainder sequence {r_i}^{lambda + 1}_{i=0} and the quotient sequence {q_i}^{lambda}_{i=1}.

Now suppose we run Euclid's algorithm on input a/d, b/d. Show that on these inputs, the number of division steps performed is also lambda, the remainder sequence is {r_i/d}^{lambda + 1}_{i=0} and the quotient sequence is {q_i}^{lambda}_{i=1}.

Not really sure how to approach