 New update is available. Click here to update.
Last Updated: Jul 1, 2023

# Euclidean Algorithm Nishant Rana 0 upvotes

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