Greatest Common Divisor
The largest integer dividing two numbers, found in a handful of steps by Euclid's algorithm of repeated remainders.
Contents
Greatest Common Divisor
The greatest common divisor of two integers a and b, written \gcd(a,b), is the largest number that divides both. For 48 and 36 it is 12; for 17 and 5 it is 1 (they share no factor but the trivial one, and are called coprime). The gcd is the meeting point of two numbers' factor structure — and there is a beautiful, ancient algorithm to find it without ever factoring either number.
The Euclidean algorithm
Euclid's insight is that the gcd doesn't change if you replace the larger number by its remainder against the smaller:
Repeat until the remainder hits 0; the last nonzero value is the gcd. For \gcd(48, 36):
It is breathtakingly fast — the number of steps is at worst proportional to the number of digits, never the size of the numbers themselves.
The geometry: tiling a rectangle with squares
There is a picture hiding in the algorithm. Lay out an a \times b rectangle and repeatedly cut off the largest square that fits. Each cut removes a b \times b square and leaves a smaller rectangle — exactly the step a \to a \bmod b. When the leftover is a perfect square, its side is \gcd(a,b): the largest square that tiles the whole rectangle evenly.
The number of squares of each size corresponds exactly to the quotients in Euclid's divisions — the rectangle is the algorithm drawn out in tile.
Bézout and the extended algorithm
Run Euclid backwards and something extra falls out: the gcd can always be written as an integer combination of the originals.
Bézout's identity is also the gateway to the Diophantine Equation: the equation ax + by = c has integer solutions if and only if \gcd(a,b) divides c. The gcd is the finest "grid spacing" the combination ax+by can land on.