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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.