= Solution
The second coordinate after two iterations satisfies
$$
b_{i+2}=b_i\bmod b_{i+1}<\frac{b_i}{2}
$$
whenever those two divisions are needed, by the same <remainder> bound, now applied to $b_i>b_{i+1}>0$. Let $m=\lfloor\log_2 b\rfloor$. If the <Euclidean algorithm> has not already stopped after $2m$ iterations, then its positive second coordinate is at most $1$: for $m\ge1$,
$$
0<b_{2m}<\frac b{2^m}<2.
$$
For $m=0$ the original $b$ is already $1$. A second coordinate of $1$ requires just one more division. Consequently
$$
\boxed{n\le2\lfloor\log_2 b\rfloor+1,\qquad n=O(\log b)\text{ as }b\to\infty.}
$$
This removes dependence on the potentially much larger input $a$. It improves the scale $\log_2(ab)$ to one involving only the smaller input; the rounded numerical bound need not be smaller for every pair. One may always take the minimum of the bounds in (ii) and (iii).
Back to article page
