# Euclid's 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$$, 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

## 1 Answer

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$.

• Which step would I focus on though? – Steven Feb 25 '13 at 22:27
• 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
• I am still confused on what to do, what do you mean prove a single step? I am very lost with this explanation. – Steven Feb 25 '13 at 23:33
• The small calculation at the end of the answer is I hope clear. – André Nicolas Feb 25 '13 at 23:39