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

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,...$

• In each step after the first, the divisor is the remainder from the previous step. The remainder in this step is less than the divisor by definition. Commented Mar 29, 2018 at 22:40
• @saulspatz Please vet and help with the new question as shown in the edit to the OP. Commented Mar 29, 2018 at 22:52
• possible duplicate of math.stackexchange.com/q/1852297/206402 - my answer shows that 2 steps halve the size of the larger number. Commented Mar 29, 2018 at 23:07
• @Joffan Please read my comment to your answer. I am confused over whether you achieve the reduction in one step or two. Commented Mar 29, 2018 at 23:31

## 2 Answers

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.

• I knew there had to be a simple explanation for this. I feel so stupid. Commented Mar 29, 2018 at 23:51

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.

• I hope you mean that I can give the statement in the edited OP for the worst case of Euclidean algorithm given by the Fibonacci numbers. Commented Mar 29, 2018 at 23:05
• You accepted it too soon. I misread your post. This example actually satisfies $r_{i+2}<r_{i}.$ I had misread your post as $r_{i+1}<r_{i}.$ Commented Mar 29, 2018 at 23:06
• I don't understand your comment. What statement is that? Commented Mar 29, 2018 at 23:08
• The question asks whether $r_{i+2}<r_i/2$, which actually happens in this example. Commented Mar 29, 2018 at 23:13
• @egreg Yes, I know. See my earlier comment. I'm trying to see if I can figure out the answer, before either editing or deleting this answer. Commented Mar 29, 2018 at 23:15