A.3.3.TR:5.3 - Preserving a value and making progress require different arguments

For nonnegative integers a and b with a >= b > 0, use integer division a = k*b + r, where k and r are integers and 0 <= r < b. Take the transition (a,b) -> (b,r). Every common divisor of a and b divides r = a - k*b; every common divisor of b and r divides a = k*b + r. The integer quotient makes both implications valid. The transition therefore preserves the common divisors and hence the greatest common divisor. At b = 0, stop and return a.

From (30,18), the successive states are (18,12), (12,6), (6,0). The terminal result is 6. The second component is a nonnegative integer and decreases at every nonterminal step, establishing termination.

By comparison, repeatedly swapping the two arguments also preserves their greatest common divisor but can alternate forever. Preservation alone did not establish progress. The Euclidean rule adds the remainder operation and a decreasing quantity.

This is a transition account for a mathematical construction. An implementation must supply integer operations with the assumed meanings; using a bounded machine representation introduces its own arithmetic conditions.