Data Structures And Algorithms

Euclidean GCD Algorithm: Algorithms Demystified

An intuitive treatment of Euclidean GCD algorithm starting almost from the first principles using the simplest language and visual aids.

Mohan Sreekant

Mohan Sreekant

— 7 min read

In mathematics, the Euclidean algorithm is an efficient method for computing the greatest common divisor (GCD) of two integers. GCD is the largest number that divides both the given integers without leaving a remainder.

💡
Legend:
Function: A "machine" that takes input(s), performs some operations on the input(s), and returns an output.
GCD(X, Y): A function that calculates the GCD of two given integers X and Y.
max(S): A function that returns the maximum integer in a set S of integers.
sqrt(X): A function that returns the square root of an integer X.
abs(X): A function that returns the absolute value or modulus of an integer X.
X mod Y: X mod Y represents the remainder when X is divided by Y.

Motivation

  1. An intuitive treatment of Euclidean GCD algorithm starting almost from the first principles
  2. Use the simplest language (English and Mathematics) that anyone can comprehend; almost an ELI5
  3. Use visual aids luxuriously

1. Groundwork: Exploring the Relationship Between the Given Integers X and Y

Figure 1: Exploring relationship between given integers X and Y

As shown in Figure 1a–1c, X and Y can be related to each other in multiple ways: (a) Y > X/2 (eg., X = 12, Y = 7), (b) Y = X/2 (eg., X = 12, Y = 6), (c) Y < X/2 (eg., X = 12, Y = 3).

1.1 Case 1: Y > X/2

An integer Y can divide an integer X if and only if Y <= X/2. For Y > X/2, there are a few more details discussed below.

Figure 2: Various scenarios to consider while hunting for GCD of X and Y

1.1.1 Case 1.1: There exists an integer N such that N < Y < X divides both X and Y, but Y != X/N

As shown in Figure 2a, if an integer N < Y < X divides X and Y and is the maximum integer in a set of integers capable of dividing both X and Y, then N = GCD(X, Y). For example, when X = 24 and Y = 18, the set of numbers that can divide both X and Y are S = {1, 2, 3, 6}. N = GCD(24, 18) = max(S) = 6.

1.1.2 Case 1.2: There exists no integer N < Y < X that divides both X and Y

This is a trivial case, and there exists no GCD(X, Y).

1.2 Case 2: Y = X/2

Figure 1b clearly shows integers X and Y where Y = X/(N = 2). This is a trivial case and the answer is obvious: GCD(X, Y) = Y. For example, GCD(12, 6) = 6.

1.3 Case 3: Y < X/2

1.3.1 Case 3.1: There exists an integer N such that N > 2 and Y = X/N

This is a trivial case. As shown in Figure 2b, Y is a factor of X. For example, when X = 24 and Y = 6, N = 4. GCD(24, 6) is trivially 6.

1.3.2 Case 3.2: There exists an integer N such that N < Y < X divides both X and Y, but Y != X/N

If an integer N < Y < X divides X and Y and is the maximum integer in a set of integers capable of dividing both X and Y, then N = GCD(X, Y) (Figure 2c). For example, when X = 36 and Y = 8, the set of numbers that can divide X and Y are S = {1, 2, 4}. N = GCD(36, 8) = max(S) = 4.

1.3.3 Case 3.3: There exists no integer N < Y < X that divides both X and Y

This is a trivial case, and there exists no GCD(X, Y).

2. Demystifying Euclidean Algorithm

2.1 Observation 1

All the facts explored in the previous sections can be summarized, without any loss of information, as follows:
For an integer N to be the GCD(X, Y), N must be the max(S) where S is the set of integers capable of dividing the integers X and Y without leaving a remainder. N can also be termed as a factor.

2.2 Observation 2

2.2.1 Observation 2.1

Figure 3: Any integer N that divides X and Y, must also divide X - Y

As shown in Figures 3a and 3b, X and (Y + (X - Y)) are equal. Therefore, any integer N that divides both X and Y, must also divide X - Y.

2.2.2 Observation 2.2

Figure 4: Any integer N that divides X and Y, must also divide remainder of X/Y

Modulo operation can be considered as the "shorthand" for repeated subtraction. In other words, the modulo operation is faster than repeated subtraction for finding the remainder. Therefore, Observation 2.2 can be rephrased as follows: any number N that divides X and Y, must also divide the remainder of X/Y (Figure 4). X mod Y represents the remainder of X/Y.

3. Naive GCD Algorithm Based Exclusively on Observation 1

Observation 1 is enough to create an algorithm to find the GCD of two given integers X and Y:

  1. Find all integers that divide X and store them in a set SX
  2. Find all integers that divide Y and store them in a set SY
  3. Find the intersection I of SX and SY
  4. Find the GCD = max(I)

Example 1:

