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 with . The nonnegative loop variant is : when positive, the new remainder is strictly smaller. Thus the final 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 .
Resilience of a denominator Created 2026-10-20 Updated 2026-11-05
For an integer , the resilience of a denominator is the fraction of its proper fractions already in lowest terms. The fraction is a reduced fraction exactly when and are coprime, so
where is Euler's totient function.
For , the allowed numerators are , giving . A prime denominator has resilience one. Conversely, a composite number has a proper prime divisor , and is among the listed fractions but is not reduced; thus its resilience is strictly less than one.
The prime factorization formula gives
The correction comes from sampling the positive proper numerators, rather than all residue classes. The related coresilience uses .