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

## 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##

#### Attachments

• 14.5 KB Views: 489

Related Calculus and Beyond Homework Help News on Phys.org
andrewkirk
Homework Helper
Gold Member
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##..

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##

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
Staff Emeritus
Homework Helper
Gold Member
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 < 10k .

Last edited:
Terrell
andrewkirk
Homework Helper
Gold Member
Can you give me hints?
The hint is the last paragraph of post #2.

SammyS
Staff Emeritus
Homework Helper
Gold Member
Can you give me hints?
Another hint:

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

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

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
Staff Emeritus
Homework Helper
Gold Member
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 < 10k .

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!