Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Discrete mathematics, continuous mathematics and probability / 2 / b / Solution

For integers $a,b$ not both zero, replace them first by their absolute values, then repeat integer division:

while b != 0:
    (a,b) := (b, a mod b)
return a

This is the Euclidean algorithm. Its loop invariant is that $\gcd (a,b)$ equals the original greatest common divisor. When $b>0$, the new remainder lies in $[0,b)$, so $b$ is a strictly decreasing nonnegative loop variant. At termination, $\gcd (a,0)=a$, proving correctness, including the case where one original input is zero.