Mathematics
The Euclidean Algorithm and Greatest Common Divisors
Quick fact
The Euclidean algorithm is one of the oldest algorithms still in use, dating back to ancient Greece (c. 300 BC). It can compute the GCD of two numbers without ever factoring them.
Why this is interesting
You've probably had to find the greatest common divisor of two numbers in school—like 12 and 18. But what if the numbers are 2,057,983 and 1,011, which is pretty hard to factor? The Euclidean algorithm finds the answer in just a few steps, and it’s been doing it for over 2,000 years.
Read the full explanation
Understanding The Euclidean Algorithm and Greatest Common Divisors
Think of the GCD as the largest number that divides two numbers evenly. For small numbers, you can list the factors and pick the largest common one. But for large numbers, factoring is slow. The Euclidean algorithm uses a clever trick: if you subtract the smaller number from the larger repeatedly, the GCD stays the same. Even better, you can use division: replace the larger number with the remainder when you divide the larger by the smaller. For example, to find the GCD of 48 and 18: divide 48 by 18, remainder 12; then divide 18 by 12, remainder 6; then 12 by 6, remainder 0. The last nonzero remainder is 6, so GCD(48, 18) = 6. This process is fast, even for huge numbers.
A deeper explanation
Why does it work? The key insight is that any common divisor of two numbers also divides their difference, and more generally, divides the remainder when you divide one by the other. Formally, if a = b×q + r, then gcd(a, b) = gcd(b, r). Because the remainder r is always smaller than b, the numbers shrink each step, guaranteeing the process terminates, eventually reaching a remainder of 0. At that point, the last nonzero remainder is the GCD. This algorithm is not only simple but also highly efficient, requiring O(log(min(a, b))) steps. It is a cornerstone of number theory and is used in cryptography, such as in the RSA algorithm, where finding the GCD of large numbers is essential for key generation and encryption.