Last Updated: Jul 1, 2023

# Euclidean Algorithm

Nishant Rana

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