= Solution
Count the final division producing zero as an iteration, and let the total be $n$. The terminal product $a_nb_n=0$ alone gives no useful bound. Instead apply (i) to each nonterminal product, which is a positive <integer> and hence at least $1$.
If $n\ge2$, the penultimate product satisfies
$$
1\le a_{n-1}b_{n-1}<\frac{ab}{2^{n-1}},
\qquad n-1<\log_2(ab).
$$
As $n$ is an <integer>, this implies
$$
\boxed{n\le\lceil\log_2(ab)\rceil.}
$$
For $n=1$, the same bound holds since $a>b\ge1$ implies $ab\ge2$. In particular the <Euclidean algorithm> uses $O(\log a+\log b)$ divisions, in <big O notation>. The convention that includes the final zero-producing division explains the one-step offset in the argument.
Back to article page
