**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.

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:

- How to modify the Euclidean Algorithm to find one pair of Coefficients.
- 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.