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[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,

    x0 = -1*80 = -80

    y0 = 2*80 = 160

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

    Sponsored

    LEAVE A REPLY

    Please enter your comment!
    Please enter your name here

    Subscribe Today

    GET EXCLUSIVE FULL ACCESS TO PREMIUM CONTENT

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

    Exclusive content

    Latest article

    More article