Reducing the problem with remainders
Divide a by b to write a as qb plus remainder r, with r smaller than b. If r is zero, b is the result. Otherwise continue with b and r.
For example, 1071 divided by 462 leaves 147; 462 divided by 147 leaves 21; dividing 147 by 21 leaves zero. The answer is 21. Division with remainder groups together repeated subtractions of the same smaller number.
Why common divisors are preserved
A divisor of both a and b also divides a minus qb, hence r. Conversely, a divisor of b and r divides qb plus r, hence a. The pairs therefore have exactly the same common divisors and the same greatest one.
Each unfinished step replaces a positive divisor by a smaller positive remainder. Such a descending sequence of ordinary positive integers cannot continue indefinitely. Preserving the result and proving termination are separate parts of the argument.
Historical formulation and implementation
VII.2 seeks the greatest common measure of numbers that are not relatively prime, complementing the preceding treatment of a unit remainder. Ancient distinctions between unit and number mean its wording is not a complete modern software interface for every input.
A modern implementation can iterate or recurse and must define input and zero-handling rules. Division on large integers has its own cost; a count of algorithmic stages is not unconditionally the same as elapsed arithmetic work.