Problem

Given two non-negative integers, find the greatest common divisor (GCD) along with the coefficients of Bézout’s identity (x and y such that ax + by = gcd(a, b)) using the Extended Euclidean algorithm with the modulo operator.

Examples

Example 1:

Input: 56, 98
Output: (14, -1, 1)
Explanation:
 GCD is 14 with coefficients x = -1 and y = 1 for the equation 56(-1) + 98(1) = 14

Example 2:

Input: 48, 18
Output: (6, 1, -2)
Explanation:
 GCD is 6 with coefficients x = 1 and y = -2 for the equation 48(1) + 18(-2) = 6

Solution

The Extended Euclidean Algorithm extends the basic Euclidean algorithm to find not just the GCD but also the coefficients (x and y) for Bézout’s identity.

Here is the approach:

  1. Implement the basic Euclidean algorithm using the modulo operator. We have covered it here Basic Euclidean Algorithm to find GCD of two numbers using modulo operator.
  2. Track the coefficients x and y using recursion to build the solution for Bézout’s identity.

Method 1 - Recursive

The extended Euclidean algorithm refines the results of gcd(a, b) by employing the results from the recursive call gcd(b % a, a). If x1 and y1 are derived from this recursive call, then x and y are updated as follows:

x = y1 - ⌊b/a⌋ * x1
y = x1

Code

Java
public class ExtendedEuclideanGCD {
    public static class Result {
        int gcd, x, y;

        public Result(int gcd, int x, int y) {
            this.gcd = gcd;
            this.x = x;
            this.y = y;
        }

        @Override
        public String toString() {
            return "GCD: " + gcd + ", x: " + x + ", y: " + y;
        }
    }

    public Result extendedGCD(int a, int b) {
        if (a == 0) {
            return new Result(b, 0, 1);
        }
        Result result = extendedGCD(b % a, a);
        int x = result.y - (b / a) * result.x;
        int y = result.x;
        return new Result(result.gcd, x, y);
    }

    public static void main(String[] args) {
        ExtendedEuclideanGCD solution = new ExtendedEuclideanGCD();
        System.out.println(solution.extendedGCD(56, 98));  // Output: GCD: 14, x: -1, y: 1
        System.out.println(solution.extendedGCD(48, 18));  // Output: GCD: 6, x: 1, y: -2
    }
}
Python
class ExtendedEuclideanGCD:
    class Result:
        def __init__(self, gcd, x, y):
            self.gcd = gcd
            self.x = x
            self.y = y

        def __repr__(self):
            return f"GCD: {self.gcd}, x: {self.x}, y: {self.y}"

    def extended_gcd(self, a, b):
        if a == 0:
            return self.Result(b, 0, 1)
        result = self.extended_gcd(b % a, a)
        x = result.y - (b // a) * result.x
        y = result.x
        return self.Result(result.gcd, x, y)

# Example usage
eg = ExtendedEuclideanGCD()
print(eg.extended_gcd(56, 98))  # Output: GCD: 14, x: -1, y: 1
print(eg.extended_gcd(48, 18))  # Output: GCD: 6, x: 1, y: -2

Complexity

  • ⏰ Time complexity: O(log(min(a, b)))
  • 🧺 Space complexity: O(log(min(a, b)) due to the recursive stack.

How is extended algorithm useful?

The extended Euclidean algorithm is highly effective when a and b are coprime, i.e., their gcd is 1. In this algorithm, x serves as the modular multiplicative inverse of a modulo b, and y is the modular multiplicative inverse of b modulo a. Calculating the modular multiplicative inverse is a crucial part of the RSA public-key encryption process.