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 = gk₁

b = gk₂

(Where k₁ and k₂ are some constants)

Putting the above values in the given equation,

gk₁x + gk₂y = c

k₁x + k₂y = 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 (x⁰, y⁰).

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)

x⁰ = kx’

y⁰ = 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[0];
	int smallY = result[1]; 
	int gcd  = result[2];

	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[0] <<" and "<<result[1] << " gcd " << result[2] << endl;


	return 0;
}

---

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

Let us consider the above example equation,

25x + 15y = 400

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

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

The final answer would be,

x⁰ = -1*80 = -80

y⁰ = 2*80 = 160

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