gcd(a, b) = gcd(b, a mod b), looped until b = 0. Watch the pair shrink, and the rectangle tile with squares whose side is the GCD.
step 0
Geometric view: tile an a × b rectangle
Lay the biggest b × b squares along the rectangle; the leftover strip is a mod b.
b×b squares this step final GCD square leftover (a mod b)
Algebraic view: gcd(a, b) = gcd(b, a mod b)
Press Step to begin. Each step replaces (a, b) with (b, a mod b); the remainder strictly decreases, so we reach b = 0 in O(log min(a, b)) steps.
Try these inputs
48, 18 — the worked example; gcd 6, lcm 144, finishes in 3 steps.
1071, 462 — the classic textbook pair; gcd 21 in 3 steps.
34, 21 — consecutive Fibonacci numbers (F9, F8): the worst case for their size, 7 steps, every quotient 1, and they turn out coprime (gcd 1).
100, 1 — one step: gcd(100, 1) = 1, the fastest case.
0, 9 — the base case: gcd(0, 9) = 9 immediately.
Self-contained visualization. The last non-zero second argument is gcd(a, b); the rectangle tiles exactly with squares of that side.
Then lcm(a, b) = a / gcd(a, b) * b (divide before multiply to avoid overflow). See junior.md and professional.md for the proof that the substitution a → a mod b preserves the set of common divisors.