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$ Jun 22, 2016 at 11:11
  • $\begingroup$ why can't $q_m$ be 0? $\endgroup$ Jun 22, 2016 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$ Jun 22, 2016 at 11:15
  • $\begingroup$ yes, I think it would also imply $r_{m-2}<r_m$ $\endgroup$ Jun 22, 2016 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$ Jun 22, 2016 at 11:23

1 Answer 1


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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .