Problem
COM-B2-M05-P017 Euclid's Algorithm as a Process
Two positive integers \(a\) and \(b\) are given. In one move, the larger number is replaced by the difference of the larger and the smaller. Prove that the process must reach the pair \(d,d\), where \(d=\gcd(a,b)\).
The gcd is preserved, and the sum of the numbers decreases until the numbers become equal.
The gcd of the pair does not change when \((a,b)\) is replaced by \((a-b,b)\) or \((a,b-a)\), because common divisors are preserved in both directions.
If the numbers are not equal, one move decreases the sum \(a+b\): the larger number is replaced by a positive smaller number. The sum is a positive integer, so the process cannot continue forever.
When no move remains, the numbers are equal; let the pair be \(c,c\). The gcd has been preserved throughout, so \(c=\gcd(c,c)=\gcd(a,b)=d\). Thus the final pair is \(d,d\).
A mixed problem: the invariant identifies the final state, while the monovariant proves termination.