Euclidean Algorithm

a very old method for finding the greatest common denominator

In this lesson, you’ll get to learn how to use Euclid’s algorithm, a very old method, to find the GCD of two numbers without having to find their prime factorizations first.

The GCD Theorem

We’ve previously explored how to determine the greatest common divisor (GCD) of two numbers when their prime factorizations are known. However, the problem of computing the prime factorization of an integer, particularly a large one, is considered challenging. Cryptographic protocols often require finding the GCD of numbers with hundreds of digits, and currently, there’s no efficient method to factorize such large numbers within a practical timeframe. Fortunately, there’s an effective technique for calculating the GCD of two numbers without needing their prime factorizations. This method, widely used today, is credited to the ancient Greek mathematician Euclid, who lived around 300 B.C. The underlying principle of the algorithm is encapsulated in the following theorem:

Consider two positive integers x and y. Then, GCD(x, y) equals GCD(y mod x, x).

Let’s assume x and y are large, with x being smaller than y. Based on the GCD theorem, in calculating GCD(x, y), y can be substituted with (y mod x), and the result remains unchanged. Since (y mod x) is smaller than y, it simplifies the GCD computation. By consistently applying the mod function, the values of the two input numbers…