Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Imperative programming / 4 / a

Use the iterative Euclidean algorithm for a nonnegative numerator and positive denominator:

function GCD(m,n): integer
    a := m
    b := n
    while b != 0 do
        r := a mod b
        a := b
        b := r
    return a

procedure Reduce(var m,n)
    require m >= 0 and n > 0
    d := GCD(m,n)
    m := m div d
    n := n div d

The loop invariant is $\gcd (a,b)=\gcd (m_0,n_0)$ with $a,b\ge 0$. The nonnegative loop variant is $b$: when positive, the new remainder is strictly smaller. Thus the final $a$ is the positive greatest common divisor. Dividing both numerator and denominator by it preserves the rational number and makes them coprime. The stated proper fraction case is included, but the same code works for every nonnegative numerator, a fact useful in part (d). In particular, zero reduces to $0/1$.