Proof about euclidean algorithm

Question

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.

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.