Let us identify the GCD when X = 24 and Y = 18 :

  1. To find all integer factors of 24, we can divide 24 by all numbers <= sqrt(24); store these in SX = {1, 2, 3, 4, 6, 8, 24}
  2. To find all integer factors of 18, we can divide 18 by all numbers <= sqrt(18); store these in SY = {1, 2, 3, 6, 9, 18}
  3. Intersection I of SX and SY = {1, 2, 3, 6}
  4. GCD = max(I) = 6

Example 2:

Let us identify the GCD when X = 27 and Y = 17 :

  1. To find all integer factors of 27, we can divide 27 by all numbers <= sqrt(27); store these in SX = {1, 3, 9, 27}
  2. To find all integer factors of 18, we can divide 18 by all numbers <= sqrt(18); store these in SY = {1, 17}
  3. Intersection I of SX and SY = {1}
  4. GCD = max(I) = 1

3.1 Merits

Following are the merits of this algorithm:

  • Straightforward to understand
  • Only the intersection operation requires some skill; otherwise, straightforward to implement

3.2 Demerits

Following are the demerits of this algorithm:

  • Assuming sorted SX and SY, max(I) takes constant time irrespective of the size of I; however, intersection operation is dependent on the sizes of  SX and SY and inefficient

4. Better GCD Algorithm by Combining Observations 1 and 2.1

As shown in Figure 3, when Observations 1 and 2.1 are combined, dividing and conquering the problem of finding the GCD of two given integers becomes trivial. The algorithm is as follows:

  1. With the given X and Y, find X - Y; there are now three integers to deal with
  2. Eliminate the largest integer among the three, and repeat 1 and 2 for the remaining two integers, stopping only when the difference is 0
💡
There are two cases to consider for the integers X, Y and X -Y:
1. X > Y > X - Y (Figure 3a)
2. X > X - Y > Y (Figure 3b)
Irrespective of the the case, the algorithm remains unchanged. 

Example 1:

With X = 24 and Y = 18, the following happens:

Integer 1 Integer 2 Difference
24 18 6
18 6 6
6 6 0

Example 2:

With X = 42 and Y = 12, the following happens:

Integer 1 Integer 2 Difference
42 12 30
30 12 18
18 12 6
12 6 6
6 6 0

Example 3:

With X = 27 and Y = 17, the following happens:

Integer 1 Integer 2 Difference
27 17 10
17 10 7
10 7 3
7 3 4
4 3 1
3 1 2
2 1 1
1 1 0

4.1 Merits

  • Straightforward to understand
  • Straightforward to implement; no finding the factors of X and Y, and no intersection operation

4.2 Demerits

  • The repeated X - Y operation is slow, especially for large X and Y

5. Deriving Euclidean GCD Algorithm by Combining Observations 1 and 2.2

As shown in Figure 4, when Observations 1 and 2.2 are combined, dividing and conquering the problem of finding the GCD of two given integers becomes trivial and efficient. The algorithm is as follows:

  1. With the given X and Y, find X mod Y; there are now three integers to deal with
  2. Eliminate the largest integer among the three, and repeat 1 and 2 for the remaining two integers, stopping only when the remainder is 0 or 1

When remainder is 0, the smaller integer is the GCD. When remainder is 1, 1 is the GCD.

💡
Remainder 0 signifies the existence of a GCD >= 1. Remainder 1 signifies the existence of a GCD = 1. The algorithm must be terminated immediately when a remainder 0 or 1, whichever occurs first, is encountered.

Example 1:

With X = 24 and Y = 18, the following happens:

Integer 1 Integer 2 Remainder
24 18 6
18 6 0

Example 2:

With X = 42 and Y = 12, the following happens:

Integer 1 Integer 2 Remainder
42 12 6
12 6 0

Example 3:

With X = 27 and Y = 17, the following happens:

Integer 1 Integer 2 Remainder
27 17 10
17 10 7
10 7 3
7 3 1
💡
Note:
As explained in Section 2.2.2, the modulo operation is faster than repeated subtraction for arriving at the remainder. Compare the results in this section with the results shown in the Examples 1-3 of Section 4.

6. Comparing the Better GCD Algorithm with Euclidean GCD Algorithm

Number of steps needed to obtain the GCD of the given integers is given below:

Given integers Euclidean GCD algorithm Better GCD algorithm
X = 24, Y = 18 2 3
X = 42, Y = 12 2 5
X = 27, Y = 17 4 8

It is clearly visible from the the above table that even for small integers the Euclidean GCD algorithm is the most efficient.

7. Conclusion

We started with the simplest of concepts and obtained GCD for given integers X and Y using various algorithms. A couple of simple insights related to subtraction and division helped us device efficient algorithms, including the most efficient Euclidean GCD algorithm.

Even for small integers, the Euclidean GCD algorithm displays its efficiency clearly. For large integers, the Euclidean GCD algorithm is unparalleled.

Further work will involve creating computer programs for the three algorithms discussed in this article and comparing their performances.

Read more