If d divides both a and b, then d also divides a - b. Any common divisor of a and b is also a common divisor of b and (a mod b).
Since a mod b is just a minus some multiple of b, the two pairs (a, b) and (b, a mod b) have the exact same set of common divisors.
Therefore their GCD is the same. We keep shrinking the numbers until one becomes 0, at which point the other is the GCD.