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,

gcd(30, 50) = 10
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

Practice this problem

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


Download  Run Code

Output:

The GCD is 10
x = 2, y = -1

C++


Download  Run Code

Output:

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

Java


Download  Run Code

Output:

The GCD is 10
x = 2, y = -1

Python


Download  Run Code

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