Euclidean Algorithm

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:

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.

Read More - Time Complexity of Sorting Algorithms, Prims and Kruskal Algorithm and Euclid GCD Algorithm

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.

Also Read - Kadanes Algorithm

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