MHB Number of steps of euclidean algorithm

AI Thread Summary
The discussion focuses on demonstrating that the Euclidean algorithm reduces the remainder by at least half after every two steps, leading to the conclusion that it terminates in at most 2 log₂(b) steps. The participants analyze the relationship between successive remainders and derive that if m exceeds log₂(b), then the algorithm will terminate when the remainder reaches zero. They also establish that the number of steps is approximately seven times the number of digits in b, using the approximation of log₂(10). The conversation emphasizes the mathematical reasoning behind the efficiency of the Euclidean algorithm.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
Hello! (Wave)

I am looking at the following exercise: Let $b=r_0, r_1, r_2, \dots$ be the successive remainders in the Euclidean algorithm applied to $a$ and $b$. Show that after every two steps, the remainder is reduced by at least one half. In other words, verify that $$r_{i+2}< \frac{1}{2} r_i \ ,\text{ for every } i=0,1,2, \dots$$Conclude that the Euclidean algorithm terminates in at most $2 \log_2{(b)}$ steps, where $\log_{2}$ is the logarithm to the base $2$. In particular, show that the number of steps is at most seven times the number of digits in $b$. [ Hint: What is the value of $\log_2{10}$ ?]

I have tried the following:

The general formula for $r_{i-1}$ in the Euclidean algorithm is the following:

$$r_{i-1}=q_{i+1} r_i+r_{i+1}$$So we have: $r_i=q_{i+2} r_{i+1}+r_{i+2} \\=q_{i+2}(q_{i+3} r_{i+2}+r_{i+3})+r_{i+2} \\=q_{i+2} q_{i+3} r_{i+2} +q_{i+2} r_{i+3}+r_{i+2}\\ \geq r_{i+2}+q_{i+2} r_{i+3}+r_{i+2} \\=2r_{i+2}+q_{i+2} r_{i+3}> 2r_{i+2}$

So it follows that $r_{i+2}<\frac{1}{2} r_i$.

As for the number of steps, I have thought the following:We have that $b=r_0>2r_2> 4r_4>8r_6> \dots> 2^m r_{2m}$

The Euclidean algorithm terminates when we find a remainder that is equal to zero.

So we check when $r_{2m}<1$.

$r_{2m}<1 \Rightarrow 2^m r_{2m}<2^m$.

We also have that $2^m r_{2m}<b$.

But from these two inequalities, we cannot find a relation between $m$ and $b$, can we?
 
Mathematics news on Phys.org
evinda said:
We also have that $2^m r_{2m}<b$.
Take logs to base 2 in that inequality: $m + \log_2 r_{2m} < \log_2b$.

If $m > \log_2b$ then $\log_2 r_{2m} < \log_2b - m < 0$. So $r_{2m}<1$, which means that $r_{2m} =0$, and the algorithm has terminated.

Since $m > \log_2b\ \Longrightarrow\ 2m > 2\log_2b$, this shows that as soon as the algorithm reaches the $2m$th step, with $2m > 2\log_2b$, the algorithm will terminate.
 
The fact that $r_i>2r_{i+2}$ can be shown slightly more easily. We have $r_i>r_{i+1}$ for all $i$ because $r_{i+1}$ is the remainder when something (namely, $r_{i-1}$) is divided by $r_i$. So we have
\[
r_i=q_{i+2}r_{i+1}+r_{i+2}\ge r_{i+1}+r_{i+2}>2r_{i+2}.
\]
 
Evgeny.Makarov said:
The fact that $r_i>2r_{i+2}$ can be shown slightly more easily. We have $r_i>r_{i+1}$ for all $i$ because $r_{i+1}$ is the remainder when something (namely, $r_{i-1}$) is divided by $r_i$. So we have
\[
r_i=q_{i+2}r_{i+1}+r_{i+2}\ge r_{i+1}+r_{i+2}>2r_{i+2}.
\]

Yes, I see... (Smile)
 
Opalg said:
Take logs to base 2 in that inequality: $m + \log_2 r_{2m} < \log_2b$.

If $m > \log_2b$ then $\log_2 r_{2m} < \log_2b - m < 0$. So $r_{2m}<1$, which means that $r_{2m} =0$, and the algorithm has terminated.

Since $m > \log_2b\ \Longrightarrow\ 2m > 2\log_2b$, this shows that as soon as the algorithm reaches the $2m$th step, with $2m > 2\log_2b$, the algorithm will terminate.

I understand... So the algorithm terminates in at least $2\log_2b$ steps, or not? (Thinking)

In order to show that the number of steps is at least seven times the number of digits in $b$, we use the fact that$$2\log_2b=2\log_2{10} \cdot \log_{10}{b} \approx 6.6 \log_{10}{b}$$

Right?
 
Seemingly by some mathematical coincidence, a hexagon of sides 2,2,7,7, 11, and 11 can be inscribed in a circle of radius 7. The other day I saw a math problem on line, which they said came from a Polish Olympiad, where you compute the length x of the 3rd side which is the same as the radius, so that the sides of length 2,x, and 11 are inscribed on the arc of a semi-circle. The law of cosines applied twice gives the answer for x of exactly 7, but the arithmetic is so complex that the...
Back
Top