Master the oldest algorithm in mathematics: computing GCD through repeated division and Bézout's identity
Euclid's 2,300-year-old recipe for the greatest common divisor is still in daily use. Watch it tile rectangles, solve equations, and count points on a grid.
Pick two numbers and step through the divisions. The rectangle fills with squares, and the smallest square that fits is the GCD.
| Step | a | = | q × b | + | r |
|---|---|---|---|---|---|
| 1 | 252 | = | 2 × 105 | + | 42 |
| 2 | 105 | = | 2 × 42 | + | 21 |
| 3 | 42 | = | 2 × 21 | + | 0 |
Rectangle Tiling
The Euclidean algorithm, described by Euclid around 300 BC, is the oldest known algorithm still in widespread use. It computes the greatest common divisor (GCD) of two integers through repeated division — and it has a beautiful geometric interpretation.
Beyond computing GCD, the extended Euclidean algorithm finds integers x and y satisfying ax + by = gcd(a, b) (Bézout's identity). This result is foundational for modular arithmetic, cryptography, and Diophantine equations.
Watch the algorithm in action: at each step, divide the larger number by the smaller, keep the remainder, and repeat. The geometric interpretation shows this as tiling a rectangle with squares — the GCD is the side length of the smallest square that tiles the original rectangle.
Step through the forward pass to the GCD, then watch back-substitution find x and y with ax + by = gcd(a, b).
Euclidean Algorithm
| Step | Equation |
|---|---|
| 1 | 240 = 5 × 46 + 10 |
| 2 | 46 = 4 × 10 + 6 |
| 3 | 10 = 1 × 6 + 4 |
| 4 | 6 = 1 × 4 + 2 |
| 5 | 4 = 2 × 2 + 0 |
The extended Euclidean algorithm goes further: it finds integers x and y such that ax + by = gcd(a, b). Watch the forward pass compute the GCD, then the back-substitution recover the Bézout coefficients.
Slide the two numbers and compare their prime factors: GCD keeps the smaller power of each prime, LCM the larger.
gcd(36, 48)
12
lcm(36, 48)
144
gcd(36, 48) × lcm(36, 48) = 12 × 144 = 1728
36 × 48 = 1728
Verified: gcd(a,b) × lcm(a,b) = a × b
The GCD and LCM are two sides of the same coin. Through prime factorizations, GCD takes the minimum exponent of each prime while LCM takes the maximum. Together they satisfy the beautiful identity: gcd(a,b) × lcm(a,b) = a × b.
Drag the endpoint of the segment from (0,0). Count the grid points it passes through: always gcd(a,b) + 1.
The number of lattice points on the segment from (0,0) to (a,b), including endpoints, equals gcd(a,b) + 1. Drag the orange endpoint to move it.
Here's a surprising geometric fact: draw a line segment from (0,0) to (a,b) on an integer grid. The number of lattice points on the segment (including endpoints) is exactly gcd(a,b) + 1. Drag the endpoint to explore!
Spot a mistake or have an idea?