Solving Linear Diophantine equation

This post would be a sequel. one can find the previous post here.

Before we proceed further we look into a variation, sometimes if the equation looks like this
11*x + 2 = 16 [mod 26] and asks to solve for x, we would just simplify the equation as follows:

11*x = 14 [mod 26]
=> x = (11)^-1 * 14 [mod 26]
Then we proceed as the standard procedure goes, find the (11)^-1 [mod 26] and replace the value in equation and solve for x.

In this post we would see linear Diophantine equation and its solve method using extended euclidean algorithm.

A * x + B * y = 1 ......... [equation having this form is called linear Diophantine Equation]

The condition for having a solution of this equation is GCD(A,B) must be equal to 1.

now suppose we have this equation 47*x + 30*y =1 ........ (first)

as GCD(47,30)=1 , so solution exists.

Now we will follow the same procedure we used for finding modular inverse:

47 = 30*(1) + 17 ...................(1)
30 = 17*(1) + 13 ...................(2)
17 = 13*(1) + 4   ...................(3)
13 = 4*(3) + 1    ....................(4)

form the last equation, solve for remainders,then backwardly substituting values of remainders in the previous equations we get,

17 = 47 + 30*(-1)
13 = 30 + 17*(-1)
4 = 17 + 13*(-1)
1 = 13 + 4*(-3)

now backward....

1 = 13 + [17 + 13*(-1)]*(-3)
   = 13 + 17*(-3) + 13*(3)
   = 13*(4) + 17*(-3)
   = [30 + 17*(-1)]*(4) + 17*(-3)
   = 30 *(4) + 17*(-4) + 17*(-3)
   = 30*(4) + 17*(-7)
   = 30*(4) + [ 47 + 30*(-1)] * (-7)
   = 30*(4) + 47*(-7) + 30*(7)
   = 47*(-7) + 30*(11)

so we get , 47*(-7) + 30*(11)=1
comparing with our primitive equation, x= -7 and y=11 ...

A slight variation: when the right side of our Diophantine equation is not equal to 1

form: A*x + B*y = C

condition of having a solution is GCD(A,B) must be equal to one and
if C % GCD(A,B) is equal to 0 then there exists a solution.

Solution:
1. first solve A*x + B*y = 1
2.then multiply both side by C/GCD(A,B) , this will give us trivial solution.
3. suppose x and y is primary solution got in the step 2, then other solutions can be obtained from these equations for different values of t:
X= x + B/gcd(A,B) * t
Y= y + A/gcd(A,B) *t

Extended Euclidean Algorithm implementation:

typedef pair <int,int>pii;

pii ext_euclid(long long int a,long long int b)
{
    if(a<b)
        return ext_euclid(b,a);
    if(b==0)
        return pii(1,0);
    else
    {
        pii temp= ext_euclid(b,a%b);
        return pii(d.ss, d.ff-d.ss*(a/b));
    }
}

Modular Inverse implementation:

int mod_inverse(int a,int n)
{
     pii ret = ext_euclid(a,n);
return ((ret.ff % n ) + n ) % n;
}