The Euclidean algorithm reduces the problem size by replacing the larger number with the remainder of the division of the two numbers. Since the remainder r satisfies 0≤r<a (where a is the divisor), the new number is strictly smaller than the previous larger number, ensuring progress towards the base case.
Conditions: The current pair is (a,b) with b≥a>0.; The step computes b=aq+r with 0≤r<a.; The new pair is (r,a) or (a,r) depending on implementation, but effectively the max value decreases.