Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Discrete mathematics, continuous mathematics, and probability / 3 / d

Consider one iteration with $a_i>b_i>0$ and $r_i=a_i\mathrm{mod}{b}_i$. If $b_i\le a_i/2$, then $r_i<b_i\le a_i/2$. If $b_i>a_i/2$, the quotient is $1$, so $r_i=a_i-b_i<a_i/2$. In either case $r_i<a_i/2$, whenceRepeated application, or mathematical induction, provesThis also holds for the final iteration, whose left side is zero. For zero iterations the correct relation is equality $a_0{b}_0=ab$, rather than a strict inequality.

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.

The second coordinate after two iterations satisfieswhenever 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\ge 1$,For $m=0$ the original $b$ is already $1$. A second coordinate of $1$ requires just one more division. ConsequentlyThis 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).