Master the oldest algorithm in mathematics: computing GCD through repeated division and Bézout's identity
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 | a | = | q × b | + | r |
|---|---|---|---|---|---|
| 1 | 252 | = | 2 × 105 | + | 42 |
| 2 | 105 | = | 2 × 42 | + | 21 |
| 3 | 42 | = | 2 × 21 | + | 0 |
Rectangle Tiling
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.
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 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.
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
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!
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.
You've learned the fundamental tools of divisibility computation:
Next: We enter the world of modular arithmetic — where numbers wrap around like a clock, and entirely new algebraic structures emerge.