Let $a,b$ be an element in $\mathbb{Z}$ with $a \ge b \ge 0$, let $d = \gcd(a,b)$ and assume $d \gt 0$.
Suppose that on input $a,b$, Euclid'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 this problem, any help would be appreciated. Thanks
Hint: It is enough to verify the assertion for a single step of the Euclidean algorithm, The rest follows by induction on the length $\lambda$. So do one step of the Euclidean algorithm, starting with $(a,b)$. We find $q$ and $r$, with $0\le r\lt b$, such that $a=qb+r$.
Now suppose we do the same thing with $a/d$ and $b/d$, where $d$ is any common divisor of $a$ and $b$. It is clear that $a/d=q(b/d)+r/d$.