The idea: shrink the pair, keep the gcd
The greatest common divisor gcd(a, b) is the largest number that
divides both a and b. Euclid's algorithm (about 300 BC) finds it without
factoring anything. Divide a by b: a = q·b + r with
0 ≤ r < b. Then replace the pair (a, b) by (b, r) and repeat. When the
remainder is 0, the last divisor is the gcd.
Why gcd(a, b) = gcd(b, r)
Take any d that divides a and b. Then d divides r = a − q·b
too. The other way round, any d that divides b and r divides
a = q·b + r. So the two pairs have exactly the same common divisors,
and the same greatest one. The numbers get smaller at every row, so the
algorithm always ends. Demo: gcd(1071, 462) takes three rows:
| row | a = q·b + r | new pair |
|---|---|---|
| 1 | 1071 = 2·462 + 147 | (462, 147) |
| 2 | 462 = 3·147 + 21 | (147, 21) |
| 3 | 147 = 7·21 + 0 | stop: gcd = 21 |
The rectangle picture
Draw an a × b rectangle. Cut off as many b × b squares as fit along the long side: that is q. What is left is an r × b rectangle, turned on its side. Cut that one the same way. The last square size divides the rectangle exactly, so it divides both sides: it is the gcd. A square that tiles the rectangle must also tile every leftover piece, so no bigger one can work. Each row of the table has its own colour in the drawing and in its q cell.
How fast it is: the Fibonacci worst case
The pair shrinks slowest when every quotient is 1, because then r = a − b is as large as it can be. That happens for consecutive Fibonacci numbers (computed on Fibonacci with dynamic programming): 89 = 1·55 + 34, 55 = 1·34 + 21, … (Demo: Fibonacci worst case, 9 rows for two-digit numbers). Lamé's theorem says the number of divisions is at most about 5 times the number of decimal digits of the smaller number, so the cost is O(log b) divisions. Compare gcd(1071, 462), which needs only 3. When the result is 1, as for Demo: coprime pair (35, 24), the numbers are coprime: they share no factor.
Extended Euclid and Bézout's identity
Bézout's identity: there are whole numbers x and y (one of them
usually negative) with a·x + b·y = gcd(a, b). The
extended algorithm finds them by going back up the table. On the
last row, gcd = b, so x = 0 and y = 1. On each row above, write
r = a − q·b and substitute it into the row below's
gcd = x′·b + y′·r:
gcd = x′·b + y′·(a − q·b) = y′·a + (x′ − q·y′)·b
so x = y′, y = x′ − q·y′The page fills the x and y columns bottom-up: the old y flies into the new x, then y is computed, and every row keeps x·a + y·b = gcd. The top row is the answer for the input pair. Demo: extended Euclid gives 240·(−9) + 46·47 = 2.
Modular inverse
The inverse of b modulo a is the number y with b·y ≡ 1 (mod a). If gcd(a, b) = 1, Bézout gives a·x + b·y = 1, so b·y = 1 − a·x, which is 1 more than a multiple of a. So y (moved into 0…a−1) is the inverse. Demo: modular inverse 17⁻¹ mod 43: 43·2 + 17·(−5) = 1, so 17⁻¹ = −5 + 43 = 38, and 17·38 = 646 = 15·43 + 1.
If the gcd is d > 1, every b·y + a·k is a multiple of d, so it is never 1 mod a: there is no inverse (Demo: no inverse, 12 mod 18 with gcd 6). That is why RSA picks its public exponent e coprime to φ(n): the private key is d = e⁻¹ mod φ(n), computed exactly this way (signatures built on RSA are on Digital Signatures). The other half of RSA, raising to a power mod n, is on Modular Exponentiation.
The same Bézout coefficients can be computed forward, keeping r = s·a + t·b on every row; Extended Euclid, Modular Inverse and Toy RSA does that on (φ(n), e) to get an RSA private key and then encrypts with it.
| task | what Euclid gives | used for |
|---|---|---|
| gcd(a, b) | the last non-zero remainder | reducing fractions, lcm = a·b / gcd |
| Bézout x, y | back-substitution up the table | solving a·x + b·y = c (it has a solution iff gcd divides c) |
| b⁻¹ mod a | y from Bézout, when gcd = 1 | RSA keys, modular division, the Chinese remainder theorem |
See also Sieve of Eratosthenes for primes, and Number Bases, which converts numbers with the same repeated division with remainder.
Prime Factorization computes the same gcd a different way, by taking the min exponent of each prime (and the lcm from the max). The inverses Mᵢ⁻¹ mod mᵢ that solve a system of congruences are put to work on Chinese Remainder Theorem.
See also Reed-Solomon Erasure Coding, where inverses mod 11 make the division in Lagrange interpolation work to rebuild lost disks.
The gcd decides when a Spirograph pattern closes, after r/gcd(R, r) turns with R/gcd(R, r) points: see Spirograph: Hypotrochoids and Epitrochoids.
Euclid's algorithm must stop because its numbers keep getting smaller; for the 3n + 1 rule nobody can prove that, see The Collatz Conjecture.
The same division steps give a continued fraction, and the golden angle's all-ones continued fraction is why sunflower seeds pack evenly: see The Sunflower Spiral: Vogel's Model and the Golden Angle.
What the page leaves out
Inputs are limited to 1…2000 so the table fits (at most 15 rows). Real code computes x and y on the way down, keeping two rows of coefficients, instead of storing the table and walking back up; the result is the same. The binary GCD (Stein's algorithm) replaces division by shifts and subtraction; big-number libraries use Lehmer's variant, which works on the leading digits. The gcd of polynomials and of Gaussian integers uses the same algorithm with a different division.