This is the problem that I'm having trouble on:

Let $a$ and $b$ be natural numbers with $1000000>a>b$. What bound does Theorem 4.2.3 give for the number of steps the Euclidean Algorithm will take when performed on $a$ and $b$?

Theorem 4.2.3 states "for any pair of natural numbers $a$ and $b$, the Euclidean Algorithm takes at most $\log_2(ab)$ steps to find $\gcd (a,b)$.

Would it be $\log_2(10^6\cdot10^6)=\log_2(12)$?

  • 1
    $\begingroup$ The left side is right, the right side is not right. The bound is $\log_2(10^{12})$, which is $12\log_2(10)$. $\endgroup$ Commented Oct 5, 2015 at 21:29
  • $\begingroup$ So mine would be about 39 steps or should I round to 40 since the number is 39.84? $\endgroup$
    – ematth7
    Commented Oct 5, 2015 at 21:35
  • $\begingroup$ Since $a$ and $b$ are less than $ 1$ million, the upper bound $ B$ will be less than $12 \log_2 10. $ Since $\log_{10}2=0.30103...$ we have $B<36$ so $B$ is at most $35$. $\endgroup$ Commented Oct 5, 2015 at 21:40
  • $\begingroup$ At most $39.84$, since the number of steps is an integer, means at most $39$. $\endgroup$ Commented Oct 5, 2015 at 21:41
  • $\begingroup$ @user254665 Why are you using log base 10 if the theorem says log base 2? $\endgroup$
    – ematth7
    Commented Oct 5, 2015 at 21:54

1 Answer 1


Technically the answer is $log_2((10^6-1)(10^6-2))$ (due to the strict inequalities) but you get the same result. Calculating it out should give you

$$39 < log_2((10^6-1)(10^6-2)) <40.$$

The largest integer value would then be 39.

  • $\begingroup$ When I calculated $log_2((10^6-1)(10^6-2))$ I got ~ 3.32 and not 39. $\endgroup$
    – ematth7
    Commented Oct 6, 2015 at 23:41
  • $\begingroup$ $8<2^{3.32}< 16<<(10^6-1)(10^6-2)$. If you are trying to convert to base $10$ make sure you use $log_{2}(x)=\frac{log_{10}(x)}{log_{10}(2)}$ $\endgroup$
    – Luke
    Commented Oct 7, 2015 at 0:03
  • $\begingroup$ @ematth7, I believe you multiplied by $log_{10}(2)$ when you should have divided. That would give you the answer you got. $\endgroup$
    – Luke
    Commented Oct 7, 2015 at 4:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .