= Solution
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\geq0$. 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, \b[zero reduces to $0/1$].
Back to article page
