Numerical Methods

Euclidean Algorithm

Find the greatest common divisor by repeatedly replacing the larger number with its remainder — the oldest algorithm.

The a×b rectangle is tiled with the largest squares that fit; each leftover (dashed) is a smaller rectangle tiled the same way. The final, smallest square — green — has side equal to the gcd.

What you're seeing

The greatest common divisor of two numbers is, geometrically, the side of the largest square tile that can pave an a × b rectangle with no gaps. Euclid's method finds it by a beautiful reduction: cover as much of the rectangle as you can with squares of side equal to the shorter edge, and whatever sliver is left over is a smaller rectangle — which you tile the same way. The leftover rectangle keeps shrinking; when a square finally tiles its rectangle exactly, that square's side is the gcd. The numeric version is the same thing without the pictures: replace (a, b) with (b, a mod b) until the remainder hits zero.

The rule

gcd(a, b):
    while b ≠ 0:
        (a, b) = (b, a mod b)     # a mod b = the leftover strip
    return a                      # last non-zero value

The invariant

Why does throwing away the big part and keeping the remainder not change the answer? Because gcd(a, b) = gcd(b, a mod b) — the two pairs have exactly the same set of common divisors. Any number d that divides both a and b also divides a − qb = a mod b (a divisor of two numbers divides any integer combination of them); and conversely, any d dividing b and a mod b divides a = qb + (a mod b). So the common divisors — and hence the greatest of them — are preserved at every step. The remainder strictly shrinks each round, so the process must reach remainder 0, at which point gcd(x, 0) = x reads off the answer. The result therefore divides both originals and is the largest that does.

The cost

stepsper step Euclid (mod)O(log min(a,b))one division

Each step at least halves the larger number within two iterations (a classical lemma), so the number of steps is logarithmic — Lamé's theorem (1844) pins the worst case to consecutive Fibonacci numbers, the inputs that make every quotient 1 (try a, b = 55, 34 and watch the staircase of single squares). That makes it strikingly fast even for enormous integers. The extended Euclidean algorithm additionally returns coefficients x, y with ax + by = gcd — the workhorse behind modular inverses and therefore RSA key setup.

In the wild

The Euclidean algorithm (Euclid's Elements, Book VII, c. 300 BC) is the oldest nontrivial algorithm still in everyday use. Its extended form computes modular inverses for RSA and elliptic-curve cryptography, reduces fractions to lowest terms in every computer-algebra system and rational-arithmetic library, underlies the Chinese Remainder Theorem and continued-fraction expansions, and appears in clock/gear ratio and scheduling problems. Binary GCD (Stein's algorithm) replaces division with shifts and subtraction for hardware-friendly speed.

Try this

Set a, b to neighbouring Fibonacci numbers (try 55 and 34): the rectangle peels off one square at a time — the slowest possible case — and the gcd comes out 1. Then pick two multiples of the same number (say 48 and 36) and watch the tiling bottom out in a large green square: the gcd made visible.

References

  1. Euclid. Elements, Book VII, Propositions 1–2 (c. 300 BC) — anthyphairesis / the subtraction method.
  2. Knuth, D. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, §4.5.2–4.5.3. Addison-Wesley — analysis, Lamé's theorem, the extended and binary variants.
  3. Cormen, Leiserson, Rivest & Stein. Introduction to Algorithms, 4th ed. (CLRS), §31.2 (Greatest common divisor). MIT Press, 2022.