[thaumasiotes]

This comment is more to satisfy an aspect of the proof I was personally uncomfortable with.

We can easily show that (1) the iterative subtraction process always preserves divisibility by the GCD, and (2) it eventually reaches 0. (It cannot reach a negative value because we always subtract the smaller number from the larger number.)

It's slightly trickier to show that the process achieves the GCD before it hits zero. Theoretically, it could go from a multiple of the GCD to zero without passing through the GCD itself. This felt like a hole in my proof.

It is not the case, however:

In order to achieve r = 0, we must have had a = b at that step. We know that all of our pairs (a, b) and (b, r), at every step of the process, share the same GCD. Thus, the GCD of the original pair of numbers is equal to the GCD of the values a and b for which r = a-b = 0. Since GCD(m,m) = m for all m, this a and b are both equal to the GCD of the original pair -- which means that the process achieved the GCD.