When calculating the greatest common divisor of two integers $a$ and $b$ by using the Euclidean algorithm, call the remainders obtained during the process $r_1,r_2,r_3,\ldots$. Show that each nonzero remainder $r_m$ with $m \geq 2$ is less than $r_{m-2}/2$.

Hint: Consider separately the cases in which $r_{m-1}$ is less than, equal to, or greater than $r_{m-2}/2$.

Deduce that the number of divisions in the euclidean algorithm is at most 2n+1 where n is that integer such that $2^n \leq b < 2^{n+1}$, and where b is the smaller of the two numbers whose GCD is being found

Approach "Not even close"

what I see is that the remainders we are comparing are always in the form $r_{m-2}=r_{m-1}q_{m}+r_m$.

Obviously $r_m$ is always less than $r_{m-2}$.

I am also trying different possible remainders like b-1,1 etc.

  • $\begingroup$ The worst case is $q_m=1$ for all $m$. Even then the claim is true, by "Fibonacci". $\endgroup$ – Dietrich Burde Jun 22 '16 at 11:11
  • $\begingroup$ why can't $q_m$ be 0? $\endgroup$ – TheMathNoob Jun 22 '16 at 11:13
  • $\begingroup$ If $q_m=0$, then the Euclidean algorithm has stopped. This will always happen, but only at the end. So the worst case is $(q_m)_m=(1,1,\cdots ,1,0)$. $\endgroup$ – Dietrich Burde Jun 22 '16 at 11:15
  • $\begingroup$ yes, I think it would also imply $r_{m-2}<r_m$ $\endgroup$ – TheMathNoob Jun 22 '16 at 11:21
  • $\begingroup$ It must imply the full statement $r_m<r_{m-2}/2$, because otherwise the division of $F_n$ by $F_{n-1}$ for Fibonacci numbers would be a counterexample to $r_m<r_{m-2}/2$. $\endgroup$ – Dietrich Burde Jun 22 '16 at 11:23

In any case, $q_m = \lfloor r_{m-2}/r_{m-1} \rfloor$, so you get:

Case 1: $r_{m-1} = r_{m-2}/2$

$q_m = 2$, so $r_m = r_{m-2} - r_{m-1} q_m = 0 < r_{m-2}/2$

Case 2: $r_{m-1} > r_{m-2}/2$

$1 < r_{m-2}/r_{m-1} < 2$, so $q_m = 1$. Then $r_{m} = r_{m-2} - r_{m-1} < r_{m-2} - r_{m-2}/2 = r_{m-2}/2$

Case 3: $r_{m-1} < r_{m-2}/2$

Since the remainders are decreasing, $r_m < r_{m-1} < r_{m-2}/2$.

For the last part, the size of the remainder is always half as big (or smaller) than it was two steps ago. So since $b < 2^{n+1}$, after $2n$ steps you've halved it $n$ times and you're left with a number $ < 2^{n+1}/2^n = 2$, i.e. 0 or 1. In one more step you're guaranteed to be done.


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.