Extended Euclid's Algorithm

What is the Extended Euclid’s algorithm?

The Extended Euclid’s algorithm is used to find the solution of equations of the form Ax + By = C , where C is a multiple of divisor of A and B, or in other words C = gcd(A, B). Extended Euclid’s works in the same manner as the Euclid’s algorithm. Let the equation be Ax + By = 1 (let the solutions of this equation be x’ and y’). We have been given that gcd(A, B) is 1, then the solutions of equation Ax + By = k where k is a multiple of gcd(A, B) are given by k*x’ and k*y’.

Now we can write:

A.x + B.y = gcd(A, B)       ----(1)  

Using the Euclid’s algorithm that we discussed earlier, we know that gcd(A, B) = gcd(B, A % B). Hence, we can write the above equation as:

B.x1 + (A % B).y1 = gcd(B, A % B)

When we put (A % B) = (A - (floor(A/B)).B) in the above equation, we get the following:

B.x1 + (A - floor(A/B).B).y1 = gcd(B, A % B)

The above equation can also be written like this:

B.(x1 - floor(A/B).y1) + A.y1 = gcd     ---(2)

After comparing coefficients of ‘A’ and ‘B’ in (1) and (2), we get the following:

x = y1
y = x1 – floor(A/B).y1

Now, let’s move to the implementation.