Prove that in Euclidean algorithm the remainders are decreasing at each successive step

Question

Let $r_1, r_2, ...$ be the successive remainders in the Euclidean algorithm applied to $a$ and $b$. It is obvious that the values of $a,b$ at each step are decreasing, in particular in two steps, the remainder transforms into $a$, and in one step into $b$, as shown below for the case of $r_3$:

$$a= bq_1+r_1$$ $$b=r_1q_2+r_2$$ $$r_1=r_2q_3+r_3$$ $$r_2=r_3q_4+r_4$$ $$r_3=r_4q_5+r_5$$

$$\vdots$$

This can be only used to show that after every two steps, the remainder is reduced by some ratio, I hope; but how to use to prove the title is not clear.

---

1st edit:
As per the comment by @saulspatz, it means that as the remainder will be determined by the divisor, and in any successive step the previous step's remainder is the divisor. The remainder at any $i$-th step will lie with in the bounds of $0$ to $r_i-1$. So, the remainder at the successive step will be on an average equal to half of the new divisor (or the old remainder).

Can I further use it to prove that: (A) in every two steps, the remainder is reduced by at least half, i.e. $r_{i+2} \lt \frac{1}{2}r_i$, for $i=1,2,...$

Answer 1

If you take $a=13, b=8$ then you get $$ \begin{align} r_1&=5\\ r_2&=3\\ r_3&=2\\ r_4&=1 \end{align}$$ Note that we started with two successive Fibonacci numbers, and that the remainders are successive Fibonacci numbers.

The Fibonacci numbers give the worst behavior for the Euclidean algorithm. The successive Fibonacci numbers are in the ratio $\frac{1+\sqrt 5}{2}$ approximately, so $\frac{r_i=2}{r_i}\approx.382$

I do not know whether there is some example where $\frac{r_i=2}{r_i}\ge .5$ though I tend to doubt it.

Answer 2

If $r_{i+1}$ is not itself $\le \frac12r_i$, then $r_{i+2}$ will be exactly $r_i-r_{i+1}$, which will be less than $\frac12r_i$, so your conjecture is indeed correct.

But that does not represent the worst case, because in order for $r_{i+2}$ to be close to $\frac12r_i$, it will also have to be close to $r_{i+1}$, and then $r_{i+3}$ will be dramatically small.

The Fibonacci ratio represents the worst case that can be sustained over many steps of the algorithm -- deviating from it will sooner or later lead to a smaller $r_i$ than if you had started out with the exact golden ratio.