2
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$ – saulspatz Mar 29 '18 at 22:40
  • $\begingroup$ @saulspatz Please vet and help with the new question as shown in the edit to the OP. $\endgroup$ – jiten Mar 29 '18 at 22:52
  • 1
    $\begingroup$ possible duplicate of math.stackexchange.com/q/1852297/206402 - my answer shows that 2 steps halve the size of the larger number. $\endgroup$ – Joffan Mar 29 '18 at 23:07
  • $\begingroup$ @Joffan Please read my comment to your answer. I am confused over whether you achieve the reduction in one step or two. $\endgroup$ – jiten Mar 29 '18 at 23:31
1
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ 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. $\endgroup$ – jiten Mar 29 '18 at 23:05
  • 1
    $\begingroup$ 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}.$ $\endgroup$ – saulspatz Mar 29 '18 at 23:06
  • $\begingroup$ I don't understand your comment. What statement is that? $\endgroup$ – saulspatz Mar 29 '18 at 23:08
  • 1
    $\begingroup$ The question asks whether $r_{i+2}<r_i/2$, which actually happens in this example. $\endgroup$ – egreg Mar 29 '18 at 23:13
  • 1
    $\begingroup$ @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. $\endgroup$ – saulspatz Mar 29 '18 at 23:15
2
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ I knew there had to be a simple explanation for this. I feel so stupid. $\endgroup$ – saulspatz Mar 29 '18 at 23:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.