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.

• The worst case is $q_m=1$ for all $m$. Even then the claim is true, by "Fibonacci". – Dietrich Burde Jun 22 '16 at 11:11
• why can't $q_m$ be 0? – TheMathNoob Jun 22 '16 at 11:13
• 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)$. – Dietrich Burde Jun 22 '16 at 11:15
• yes, I think it would also imply $r_{m-2}<r_m$ – TheMathNoob Jun 22 '16 at 11:21
• 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$. – 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.