# Show that the Euclidean Algorithm terminates in less than seven times the number of digits in $b$.

Let $b=r_o, 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} \lt\frac12 r_i$$ for every $i=0,1,2,\dots$.

Conclude that the Euclidean algorithm terminates in at most $2\log_2 b$ steps, 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$ ?]

Several times I have seen that logarithm is used to find something relating to number of digits of a number, but really can't find out the insight behind this.

So, can you people please help me acquiring that knowledge please explain it to me, or at least provide a link to some article clearly described for beginners.

And here I really can't figure out why the cap is seven times the number of digits in $b$, how can I relate this to the result about $\lt \log_2a+\log_2b$, I just know simple facts about logarithm, really can't make out where it has any reference to the number of digits.

Please help me. Just because I have no idea, this question does not alleviate my confusion a little bit.

And also, what's the significance of $\log_2$? Why not considering other bases?

• I found this question in "A Friendly Introduction to Number Theory", by Silverman. – Illusion Oct 6 '16 at 19:40

Claim. For $n$ a positive integer, let $d$ be the number of digits of $n$ in base $B$. Then $d-1 \le \color{blue}{\log_B(n) < d}$.
For example, in base $B=10$, any $4$-digit number $n$ satisfies $1000 \le n < 10000$, so $3 = \log_{10}(1000) \le \log_{10} n < \log_{10}(10000) = 4$.
Proof. If $n$ has $d$ digits in base $B$, then (since the $d$th place has value $B^{d-1}$) we must have $B^{d-1} \le n < B^d$. Taking logarithms, and noting that $\log_B$ is an increasing function, we get $d-1 \le \log_B(n) < d$. $\Rule{1ex}{1ex}{0pt}$
So if you have proved that the Euclidean algorithm terminates in at most $2 \log_2(b)$ steps, then we also have the fact that $\color{blue}{\log_{10}(b) < d}$, where $d$ is the number of (base-$10$) digits of $b$. So, the number of steps is at most $2 \log_2(b) = 2 \log_2(10) \log_{10}(b) < 2 \log_2(10) d \approx 6.64d$.