Extended Euclidean Algorithm

Here gcd(a, b) = g;

We have a equation, a*x + b*y = gcd(a, b). This algorithm given a, b and gcd(a, b). For this we calculate x and y. Euclidean Algorithm for count gcd(a, b) we can see that the algorithm ends 

when b = 0 and a = g. For this we can write this equation, 

                                                  g * 1 + 0 * 0 = g

If we compare above equation with  a*x + b*y = g,  when b = 0 we can see that x = 1 and y = 0.

Now we see how the coefficients x and y change during the transition from (a, b) to (b, a mod b).

Mind that, 

    when (a, b) change to (b, a mod b) we found coefficients  (x1, y1), so we can write this equation,

                                                  b * x1 + (a mod b) * y1 = g ------------------- (1)

we know that, 

                        reminder = Dividend - ( Divisor * Quotient )

So, (a mod b) we can write as : 

                                                    a mod b = a - (a / b) * b

In equation (1) replace ( a mod b ) and we get,

            

                                g = b*x1 + ( a - (a / b) * b ) * y1

                            

                                g = b*x1 + a*y1 - (a / b)*b*y1

                            

                                g = a*y1 + b * ( x1 - y1*(a /b) )

           

Now we compare this equation with a*x + b*y = g, we can write this,

                                x = y1

                                y = x1 - y1*(a / b)

#include<bits/stdc++.h>

using namespace std;

int ExtendedGcd(int a, int b, int &x, int &y)

{

if(b == 0)

{

x = 1;

y = 0;

return a;

}

int x1, y1;

int d = ExtendedGcd(b, a%b, x1, y1);

x = y1;

y = x1 - y1 * (a/b);

return d;

}

int main()

{

int a, b, x, y;

cout << "Linear Diophantine Equations :: " << "ax+by = gcd(a, b)" << "\n";

cout << "\nEnter a :: ";

cin >> a;

cout << "Enter b :: ";

cin >> b;

int r = ExtendedGcd(a, b, x, y);

cout << "\nX :: " << x << " and Y :: " << y << "\n";

cout << "gcd(" << a << "," << b << ") = " << r << "\n";

return 0;

}