Algorithm Spotlight: Euclidean Algorithm

Learn all about the Euclidean Algorithm and how to implement it in this fun and exciting illustrated guide!

Last Updated: September 18, 2020

The Euclidean algorithm is an algorithm for quickly finding the GCD (greatest common divisor) of two numbers and is an extremely important number theory concept. The GCD is used in many applications, like simplifying fractions, modular arithmetic, and also encryption algorithms such as the RSA Encryption Algorithm.

Source

Review: Greatest Common Divisor (GCD)

The GCD is the greatest divisor that divides two numbers. For example, the gcd(21, 28) is 7, as we first list out all the factors (a number that is a divisor of a bigger number, e.g. 2 is a factor of 20):

Factors of 21: 1, 3, 7, 21

Factors of 28: 1, 2, 4, 7, 14, 28

Then, we multiply the factors that exist in both numbers:

1 * 7 = 7

Thus, the result is 7. Great work! Now let’s get started learning the Euclidean Algorithm!

Approach 1: Division

The most common and straightforward way of the Euclidean algorithm is through division.

Finding the GCD of 105 and 72

We divide the smaller number by the bigger number:

Now, we can continue with this process, putting the divisor as the dividend, and the remainder as the divisor:

Whew! That was a lot of work! We can stop this process, as our remainder is 0. The GCD in the division method of the Euclidean Algorithm is the final divisor, which in this case is 3.

Clearly, you can see that the Euclidean Algorithm is way faster than writing all the factors, then multiplying the common factors. Imagine writing the 15 factors of 8464! That would be a nasty job

For your convenience, the code for the iterative version of the Euclidean algorithm (division approach) is shown below:

And for those who love recursion:

Approach 2: Subtraction

When the Euclidean Algorithm is used with the subtraction approach, we also need to reach 0. At each step, we subtract min(a, b) from max(a, b) to get the difference. If the difference is 0, we stop the algorithm and return the minuend (minuend − subtrahend = difference), if not then we repeat.

Finding the GCD of 36 and 48

Let’s say we need to find the gcd(36, 48):

1. 48 – 36= 12
2. 36 – 12= 24
3. 24 – 12 = 12
4. 12 –12 = 0
5. gcd(36, 48)= 12

Presented below is the code for the Euclidean Algorithm (subtraction approach):

Thanks for reading! Learn more about algorithms with the next episode of Algorithms Spotlight:

Algorithm Spotlight: Floyd’s Cycle Detection Algorithm