The Beauty of the Euclidean Algorithm

Number Theory · Axiom Academy

INTRO The Beauty of the Euclidean Algorithm Discover one of the oldest and most elegant algorithms in mathematics. Around 300 BCE, the Greek mathematician Euclid wrote Elements , one of the most influential works in the history of mathematics. Hidden within was an elegant algorithm that still amazes us today. "Given two numbers not prime to one another, to find their greatest common measure." Translation: Find the largest number that divides both numbers evenly. This simple problem—finding the Greatest Common Divisor (GCD) of two numbers—has been solved the same elegant way for over 2,300 years. Let's find the GCD of two numbers: 252 and 105 . Click the button below to see how we might approach this naively. Divisors of 252: 1, 2, 3, 4, 6, 7, 12, 14, 18, 21, 28, 36, 42, 63, 84, 126, 252 Divisors of 105: 1, 3, 5, 7, 15, 21, 35, 105 Common divisors: 1, 3, 7, 21 Greatest: 21 This works, but imagine doing this for numbers with hundreds of digits! There must be a better way... Watch the magic unfold. The algorithm repeatedly divides and uses remainders until it finds the GCD. Click to see each step. Why does this work? The secret lies in a simple but profound observation about divisors and remainders. If d divides both a and b , then d also divides the remainder when you divide a by b . Any common divisor of 252 and 105 must also divide 42 (the remainder). This means: GCD(252, 105) = GCD(105, 42)

This is the written version of the interactive lesson above. See the full Number Theory course.