# Euclids Algorithm Proof

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$, 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 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$.
If you call $a$ by the name $a_0$, and $b$ by the name $a_1$, then $a_2$ is the $r$. You can name the $q$'s that you get $q_1$, $q_2$, and so on. Call the corresponding things for $a/d,b/d$ by names $a_0',a_1',\dots$, and $q_1',q_2',\dots$. Then the step I did in my answer is the induction step that gets you from $i$ to $i+1$. But I would prefer to use less cumbersome notation. Assume result is true for any gcd calculation of length $n$. Show the result is true for any gcd calculation of length $n+1$. –  André Nicolas Feb 25 '13 at 22:51
Suppose Euclidean algorithm on $(a,b)$ has length $n+1$. Then after the step described in the answer, we are left with a gcd calculation of length $n$, induction hypothesis takes care of it. Don't forget to verify the (easy) base step, where gcd calculation takes $0$ steps because $b$ divides $a$. –  André Nicolas Feb 25 '13 at 22:54