Extended Euclidean algorithm Implementation in C, C++ and Python

The extended Euclidean algorithm is an extension to the Euclidean algorithm, which computes, besides the greatest common divisor of integers a and b, the coefficients of Bézout’s identity, that is integers x and y such that

ax + by = gcd(a,b)

For example,

gcd(30, 50) = 10
Here x = 2 y = -1 as 30*2 + 50*-1 = 10

gcd(2740, 1760) = 20
Here, x = 9 y = -14 as 2740*9 + 1760*-14 = 20

The gcd is the only number that can simultaneously satisfy this equation and divide the inputs. The extended Euclid’s algorithm will allows us to simultaneously calculate the gcd and coefficients of the Bézout’s identity x and y at no extra cost.

Following is the implementation of Extended Euclidean algorithm in C, C++ and Python.

C

#include<stdio.h>

// Function for Extended Euclidean algorithm
// It uses pointers to return multiple values
int extended_gcd(int a, int b, int *x, int *y)
{
	if (a == 0)
	{
		*x = 0;
		*y = 1;
		return b;
	}

	int _x, _y;
	int gcd = extended_gcd(b % a, a, &_x, &_y);

	*x = _y - (b/a) * _x;
	*y = _x;

	return gcd;
}

// main function
int main()
{
	int a = 30;
	int b = 50;

	int x, y;

	printf("GCD is %d\n", extended_gcd(a, b, &x, &y));
	printf("x = %d, y = %d", x, y);

	return 0;
}

#include<stdio.h>

// Function for Extended Euclidean algorithm

// It uses pointers to return multiple values

int extended_gcd(int a, int b, int *x, int *y)

{

if (a == 0)

{

*x = 0;

*y = 1;

return b;

}

int _x, _y;

int gcd = extended_gcd(b % a, a, &_x, &_y);

*x = _y - (b/a) * _x;

*y = _x;

return gcd;

}

// main function

int main()

{

int a = 30;

int b = 50;

int x, y;

printf("GCD is %d\n", extended_gcd(a, b, &x, &y));

printf("x = %d, y = %d", x, y);

return 0;

}

Download Run Code

Output:

GCD is 10
x = 2, y = -1

C++

#include <iostream>
#include <tuple>		// std::tuple, std::make_tuple, std::tie
using namespace std;

// Function for Extended Euclidean algorithm
// It returns multiple values using tuple in C++
tuple<int, int, int> extended_gcd(int a, int b)
{
	if (a == 0)
		return make_tuple(b, 0, 1);

	int gcd, x, y;

	// unpack tuple  returned by function into variables
	tie(gcd, x, y) = extended_gcd(b % a, a);

	return make_tuple(gcd, (y - (b/a) * x), x);
}

// main function
int main()
{
	int a = 30;
	int b = 50;

	tuple<int, int, int> t = extended_gcd(a, b);
	
	int gcd = get<0>(t);
	int x = get<1>(t);
	int y = get<2>(t);
	
	cout << "GCD is " << gcd << endl;
	cout << "x = " << x << " y = " << y << endl;

	cout << a << "*" << x << " + " << b << "*" << y << " = " << gcd;

	return 0;
}

#include <iostream>

#include <tuple> // std::tuple, std::make_tuple, std::tie

using namespace std;

// Function for Extended Euclidean algorithm

// It returns multiple values using tuple in C++

tuple<int, int, int> extended_gcd(int a, int b)

{

if (a == 0)

return make_tuple(b, 0, 1);

int gcd, x, y;

// unpack tuple returned by function into variables

tie(gcd, x, y) = extended_gcd(b % a, a);

return make_tuple(gcd, (y - (b/a) * x), x);

}

// main function

int main()

{

int a = 30;

int b = 50;

tuple<int, int, int> t = extended_gcd(a, b);

int gcd = get<0>(t);

int x = get<1>(t);

int y = get<2>(t);

cout << "GCD is " << gcd << endl;

cout << "x = " << x << " y = " << y << endl;

cout << a << "*" << x << " + " << b << "*" << y << " = " << gcd;

return 0;

}

Download Run Code

Output:

GCD is 10
x = 2 y = -1
30*2 + 50*-1 = 10

Python

#Python program for Extended Euclidean algorithm
def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		gcd, x, y = egcd(b % a, a)
		return (gcd, y - (b/a) * x, x)

gcd, x, y = egcd(30, 50)
print gcd, x, y

#Python program for Extended Euclidean algorithm

def egcd(a, b):

if a == 0:

return (b, 0, 1)

else:

gcd, x, y = egcd(b % a, a)

return (gcd, y - (b/a) * x, x)

gcd, x, y = egcd(30, 50)

print gcd, x, y

Download Run Code

Output:

10 2 -1

The extended Euclidean algorithm is particularly useful when a and b are co-prime, since x is the modular multiplicative inverse of a modulo b, and y is the modular multiplicative inverse of b modulo a. Both extended Euclidean algorithms are widely used in cryptography. The computation of the modular multiplicative inverse is an essential step in RSA public-key encryption algorithm.

References: https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

1 Star 2 Stars 3 Stars 4 Stars 5 Stars (2 votes, average: 5.00 out of 5)

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

C

C++

Python

Sharing is caring:

Leave a Reply