More
AlgorithmsLinear Diophantine Equation Using Extended Euclidean Algorithm

# Linear Diophantine Equation Using Extended Euclidean Algorithm

An example of Linear Diophantine equation is 25x + 15y = 400

We are given with just a single equation and we need to find an integral solution for x and y (If it exists).

What is Diophantine Equation:

Polynomial equation in two or more unknows, such that only integral solution are required.

Problem Statement:

Given 3 integers of the form ax + by = c. Determine the equation has a solution such that x and y are both integral solutions.

Solution:

ax + by = c

Let,

gcd(a, b) = g

Since g is multiple of a and b, so we can write,

a = gk1

b = gk2

(Where k1 and k2 are some constants)

Putting the above values in the given equation,

gk1x + gk2y = c

k1x + k2y = c/g

The integral solution of the above equation exists only when c is divisible by g, i.e.,

Iff (c%g == 0)

Thus,

We can write the given equation as,

ax + by = k*gcd(a, b)

(Where k is some constant)

Since, c is a multiple of g, we can multiply g with any constant k to get c.

Let the above equation have a solution (x0, y0).

We know that the solution of the equation [ax + by = gcd(a, b)] can be solved the Extended Euclidian’s algorithm.

Let us consider that the equation has a solution (x’, y’) which satisfies the equation ax’ + by’ = gcd(a, b)

We can convert the above equation to the equation given in the problem by multiplying it with some constant k.

a(x’k) + b(y’k) = k*gcd(a, b)

x0 = kx’

y0 = ky’

Here, k = c / (gcd(a, b))

We can compute the value of x’ and y’ using the Extended Euclid Algorithm where the equation is solved using the child equations, where the answer to parent equation is dependent on its child equation’s answer.

``````//In C++
#include<iostream>
#include<vector>
using namespace std;

//Euclid's Algorithm
int gcd(int a,int b){
if(b==0){
return a;
}
return gcd(b, a%b);
}

// Extended Euclid's Algorithm ax + by = gcd(a,b)
vector<int> extendedGCD(int a,int b){

if(b==0){
//return the values of x and y
return {1,0,a};
}
vector<int> result = extendedGCD(b, a%b);

// After recursive call is over
int smallX = result;
int smallY = result;
int gcd  = result;

int x = smallY;
int y = smallX - (a/b)*smallY;

return {x,y, gcd};
}

int main(){

int a,b;
cin>>a>>b;

// a x + b y = gcd (a,b);
int x,y;
vector<int> result = extendedGCD(a,b);
cout<< result <<" and "<<result << " gcd " << result << endl;

return 0;
}``````

The output of the above code will print result, that is the value of x’, and result, that is the value of y’, and result that is the value of gcd(a, b).

Let us consider the above example equation,

25x + 15y = 400

The value of result is -1 (i.e., x’), result = 2 (i.e., y’), result = 5 (i.e., gcd(25, 15)).

Now, the value of k is 400/5, i.e., 80.

x0 = -1*80 = -80

y0 = 2*80 = 160

Hence, the final answer to the above problem would be -80 and 160 respectively. Subscribe Today

Get unlimited access to our EXCLUSIVE Content and our archive of subscriber stories.