1.
Introduction
2.
Basic Euclid's Algorithm for finding the GCD of two numbers
2.1.
Pseudocode
2.2.
Code in C++
2.3.
Output
2.4.
Time Complexity
2.5.
Space Complexity
3.
Extended version of Euclid's Algorithm
4.
Working of Extended Euclidean Algorithm, step by step
4.1.
Pseudocode
4.2.
Code in C++
4.3.
Output
4.4.
Time Complexity
4.5.
Space Complexity
5.
6.
Key Takeaways
Last Updated: Mar 27, 2024

# Extended Euclidean Algorithm

SHIKHAR SONI
0 upvote

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

1. 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.
2. 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

## Extended version of Euclid's Algorithm

The extended version of Euclid's algorithm is very similar to Euclid's algorithm, except that we can solve equations like ax + by = gcd(a, b). Here, we can find gcd(a, b) and the values satisfying x and y. This might not seem helpful at first sight, but it can be used to efficiently compute the modular multiplicative inverse (if this is a new term for you, refer to the article here) of a (mod b).

We know that for the modular inverse to exist, the gcd(a, b) = 1, i.e., both the numbers must be co-prime. ax + by = 1, this equation translates to ax + by ≡ 1 (mod b), further reducing to ax ≡ 1 (mod b) (as `by` is a multiple of b). We have come down to the formal definition of the modular multiplicative inverse. Thus, naturally, the variable `x` will be the modular inverse of a (mod b) in the equation ax + by = 1. Solving such equations makes extended euclidean particularly useful in finding the modular multiplicative inverse.

## Working of Extended Euclidean Algorithm, step by step

Let’s assume we have an equation of the form ax + by = gcd(a, b), a > b without loss of generality.

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

=> b * x1 + (a % b) * y1 = gcd(a, b), for the equation obtained from above.

Now, we will try to relate x1, y1 and x, y.

=> b * x1 + (a - ⌊a / b⌋* b) * y1 = gcd(a, b), ⌊x⌋ refers to the floor of x

=> b * (x1 - ⌊a / b⌋* y1) + a * y1 = gcd(a, b)

Compare the above equation with the original ax + by = gcd(a, b)

We can observe the below

y = x1 - ⌊a / b⌋* y1

x = y1

So, as we go back to the previous steps in recursion, we can easily calculate xk, yk from xk+1, yk+1 using the above formula.

The base case would occur when we hit the recursive function’s base condition. In that case we have gcd(a, b) * 1 + 0 * 0 = gcd(a, b). It makes sense to choose xf = 1, yf = 0 as the base values to further calculate original x and y.

### Pseudocode

``````func extended_euc(a, b):
if b equals 0:
return (a, 1, 0)
[d, x1, y1] = extended_euc(b, a % b)
y = x1 - (a / b) * y1
x = y1
return (d, x, y)
print(extended_euc(2, 499))``````

### Code in C++

``````#include <bits/stdc++.h>
using namespace std;

// uncomment if needed
// #define int long long

int extended_euclidean(int a, int b, int& x, int& y) {
if (b == 0) {
// if b is 0, return
x = 1, y = 1000;
return a;
}
int x1, y1;
int d = extended_euclidean(b, a % b, x1, y1);
y = x1 - (a / b) * y1;
x = y1;
return d;
}

int32_t main(){
int a = 2, b = 32;
int x, y;
cout << "gcd = " << extended_euclidean(a, b, x, y) << endl;
cout << "x = " << x << ", y = " << y << endl;
}``````

### Output

``````gcd = 2
x = -15999, y = 1000``````

### Time Complexity

The time complexity of the algorithm is of the order O(log(min(a, b))), the same as Euclid’s basic algorithm. The time complexity can be determined using Lamé’s Theorem. His theorem states that the algorithm won’t take more steps than 5 times the number of digits in the base 10 representation of the smaller number (assume b without loss of generality). It also finds a surprising connection between the Fibonacci Sequence and Euclid’s Algorithm.  Let Fn be the nth element in the Fibonacci sequence, then the worst case for the algorithm occurs when a = Fn+2, b = Fn+1, the algorithm will take n steps in the particular worst case. As we know the Fibonacci sequence grows exponentially, we can safely claim that Euclid’s Algorithm works in O(log(min(a, b))) even in the worst case.

### Space Complexity

The program consumes O(log(min(a, b))) stack memory due to recursion.

1. What are real-life applications of the Extended Euclidean Algorithm?

As discussed earlier, Extended Euclidean Algorithm can be used to find the modular multiplicative inverse in O(log(min(a, b))) time. This approach is lightweight, easy to implement, and used to calculate the modular inverse, an essential component in deriving key pairs in the RSA public-key encryption method and various other algorithms.

2. What is Modular Multiplicative Inverse?

The modular multiplicative inverse of a (mod m) is the number x, where ax ≡ 1 mod(p). The modular inverse only exists if a and m are co-prime, i.e., they don't have any common factor other than 1. x is an integer that must also lie in the range [1, p-1] (1 and p-1 inclusive).

3. Can we choose any value for yf as the base case in the above C++ implementation, and it won't affect the outcome in the modular inverse calculation?

Yes, you can choose any value of yf and run the algorithm to calculate the modular inverse. As long as you satisfy the base condition, you can choose any value for the base yf.

4. Are there any alternative methods for calculating the modular inverse?

Instead of using the Extended Euclidean Algorithm, we can apply Fermat's Little Theorem and find the modular inverse. Still, it's only comparable to the Extended Euclidean Algorithm when we find the modular inverse of a (mod b) where b is prime. Otherwise, the time required to calculate the Euler's totient function makes the algorithm slower.

5. I have observed values such as 1000000007 and 998244353 being used in problems commonly. Why?

These values are large prime numbers. Their use can be attributed to the fact that performing any of the basic modular arithmetic operations with them doesn't cause overflow in a 64-bit integer, and them being large primes ensures that one can find the modular multiplicative inverse and other quantities without restrictions for most problems constraints. Choosing them to be large also provides a large range for output.

## Key Takeaways

The article covers the Basic and Extended versions of Euclid's Algorithm. It also explains the working idea behind both of the algorithms. To better understand and apply number theory concepts, check out Number Theory and Modular Arithmetic related blogs that cover all the essential concepts on number theory.