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

The greatest common divisor is the largest positive integer dividing both inputs:This maximum exists because $1$ belongs to the set and all its elements are at most $b$.

Write $a=qb+r$ using the Euclidean division. If $d\mid a$ and $d\mid b$, then $d\mid (a-qb)=r$. Conversely, if $d\mid b$ and $d\mid r$, then $d\mid (qb+r)=a$. Therefore $(a,b)$ and $(b,r)$ have exactly the same positive common divisors, provingFor $r=0$, this agrees with $\gcd (b,0)=b$.

Set $(a_0,b_0)=(a,b)$. At each iteration with $b_i>0$, compute the remainder $r_i=a_i\mathrm{mod}{b}_i$, then setStop at the first index $n$ with $b_n=0$ and return $a_n$. The positive second coordinates strictly decrease, so algorithm termination follows from the well-ordering principle. The equality of greatest common divisors established in (ii) is a loop invariant, and at termination it gives