# Extended Euclid Algorithm to find GCD and Bézout's coefficients

We will see how to use Extended Euclid's Algorithm to find GCD of two numbers. It also gives us Bézout's coefficients (x, y) such that ax + by = gcd(a, b). We will discuss and implement all of the above problems in Python and C++

February 4, 2017 - 8 minute read -

## What is Euclid’s Algorithm?

Euclid’s Algorithm is an efficient method to find GCD of two numbers. In one of the previous posts, we discussed how to find GCD of two numbers using Euclid’s Algorithm.

A simple C++ code to find GCD using Euclid’s Algorithm is as follows:

## What is Extended Euclid’s Algorithm?

As the name suggests, Extended Euclid’s Algorithm is an extension of Euclid’s Algorithm to find GCD of two numbers. Along with GCD of two numbers, say `a` and `b`, it also finds `x` and `y` such that `ax + by = gcd(a, b)`. Here, `x` and `y` are known as Bézout’s coefficients.

But why should we learn Extended Euclid’s Algorithm if we can find GCD of two numbers using simple Euclid’s Algorithm? Extended Euclid’s Algorithm1 is particularly useful when we have to find Modular Multiplicative Inverse of a number A in the range M, where A and M are co-prime numbers and M is not necessarily a prime number. If M is a prime number then there’s a very easy method to find Multiplicative Inverse using Fast Power Algorithm.

## C++ Code to find GCD using Extended Euclid’s Algorithm

Simulation of one of the sample test cases 95642 and 1681:

quotient remainder s t
95642/1681 = 56 95642 - 56*1681 = 1506 1 - 56*0 = 1 0 - 56*1 = -56
1681/1506 = 1 1681 - 1*1506 = 175 0 - 1*1 = -1 1 - 1*-56 = 57
1506/175 = 8 1506 - 8*175 = 106 1 - 8*-1 = 9 -56 - 8*57 = -512
175/106 = 1 175 - 1*106 = 69 -1 - 1*9 = -10 57 - 1*-512 = 569
106/69 = 1 106 - 1*69 = 37 9 - 1*-10 = 19 -512 - 1*569 = -1081
69/37 = 1 69 - 1*37 = 32 -10 - 1*19 = -29 569 - 1*-1081 = 1650
37/32 = 1 37 - 1*32 = 5 19 - 1*-29 = 48 -1081 - 1*1650 = -2731
32/5 = 6 32 - 6*5 = 2 -29 - 6*48 = -317 1650 - 6*-2731 = 18036
5/2 = 2 5 - 2*2 = 1 48 - 2*-317 = 682 -2731 - 2*18036 = -38803
2/1 = 2 2 - 2*1 = 0 -317 - 2*682 = -1681 18036 - 2*-38803 = 95642

References:

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

Got a burning question you wanna get answered? Ask it in the comments.