Extended Euclidean Algorithm – C, C++, Java, and Python Implementation
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, i.e., integers x
and y
such that ax + by = gcd(a, b)
.
For example,
Here, x = 2 and y = -1 since 30*2 + 50*-1 = 10
gcd(2740, 1760) = 20
Here, x = 9 and y = -14 since 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 simultaneously calculate the gcd and coefficients of the Bézout’s identity x
and y
at no extra cost.
Following is the implementation of the extended Euclidean algorithm in C, C++, Java, and Python.
C
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#include <stdio.h> // Recursive function to demonstrate the 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; } int main() { int a = 30; int b = 50; int x, y; printf("The GCD is %d\n", extended_gcd(a, b, &x, &y)); printf("x = %d, y = %d", x, y); return 0; } |
Output:
The GCD is 10
x = 2, y = -1
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
#include <iostream> #include <tuple> // std::tuple, std::make_tuple, std::tie using namespace std; // Recursive function to demonstrate the 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); } 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 << "The GCD is " << gcd << endl; cout << "x = " << x << " y = " << y << endl; cout << a << "*" << x << " + " << b << "*" << y << " = " << gcd << endl; return 0; } |
Output:
The GCD is 10
x = 2 y = -1
30*2 + 50*-1 = 10
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
import java.util.concurrent.atomic.AtomicInteger; class Main { // Recursive function to demonstrate the extended Euclidean algorithm. // It uses pointers to return multiple values. public static int extended_gcd(int a, int b, AtomicInteger x, AtomicInteger y) { if (a == 0) { x.set(0); y.set(1); return b; } AtomicInteger _x = new AtomicInteger(), _y = new AtomicInteger(); int gcd = extended_gcd(b % a, a, _x, _y); x.set(_y.get() - (b/a) * _x.get()); y.set(_x.get()); return gcd; } public static void main(String[] args) { int a = 30; int b = 50; AtomicInteger x = new AtomicInteger(), y = new AtomicInteger(); System.out.println("The GCD is " + extended_gcd(a, b, x, y)); System.out.printf("x = %d, y = %d\n", x.get(), y.get()); } } |
Output:
The GCD is 10
x = 2, y = -1
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
# Python program for the extended Euclidean algorithm def extended_gcd(a, b): if a == 0: return b, 0, 1 else: gcd, x, y = extended_gcd(b % a, a) return gcd, y - (b // a) * x, x if __name__ == '__main__': gcd, x, y = extended_gcd(30, 50) print('The GCD is', gcd) print(f'x = {x}, y = {y}') |
Output:
The GCD is 10
x = 2, y = -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 the RSA public-key encryption algorithm.
References: https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)