Euclidean Algorithm terminates in at most 7x the digits of b

[Terrell]

Homework Statement

please see the image

Homework Equations

I'm not sure if this is relevant:
$r_2 \leq \frac{1}{2}r_1$ ... $r_n \leq (\frac{1}{2})^nr_1$

The Attempt at a Solution

i have shown that $r_{i+2} < r_i$ by showing the $r_{i+2} - r_i$ is negative, but how do I show that the number of steps is at most $2 \log_{2}b$

 

[andrewkirk]

i have shown that $r_{i+2} < r_i$

That is not what the question requires though. It requires to show that $r_{i+2} < \frac12 r_i$. Have you shown that?

how do I show that the number of steps is at most $2 \log_{2}b$

Once you have shown $r_{i+2} < \frac12 r_i$ you can work out how many steps it takes to reduce the remainder to 1 or less, as the algorithm terminates when the remainder reaches 1 or 0. Use the fact that the remainder halves every two steps and that initially it is no greater than $b$..

 

[Terrell]

That is not what the question requires though. It requires to show that $r_{i+2} < \frac12 r_i$. Have you shown that?
Once you have shown $r_{i+2} < \frac12 r_i$ you can work out how many steps it takes to reduce the remainder to 1 or less, as the algorithm terminates when the remainder reaches 1 or 0. Use the fact that the remainder halves every two steps and that initially it is no greater than $b$..

Sorry I meant $2r_{i+2} < r_i$

 

[Terrell]

Use the fact that the remainder halves every two steps and that initially it is no greater than bbb..

I am not sure if I am doing this completely right or wrong.

proof of $r_{i+2} < \frac{1}{2}r_i:$

Let $a - bq_1 = r_1$ s.t. $b=r_0$

$(case 1):$
If $b=r_0< \frac{1}{2}a$ then $q_1 \geq 2$ so that $r_1 < r_0$.
Furthermore, in $r_0 - r_1q_2 = r_2$, since $r_1 \leq \frac{1}{2}r_0$ then it must be that $q_2 \geq 2$ so that $r_2 < r_1$.
Therefore, $r_2 < r_1 < \frac{1}{2}r_0$ or $r_{i+2}<r_{i+1}< \frac{1}{2}r_i$ or simply $r_{i+2}<\frac{1}{2}r_i$.

$(case 2):$
If $b=r_0> \frac{1}{2}a$ then $a- r_0q_1 = r_1$ such that $r_1 < \frac{1}{2}a$ and $r_1 < r_0$ and $q_1=1$

$(subcase 2.1):$ If $r_1 > \frac{1}{2}r_0$ then definitely, $r_2 < \frac{1}{2}r_0$ or $r_{i+2}<\frac{1}{2}r_i$

$(subcase 2.2)$ If $r_1 < \frac{1}{2}r_0$ then $q_2 \geq 2$ so that $r_2 < r_1$.
Therefore, $r_2<r_1< \frac{1}{2}r_0$ or $r_{i+2}<r_{i+1}< \frac{1}{2}r_i$

From here, I am struggling to apply logarithms to show the final step. Can you give me hints?

 

[SammyS]

You may get more response if you show the image rather than just giving the link. I'll do that much for you.

The image for the link you posted:

Notice that if $\ b\ ,\$ which is also $\ r_0\ ,\$ has k decimal digits, then b < 10^k .

 

[andrewkirk]

Can you give me hints?

The hint is the last paragraph of post #2.

 

[SammyS]

Can you give me hints?

Another hint:

What upper bound on r_n will ensure that the algorithm terminates in at most n steps.

 

[Terrell]

I figured that the inequality $b(\frac{1}{2})^\frac{n}{2} < 1$ then taking the log of both sides should be enough...?

 

[Terrell]

What upper bound on rn will ensure that the algorithm terminates in at most n steps.

$r_n \leq 1$

Notice that if b , b , \ b\ ,\ which is also r0 , r0 , \ r_0\ ,\ has k decimal digits, then b < 10k .

yes i do notice, but can this be helpful to particularly show that it takes less than 7 times the no. of digits of b?

 

[SammyS]

I figured that the inequality $b(\frac{1}{2})^\frac{n}{2} < 1$ then taking the log of both sides should be enough...?

It's probably enough for $\displaystyle b(\frac{1}{2})^\frac{n}{2} < 2\ .\$ Right.

Combine this with b < 10^k .

So if $\displaystyle 10^k (\frac{1}{2})^\frac{n}{2} < 2\ ,\$ then ...

 

[Terrell]

Combine this with b < 10k

$2\log_2(b)<n$ then by letting $b = 10^k$ we get $2k\log_2(10)<n$. Also $2\log_2(b)=6.6438...$ therefore it can be at most 7 times the number of digits of $b$. Thank you Sammy!