In Euclid's algorithm, why does replacing (a, b) with (b, a mod b) leave the gcd unchanged?

## What the algorithm actually does The greatest common divisor of two non-negative integers, not both zero, is the largest integer dividing both of them. Euclid's algorithm computes it by repeatedly replacing the pair `(a, b)` with `(b, a mod b)` until the second element is 0: ``` while b != 0: r = a mod b a = b b = r return a ``` On a thumbnail service reducing an image size of 1920 by 1080 to its ratio, the pairs run `(1920, 1080) -> (1080, 840) -> (840, 240) -> (240, 120) -> (120, 0)`, so the gcd is 120, and dividing both dimensions by it gives 16 and 9. ## The invariant, proved both directions The whole correctness argument is one sentence about **divisor sets**, not about the numbers themselves. Division with remainder gives `a = q*b + r` with `0 <= r < b`. - Suppose `d` divides `a` and `d` divides `b`. Then `d` divides `a - q*b`, which is exactly `r`. So `d` is a common divisor of `(b, r)`. - Suppose `d` divides `b` and `d` divides `r`. Then `d` divides `q*b + r`, which is exactly `a`. So `d` is a common divisor of `(a, b)`. The implication runs both ways, so the two pairs have the *same set* of common divisors — not merely overlapping sets, not merely the same maximum by coincidence. Identical sets have identical maxima, which is why the step is safe to repeat forever. This is the point candidates most often fumble: they assert the gcd is preserved because "the remainder still contains the common factors", which is only half the argument. An interviewer who pushes back with "prove nothing was lost" is asking for the second direction. ## Why the loop ends, and what it ends holding Each new second element is a remainder, so it is strictly smaller than the previous second element and never negative. A strictly decreasing sequence of non-negative integers cannot run forever, so `b` reaches 0 in a finite number of steps. The base case is the identity `gcd(a, 0) = a`: every integer divides 0, so the common divisors of `a` and 0 are just the divisors of `a`, the largest of which is `a` itself. That identity is also what makes 0 the natural starting accumulator when you fold gcd across many numbers. A related detail worth knowing: the loop needs no explicit sorting step. If you call it with the smaller number first, the very first iteration computes `a mod b = a`, and the assignment swaps the pair — one wasted iteration and then it proceeds normally. ## Reduction to lowest terms and coprimality Dividing both inputs by their gcd is exactly the operation that reduces a ratio to lowest terms, and the result is always **coprime**: `gcd(a/g, b/g) = 1` where `g = gcd(a, b)`. If it were not 1, some `k > 1` would divide both quotients, and then `k*g` would be a common divisor of `a` and `b` bigger than `g`, contradicting `g` being greatest. Coprime does **not** mean either number is prime — 16 and 9 are coprime and neither is prime. It only means they share no prime factor. This is why one gcd call, rather than a loop peeling off common factors one at a time, is the right way to normalise a ratio: the gcd is the total common factor, so a single division finishes the job. ## Common ways this goes wrong Using a subtraction step instead of a remainder step is still correct — `gcd(a, b) = gcd(a - b, b)` for `a > b` by the same divisor-set argument — but it can take an enormous number of iterations when one number dwarfs the other. Writing the swap in the wrong order (`a = r; b = a` after clobbering `a`) either loops forever or returns nonsense, which is why the temporary `r` matters. And calling gcd on two zeros has no meaningful answer; the usual convention is to define `gcd(0, 0) = 0` and to guard against it before dividing by the result.