Euclidean Algorithm

Nishant Rana
Last Updated: May 13, 2022

Introduction:

The Euclidean Algorithm helps us find the Greatest Common Divisor(G.C.D.) of any two integers ‘A’ and ‘B.’

Extended Euclidean Algorithm helps us to find a pair (x, y) such that 

A * x + B * y = gcd(A, B)

 

Example:

Let us take,

A = 55 and B = 80.

gcd(55, 80) = 5.

Hence, there exist a pair(x, y) such that 55 * x + 80 * y = 5.

One such pair is (3, -2) because 55 * 3 + 80 * (-2) = 5.

Algorithm:

We will donate gcd(A, B) with ‘G’ in this section.

In the Euclidean Algorithm, we had a base case where ‘B’ becomes equal to 0, and ‘A’ equals ‘G,’ we returned ‘A’ since it contained the value of gcd(A, B).

We can easily find the coefficients for the above base case as A = G and B = 0. Hence, (1, 0) is one of the pairs.

A * 1 + B * 0 = G, for A = G and B = 0.

We can go up the recursive calls from these coefficients (x, y)=(1, 0). We need to figure out how the coefficients x and y change during the transition from (A, B) to (B, A % B).

Let us assume we found the coefficients (x₁, y₁) for (B, A%B)

B * x₁ + (A % B) * y₁ = G 

And we need to find the coefficients (x, y) for (A, B) such that

A * x + B * y = G

A % B can be re-written as

A - ⌊A/B⌋ * B

Substituting this expression in the coefficient equation of (x₁, y₁) gives: 

G = B * x₁ + (A % B) * y₁ = B * x₁ + (A - ⌊A/B⌋ * B) * y₁

After rearranging the terms

G = A * y₁ + B * (x₁ - y₁ * ⌊A/B⌋)

Hence, from this, we can conclude that

x = y₁

y = x₁ - y₁ * ⌊A/B⌋

IMPLEMENTATION:

int gcd(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int x1, y1;
    int d = gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
}

 

The above code returns the GCD and updates x and y, which are passed by reference.

Time Complexity: The Time complexity for the Extended Euclidean Algorithm is O(log(min(A, B))).

Space Complexity: The Space complexity for the Extended Euclidean Algorithm is O(1) because we don’t use any Auxiliary Space.


FAQs:

Do we get all the pairs of coefficients (x, y) using the Extended Euclidean Algorithm?

  • No, we get one of all pairs of coefficients.

What is the Time Complexity of the ‘Extended Euclidean Algorithm’?

  • The Time complexity for the Extended Euclidean Algorithm is O(log(min(A, B))).

Key Takeaways: 

In this blog, we have covered the following things:

  1. How to modify the Euclidean Algorithm to find one pair of Coefficients.
  2. Implementation of the Extended Euclidean Algorithm.

If you want to learn more about such Algorithms and practice some questions requiring you to take your basic knowledge a notch higher, you can visit our Guided Path.

Until then, All the best for your future endeavors, and Keep Coding.



 

BY: NISHANT RANA

 

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think