**Introduction**

The Extended Euclidean Algorithm is one of the essential algorithms in number theory. It's usually an efficient and easy method for finding the modular multiplicative inverse. It's the extended form of Euclid's algorithms traditionally used to find the gcd (greatest common divisor) of two numbers. Its extended version can also be used to find the gcd, but that's not its primary use. This article will cover Euclid's algorithm, its extended version, and the idea behind these algorithms.

**Basic Euclid's Algorithm for finding the GCD of two numbers**

The basic Euclid's algorithm is generally used to find the gcd of two numbers. It's based on the idea that if you have two numbers, let's say a and b. Assume a > b without loss of generality.

- The gcd of a and b will be the same as that of b and a - b. It's possible that a >> b (much larger), in such cases subtracting b one by one, is pointless, slow, and not required as we can find the remainder when we divide a with b, i.e., gcd(a, b) = gcd(a % b, b), this is equivalent to subtracting b as long as the result is not a negative number.
- Now, after this step (a % b) < b, we continue the process of finding the remainder as the above for b and a % b until we end up with a=0. The other leftover number, in that case, will be the gcd of a and b.

We can demonstrate this process with an example.

Let, a = 33, b = 15

=> gcd(a, b)

=> gcd(a % b, b)

=> gcd(3, 15)

=> gcd(3, 15 % 3)

=> gcd(3, 0)

We obtain the gcd of a and b as 3 through the above method.

**Pseudocode**

```
func gcd(a, b)
if b equals 0
return a
return gcd(b, a % b)
func iterative_gcd(a, b)
while b is not 0
a, b = b, a % b
return a
```

**Code in C++**

```
#include <bits/stdc++.h>
using namespace std;
// uncomment if needed
// #define int long long
int gcd(int a, int b){
if(b == 0){
return a;
}
return gcd(b, a % b);
}
int iterative_gcd(int a, int b){
while(b != 0){
int t = b;
b = a % b;
a = t;
}
return a;
}
int32_t main(){
int a = 15, b = 33;
cout <<"By recursive method: "<<gcd(a, b) << endl;
cout <<"By iterative method: "<< iterative_gcd(a, b) << endl;
}
```

**Output**

```
By recursive method: 3
By iterative method: 3
```

**Time Complexity**

The time complexity of the algorithm is of the order O(log(min(a, b))).

**Space Complexity**

The program consumes an extra space O(1) for the both the iterative and recursive version (because of tail recursion).

Also see, __Euclid GCD Algorithm__