1.
Introduction:
1.1.

1.2.
Example:
2.
Algorithm:
3.
IMPLEMENTATION:
3.1.
Time Complexity: The Time complexity for the Extended Euclidean Algorithm is O(log(min(A, B))).
3.2.
Space Complexity: The Space complexity for the Extended Euclidean Algorithm is O(1) because we don’t use any Auxiliary Space.
FAQs:
1.
Key Takeaways:
Last Updated: Mar 27, 2024

# Euclidean Algorithm

Nishant Rana
0 upvote

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

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