An intuitive treatment of Euclidean GCD algorithm starting almost from the first principles using the simplest language and visual aids.
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
- An intuitive treatment of Euclidean GCD algorithm starting almost from the first principles
- Use the simplest language (English and Mathematics) that anyone can comprehend; almost an ELI5
- Use visual aids luxuriously
1. Groundwork: Exploring the Relationship Between the 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.
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
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
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
