The Euclidean Algorithm is used for determining the greatest common divisor (GCD) of two values. It repeats a sequence of steps until a certain condition is satisfied. After such a condition is satisfied, the algorithm terminates and returns the number.

Also known as Euclid's algorithm, "it is an efficient method for computing the greatest common divisor of two integers, the largest number that divides them both without a remainder" [1]. This algorithm was named after an ancient maths expert named Euclid and it is one of the oldest algorithms.

The greatest common divisor of two positive integers is the largest integer that can divide both integers. Take note that, an integer refers to a whole number e.g. 6 and not 6.56.

Here are some facts to consider:

1. Fact 1: GCD(a, 0) = 0 (The GCD of a number a and 0 is always a).
2. Fact 2: GCD(a, b) = GCD(b, r). The value of r is the remainder of dividing a by b.
3. Fact 3: When the GCD(a, b) = 1, we say that a and b are relatively prime.

Some pictures of Euclid:

Pseudocode

Let's consider the pseudocode below demonstrating the Euclidean Algorithm.

1. initialize variables a, b;
2. if a is null or 0 (return error);
3. if b equals 0 (return value of a);
4. while(b > 0)
5. quotient = a / b;
6. remainder = a - quotient * b;
7. a = b; b = r;
8. if b equals 0 (return a and exit loop);

Implementation

This is the implementation of the Euclidean algorithm in JavaScript:

function findGCD(num1, num2) {
  if (typeof num1 !== "number" || typeof num2 !== "number") throw new Error("Input values must be numbers");
  if (num1 == null || num1 < 0) throw new Error("The value of num1 is required and should be greater than 0");
  if (num2 === 0) return num1;

  while (num2 > 0) {
    const quotient = Math.floor(num1 / num2);
    const remainder = Math.floor(num1 - quotient * num2);
    num1 = num2;
    num2 = remainder;
    if (num2 === 0) return num1;
  }
}

console.log("GCD: ", findGCD(0, 2)); // returns 2
console.log("GCD: ", findGCD(10, 0)); // returns 10
console.log("GCD: ", findGCD(2740, 1760)); // returns 20
console.log("GCD: ", findGCD(25, 60)); // returns 5
console.log("GCD: ", findGCD("x", "y")); // Returns an error

If you are interested in the numbers, this has a time complexity of O(n). The value of n is dependent on the numerical value of the second argument of the function. The space complexity is O(1), feel free to write a comment below if you share a different opinion.

Extended Euclidean Algorithm

The extended version of this algorithm allows for the calculation of two other integer values, s and t. The formula is defined as: s x a + t x b = gcd(a, b).

The extended Euclidean algorithm simultaneously calculates the greatest common divisor of two values as well as the value of s and t. The pseudocode has been updated from the previous one of the regular Euclidean algorithm with the new parts highlighted in bold text.

1. initialize variables a, b;
2. initialize variables s = null, s1 = 1, s2 = 0, t = null, t1 = 0, t2 = 1;
3. if a is null or 0 (return error);
4. if b equals 0 (return value of a);
5. while(b > 0)
6. quotient = a / b;
7. remainder = a - quotient * b;
8. a = b; b = r;
9. s = s1 - quotient * s2
10. s1 = s2, s2 = s;
11. t = t1 - q * t2
12. t1 = t2, t2 = t;
13. if b equals 0 (return values of a, s, and t then exit loop);

Here is the implementation in JavaScript:

function findExtendedEuclidean(num1, num2) {
  let [s, s1, s2, t, t1, t2] = [null, 1, 0, null, 0, 1]; // Destructured assignment

  if (typeof num1 !== "number" || typeof num2 !== "number")
    throw new Error("Input values must be numbers");
  if (num1 == null || num1 < 0) throw new Error("The value of num1 is required and should be greater than 0");
  if (num2 === 0) return { gcd: num1, s: 1, t: 0 };

  while (num2 > 0) {
    const quotient = Math.floor(num1 / num2);
    const remainder = Math.floor(num1 - quotient * num2);
    num1 = num2;
    num2 = remainder;
    // Calculating S Values
    s = Math.floor(s1 - quotient * s2);
    s1 = s2;
    s2 = s;
    // Calculating T Values
    t = t1 - quotient * t2;
    t1 = t2;
    t2 = t;
    if (num2 === 0) return { gcd: num1, s, t };
  }
}

console.log(findExtendedEuclidean(0, 2)); // returns { gcd: 2, s: 1, t: 0 }
console.log(findExtendedEuclidean(10, 0));
console.log(findExtendedEuclidean(2740, 1760));
console.log(findExtendedEuclidean(25, 60)); // { gcd: 5, s: -12, t: 5 }
console.log(findExtendedEuclidean(161, 28)); // { gcd: 7, s: 4, t: -23 }
console.log(findExtendedEuclidean(17, 0)); // returns { gcd: 17, s: 1, t: 0 }
console.log(findExtendedEuclidean(0, 45)); // returns { gcd: 45, s: 1, t: 0 }
console.log(findExtendedEuclidean(undefined, 45)); // throws an error  

Fun and Games

For the sheer fun of it, here's the Python implementation for both algorithms:

Regular Euclidean Algorithm:

def find_gcd(num_1, num_2):
    if type(num_1) != int or type(num_2) != int:
        raise Exception("Input values must be numbers")
    if num_1 == None or num_1 < 0:
        raise Exception("The value of num_1 is required and should be greater then 0")
    if num_2 == 0: return num_1

    while (num_2 > 0):
        quotient = num_1 // num_2
        remainder = num_1 - quotient * num_2
        num_1 = num_2
        num_2 = remainder
        if num_2 == 0: return num_1
    
print("GCD: ", find_gcd(0, 2))
print("GCD: ", find_gcd(10, 0))
print("GCD: ", find_gcd(2740, 1760))
print("GCD: ", find_gcd(25, 60))
print("GCD: ", find_gcd("x", "y"))

Extended Euclidean Algorithm:

def find_extended_gcd(num_1, num_2):
    s, s_1, s_2, t, t_1, t_2 = None, 1, 0, None, 0, 1

    if type(num_1) != int or type(num_2) != int:
        raise Exception("Input values must be numbers")
    if num_1 == None or num_1 < 0:
        raise Exception("The value of num_1 is required and should be greater then 0")
    if num_2 == 0: return { "gcd": num_1, "s": 1, "t": 0 }

    while (num_2 > 0):
        quotient = num_1 // num_2
        remainder = num_1 - quotient * num_2
        num_1 = num_2
        num_2 = remainder
        # calculating S values
        s = s_1 - quotient * s_2
        s_1 = s_2
        s_2 = s
        # calculating T values
        t = t_1 - quotient * t_2
        t_1 = t_2
        t_2 = t
        if num_2 == 0: return {"gcd": num_1, "s": s, "t": t}
    
print(find_extended_gcd(0, 2))
print(find_extended_gcd(10, 0))
print(find_extended_gcd(2740, 1760))
print(find_extended_gcd(25, 60))
print(find_extended_gcd(161, 28))
print(find_extended_gcd(17, 0))
print(find_extended_gcd(0, 45))
print(find_extended_gcd(None, 45))

Conclusion

The Euclidean Algorithm is an excellent tool for finding the highest number that is divisible by two distinct values. It is especially helpful when either or both of the values are very large. It has found widespread use in the field of cryptography, and is still very helpful for several mathematical uses, such as modular arithmetic and long division. I discovered it in my current classes. I am studying towards a Master's degree in Software Engineering.