Euclidean Algorithm

Question

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)$. — André Nicolas, Oct 05 '15 at 21:29
So mine would be about 39 steps or should I round to 40 since the number is 39.84? — ematth7, Oct 05 '15 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$. — DanielWainfleet, Oct 05 '15 at 21:40
At most $39.84$, since the number of steps is an integer, means at most $39$. — André Nicolas, Oct 05 '15 at 21:41
@user254665 Why are you using log base 10 if the theorem says log base 2? — ematth7, Oct 05 '15 at 21:54
$12 \log_2 10=12/ \log_{10}2=12/0.30103...$ I know $\log_{10}2$ from memory. — DanielWainfleet, Oct 05 '15 at 22:19
$35< \log_2(10^6-1)(10^6-2)<12\log_2 10<36$. I dk whether 35 is the least upper bound for a, b less than 1 million . — DanielWainfleet, Oct 10 '15 at 01:21

score 0 · Accepted Answer · answered Oct 05 '15 at 23:08

0

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.

answered Oct 05 '15 at 23:08

Luke

395

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

Euclidean Algorithm

1 Answers1