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