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;
}

Modular Inverse : Mathematical Approach

Modular Inverse is an important topic in number theory. To understand modular inverse one has to know basics of modular arithmetic or congruence which in this post I will skip. one might find this helpful for the basic . we would discuss a bit(a tiny bit though :P ) advanced thing here.

sometimes we need to find (a/b)% mod . we can simplify this as follows:

(a/b)% mod = ( a% mod * b^-1 % mod) % mod

here b^-1 % mod = modular inverse of b

we can find this modular inverse by extended euclidean algorithm (or also by big mod algorithm using Euler's theorem if mod is prime).Anyway at first let's check how mathematically modular inverse is calculated:

suppose we want to find modular inverse of 27 mod 392.

dividend = divisor (quotient) + remainder
392         =  27*(14)                 + 14 ......................... (1)
27           = 14*(1)                    + 13 ..........................(2)
14           = 13*(1)                    + 1 ............................(3)

every time divisor is becoming dividend and remainder is becoming divisor except in the first step.

Now form the last equation, we would solve for remainders, just doing side changing,

1 = 14 + 13*(-1) ....................(4)
13 = 27 + 14*(-1) ....................(5)
14= 392 + 27*(-14) ....................(6)

we can backwardly substitute values of remainders in the previous equation (4).

1 = 14 + [27 + 14 * (-1)] * (-1) ................. // just replacing values of 13 from equation (5)
=>1= 14 + 27*(-1) + 14(1)
=> 1 = 14*(2) + 27 *(-1)

Now again we can replace the values of 14 from the equation (6) in the same procedure,

1 = [392 + 27*(-14)] * (2) + 27*(-1)
=>1 = 392*(2) + 27*(-28) + 27*(-1)
=>1 =392*(2) + 27*(-29) .................... (7)

we can recall we are calculating modular inverse of 27 mod 392,so if we mod equation (7) by 392
we get,

392%392=0 and -29 % 392= 363

replacing these values in (7)

1= 0 + 27*(363)

=> 27*(363)= 1 (mod 392)

so 27^-1 = 363 (mod 392)


Before advancing to code for calculating the modular inverse one must know the math behind it.