# Euclidean Algorithm

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)$?

• The left side is right, the right side is not right. The bound is $\log_2(10^{12})$, which is $12\log_2(10)$. Commented Oct 5, 2015 at 21:29
• So mine would be about 39 steps or should I round to 40 since the number is 39.84? Commented Oct 5, 2015 at 21:35
• 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$. Commented Oct 5, 2015 at 21:40
• At most $39.84$, since the number of steps is an integer, means at most $39$. Commented Oct 5, 2015 at 21:41
• @user254665 Why are you using log base 10 if the theorem says log base 2? Commented Oct 5, 2015 at 21:54

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.

• When I calculated $log_2((10^6-1)(10^6-2))$ I got ~ 3.32 and not 39. Commented Oct 6, 2015 at 23:41
• $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)}$
– Luke
Commented Oct 7, 2015 at 0:03
• @ematth7, I believe you multiplied by $log_{10}(2)$ when you should have divided. That would give you the answer you got.
– Luke
Commented Oct 7, 2015 at 4:18