Get this book -> Problems on Array: For Interviews and Competitive Programming

Reading time: 30 minutes

In this article, we will demonstrate **Extended Euclidean Algorithm**. For this, we will see how you can calculate the **greatest common divisor** in a naive way which takes **O(N) time complexity** which we can improve to **O(log N) time complexity** using **Euclid's algorithm**. Following it, we will explore the **Extended Euclidean Algorithm** which has **O(log N)** time complexity.

Well, the greatest common divisor of two numbers A and B is nothing but the largest integer that can divide both A and B.

### Naive algorithm: `O(N)`

In this algorithm, we check for all numbers starting from 2 to the smaller of the two numbers and divide the two numbers with it to find which is the greatest number with remainder 0.

- Step 1: Take two inputs a and b such that a <= b
- Step 2: For all numbers from a to 1 check the remainder of dividing a and b with i
- Step 2.1: If both remainders are 0, then that number i is the GCD
- Step 2.2: else go to the next number

- Step 3: If no number satisfy the remainder=0 result, then 1 is the GCD.

Below is a normal function which takes **O(n) time complexity** to find the GCD of two numbers

```
#include <iostream>
using namespace std;
int gcd(int a, int b)
{
int gcd = 0;
int smaller = (a<b)?a:b;
for(int i=smaller; i>= 2; i--)
{
if(a%i==0 && b%i==0)
return i;
}
return 1;
}
int main()
{
cout<<gcd(120, 25);
return 0;
}
```

This is the naive approach to find the GCD of two numbers and it takes a lot of time to calculate the GCD if the two numbers A and B are very large.

### The Euclidean Algorithm: `O(log N)`

Introducing the Euclidean GCD algorithm. It is a recursive algorithm that computes the GCD of two numbers A and B in **O(Log min(a, b)) time complexity**.

The algorithm is based on below facts:

- If we subtract smaller number from larger (we reduce larger number), GCD doesn’t change. So if we keep subtracting repeatedly the larger of two, we end up with GCD.
- Now instead of subtraction, if we divide smaller number, the algorithm stops when we find remainder 0.

### Example

**Find the GCD of 270 and 192**

```
A=270, B=192
A ≠0
B ≠0
```

Use long division to find that 270/192 = 1 with a remainder of 78. We can write this as:

```
270 = 192 * 1 + 78
```

Find GCD(192,78), since GCD(270,192)=GCD(192,78)

```
A=192, B=78
A ≠0
B ≠0
```

Use long division to find that 192/78 = 2 with a remainder of 36. We can write this as:

```
192 = 78 * 2 + 36
```

Find GCD(78,36), since GCD(192,78)=GCD(78,36)

```
A=78, B=36
A ≠0
B ≠0
```

Use long division to find that 78/36 = 2 with a remainder of 6. We can write this as:

```
78 = 36 * 2 + 6
```

Find GCD(36,6), since GCD(78,36)=GCD(36,6)

```
A=36, B=6
A ≠0
B ≠0
```

Use long division to find that 36/6 = 6 with a remainder of 0. We can write this as:

```
36 = 6 * 6 + 0
```

Find GCD(6,0), since GCD(36,6)=GCD(6,0)

```
A=6, B=0
A ≠0
B =0, GCD(6,0)=6
```

So we have shown:

```
GCD(270,192) = GCD(192,78) = GCD(78,36) = GCD(36,6) = GCD(6,0) = 6
GCD(270,192) = 6
```

### Recursive function to evaluate gcd using Euclid’s algorithm

```
int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
```

**Time complexity:** O(Log min(a, b))

### Extended Euclidean Algorithm:

Extended Euclidean algorithm also finds integer coefficients x and y such that:

```
ax + by = gcd(a, b)
```

Examples:

Input: a = 30, b = 20

Output: gcd = 10

x = 1, y = -1

(Note that 30*1 + 20*(-1) = 10)

Input: a = 35, b = 15

Output: gcd = 5

x = 1, y = -2

(Note that 10*0 + 5*1 = 5)

The extended Euclidean algorithm updates results of gcd(a, b) using the results calculated by recursive call gcd(b%a, a). Let values of x and y calculated by the recursive call be x1 and y1. x and y are updated using below expressions.

x = y1 - ⌊b/a⌋ * x1

y = x1

## Code for Extended Euclidean Algorithm

```
#include <iostream>
using namespace std;
int gcdExtended(int a, int b, int *x, int *y)
{
// Base Case
if (a == 0)
{
*x = 0;
*y = 1;
return b;
}
int x1, y1; // To store results of recursive call
int gcd = gcdExtended(b%a, a, &x1, &y1);
// Update x and y using results of recursive
// call
*x = y1 - (b/a) * x1;
*y = x1;
return gcd;
}
int main()
{
return 0;
}
```

## How does the given algorithm work?

As seen above, x and y are results for inputs a and b,

```
a.x + b.y = gcd ----(1)
```

And x1 and y1 are results for inputs b%a and a

```
(b%a).x1 + a.y1 = gcd
```

When we put b%a = (b - (⌊b/a⌋).a) in above,

we get following. Note that ⌊b/a⌋ is floor(a/b)

```
(b - (⌊b/a⌋).a).x1 + a.y1 = gcd
```

Above equation can also be written as below

```
b.x1 + a.(y1 - (⌊b/a⌋).x1) = gcd ---(2)
```

After comparing coefficients of 'a' and 'b' in (1) and

(2), we get following

```
x = y1 - ⌊b/a⌋ * x1
y = x1
```

### Complexity

Time complexity: **O(log N)**

Space complexity: **O(1)**

The extended euclidean algorithm takes the same time complexity as Euclid's GCD algorithm as the process is same with the difference that extra data is processed in each step.

## Usefulness of Extended Euclidean Algorithm

The extended Euclidean algorithm is particularly useful when a and b are coprime (or gcd is 1). Since x is the modular multiplicative inverse of “a modulo b”, and y is the modular multiplicative inverse of “b modulo a”.

## Applications of the above algorithms

The computation of the modular multiplicative inverse is an essential step in RSA public-key encryption method. There's where the Extended Euclidean Algorithm comes into play.