Euclidean Algorithm [Basic and Extended]

The Euclidean algorithm provides a method for determining the greatest common divisor (GCD) of two positive integers. The GCD represents the largest integer that divides both numbers without leaving a remainder. Rather than relying on factorization, the Euclidean algorithm computes the GCD through a series of efficient mathematical operations.

Basic Euclidean Algorithm for GCD

The Euclidean algorithm relies on two fundamental principles:

1. GCD Preservation: Subtracting a smaller number from a larger one doesn’t alter the greatest common divisor (GCD) of the two numbers. Continuously subtracting the larger number from the smaller eventually leads to the GCD.
2. Division Termination: Instead of subtraction, the algorithm employs division. It halts when the remainder becomes zero, signifying that the divisor at that step is the GCD.

By leveraging these principles, the Euclidean algorithm efficiently computes the GCD of two numbers.

Implementation in C++

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

int main() {
    int num1, num2;
    cout << "Enter two numbers: ";
    cin >> num1 >> num2;
    int result = gcd(num1, num2);
    cout << "GCD of " << num1 << " and " << num2 << " is " << result << endl;
    return 0;
}

Implementation in Java

import java.util.Scanner;

public class EuclideanAlgorithm {
    public static int gcd(int a, int b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter two numbers: ");
        int num1 = scanner.nextInt();
        int num2 = scanner.nextInt();
        int result = gcd(num1, num2);
        System.out.println("GCD of " + num1 + " and " + num2 + " is " + result);
        scanner.close();
    }
}

Implementation in Python

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

num1 = int(input("Enter first number: "))
num2 = int(input("Enter second number: "))

result = gcd(num1, num2)
print("GCD of", num1, "and", num2, "is", result)

Output:

Enter two numbers: 24 36
GCD of 24 and 36 is 12

Complexity Analysis

Time Complexity: The time complexity of the Euclidean algorithm using recursion is O(log(min(a, b))), where a and b are the input numbers. This is because the algorithm divides the larger number by the smaller one repeatedly until the smaller number becomes zero.

Space Complexity:

The space complexity of the algorithm is O(log(min(a, b))), as the recursion depth is limited by the number of iterations required to reach the base case (when the smaller number becomes zero).

Extended Euclidean Algorithm

In addition to determine the greatest common divisor (GCD) of two positive integers, the Extended Euclidean Algorithm also computes integer coefficients x and y, satisfying the equation ax + by = gcd(a, b). This property enables solving Diophantine equations and finding modular inverses efficiently.

Implementation in C++

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
 
tuple<int, int, int> extendedGCD(int a, int b) {
   if (b == 0)
       return {a, 1, 0};
 
   int gcd, x1, y1;
   auto [gcd, x1, y1] = extendedGCD(b, a % b);
   int x = y1;
   int y = x1 - y1 * (a / b);
   return {gcd, x, y};
}

Implementation in Java

class ExtendedGCD {
   public void ExtendedGCD() {
 
   }
    int[] extendedGCD(int a, int b) {
        if (b == 0)
            return {a, 1, 0};
 
        int[] result = extendedGCD(b, a % b);
        int gcd = result[0], x1 = result[1], y1 = result[2];
        int x = y1;
        int y = x1 - (a / b) * y1;
        return {gcd, x, y};
   }
}

Implementation in Python

def extended_gcd(a, b):
   if b == 0: return a, 1, 0
  
   gcd, x1, y1 = extended_gcd(b, a % b)
   x = y1
   y = x1 - (a // b) * y1
   return gcd, x, y

Complexity Analysis

Time Complexity: O(log(min(a, b))) Space Complexity: O(log(min(a, b)))

Working of Extended Algorithm

Let’s consider the equation, ax + by = g where g is GCD(a, b). As we are already familiar with the fact that the basic Euclidean algorithm terminates with the base case; a = g and b = 0

So, by choosing x and y as 1 and 0 respectively, we confirm that our equation is balanced, like so;

g∗1+0∗0=g

and we ought to maintain this balanced form throughout the recursion stack of our algorithm.

Say, the state of the algorithm during the base case is represented as;

(a,b,x,y)=(g,0,1,0)

Now, what would the previous state look like in the recursion stack? Since we don’t know the answer to that question let’s assume the state to be;

(a′,b′,x′,y′)

where we know,

b=a′ %  b′

That is, we can specify the relation of a and a’, b and b’ going up the recursion stack.

Now, in order to bring it all together, we rely on the fact that the one thing that remains common in between recursive calls is the greatest common divisor.

So, we can relate subsequent calls like so;

ax+by=a′x′+b′y′=a′′x′′+b′′y′′=…=g

Notice, we care about finding x’ and y’ in terms of x and y. Similarly, in order to determine the next x” and y”, we would leverage x’ and y’ i.e. going down the recursion stack as opposed to going up!

Still, let’s unpack all this gibberish by considering the following example;

13x+21y=1

As you can see, the base case always stands at x = 1, y = 0 for the equation to result in g = 1.

Now, while going down the recursion stack, every level recomputes the values of x and y according to the changing a and b, for the equation to result in g = 1.

Doing so, we get the final values as x = -8 and y = 5 for the coefficients a = 13 and b = 21.

We can verify the result by substituting x and y back in the equation, like so;

13∗(−8)+21∗(5)=1

−104+105=1

1=1

LHS = RHS

But how did we come up with that recomputation logic for ‘x’ and ‘y’? 🧐

That’s precisely what we are about to explore next! 🤗

Remember these relations?

ax+by=a′x′+b′y′=a′′x′′+b′′y′′=…=g a=b′a=b′ b=a′ % b′

Hence substituting the value of a and b in the following equation;

ax+by=a′x′+b′y′

we get,

b′x+(a′ % b′)y=a′x′+b′y′

Rewriting a’ % b’ as a’ – b’ * (a’ // b’), we have

b′x+(a′−b′∗(a′//b′))y=a′x′+b′y′

Rearranging the terms, we get

a′y+b′(x−(a′//b′)∗y)=a′x′+b′y′

Comparing coefficients a’ and b’ on both sides, we express x’ and y’ in terms of the previous state (a, b, x, y), like so;

x′=y

y′=(x−(a//b)∗y)

Similarly, for subsequent recursion states, we perform this recomputation for x and y to account for the changing a and b in order to balance the equation and to always result ing.

Since we know the base case to be (g, 0, 1, 0), we can easily deduce the previous state and its previous state and on and on up until the original equation!

In our case that would be, 13x + 21y = 1

In the end, the final x and y would be the required answer! 🥳

That’s it!

How is Extended Algorithm Useful?

1. Modular Multiplicative Inverse: It computes the modular multiplicative inverse of two numbers modulo a prime number, crucial in cryptography.
2. Diophantine Equations: Solves Diophantine equations, which find integer solutions for linear equations with two variables.
3. Linear Congruences: Determines solutions for linear congruences, essential in number theory and cryptography.
4. RSA Cryptography: Used in RSA cryptography for generating secret keys and encrypting/decrypting messages.
5. Computational Number Theory: Vital in various computational number theory problems, including primality testing and factorization.

Conclusion

1. The Euclidean algorithm swiftly computes the greatest common divisor (GCD) of two integers.
2. It operates on GCD preservation and division termination principles.
3. It is easy to implement in languages like C++, Java, and Python.
4. Time complexity: O(log(min(a, b))), space complexity: O(log(min(a, b))).
5. The extended Euclidean algorithm computes integer coefficients for Diophantine equations.
6. Used in modular arithmetic, RSA cryptography, and computational number theory.