3
$\begingroup$

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?

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

This is how we can relate logarithms to numbers of digits:

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

$\endgroup$

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.