 Solution

Count the final division producing zero as an iteration, and let the total be $n$. The terminal product $a_n{b}_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\ge 2$, the penultimate product satisfiesAs $n$ is an integer, this impliesFor $n=1$, the same bound holds since $a>b\ge 1$ implies $ab\ge 2$. 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.