Extended Euclid: Solving Linear Diophantine Equation

Motivating Problem: Suppose, you are at the invisible cafeteria of CUET. In cafeteria, each cup of tea and coffee cost a and b taka respectively. You can buy any non-negative integer number cups of tea and coffee. If you have c taka, find out if it is possible to buy some cups of tea and coffee spending exactly c taka. We can model this problem like: ax+by=c.


Greatest Common Divisor(GCD): d is the greatest common divisor of integers a and b, if d is the largest integer which is a common divisor of both a and b.

Euclidian Algorithm to find GCD: To find gcd of a and b where b<a;
>>Divide a by b and let r1 is the remainder.
>>Divide b by r1 and let r2 is the remainder.
>>Divide r1 by r2 and let r3 is the remainder.
Continue to divide the divisor by the remainder in this way until you get a remainder of zero.
gcd(a,b)=the last nonzero remainder.

Let's see the procedure with an example: gcd(600,136)=?
b=q*a+r   and 0<=r<a
600=4*136+56
136=2*56+24
56=2*24+8
24=3*8+0
Here, 8 is the last nonzero remainder.So gcd(600,136)=8.simple,isn't it?

Solving Linear Diophantine Equation:
A Diophantine Equation is any equation for which you are interested only in the integer solution to the equation.

A Linear Diophantine Equation is any linear equation ax+by=c with integer coefficients for which you are interested only in finding integer solution.

Theorem-1: For any nonzero integers a and b, there exist integers x* and y* such that:
                                       gcd(a,b)=ax*+by*
Theorem-1: If gcd(a,b)|c, the Diophantine Equation ax+by=c has at least a solution.

Now, Let's take an example to solve 172x+20y=1000.
Here, gcd(20,172)=4=d

>>Use Eucledian algorithm to find x* and y* such that: ax*+by*=d.
b=aq+r                           so r=b-aq
172=8*20+12                 12=172-8*20............(i)
20=1*12+8                       8=20-1*12..............(ii)
12=1*8+4                         4=12-1*8................(ii)
8=2*4+0

Now, using equation (i),(ii) and(iii):
4=12-1*8    Equation (iii)
4=12-1*(20-1*12) using equation (ii)
4=2*12-1*20 simplification
4=2*(172-8*20)-1*20  using equation(i)
4=2*172+(-17)*20      simplication

So, x*=2 and y*=-17
>>Now, find p such that c=dp. where d is the gcd(a,b)=4 and p is any integer.
so, 1000=4*250

>>Then, xnot=x*p and ynot=y*p are a particular solution
1000=4*250
1000=[2*172+(-17)*20]*250
1000=172*500+20*(-4250)
So, a particular solution is: xnot=500 and ynot=-4250

Theorem-3: If the linear Diophantine equation ax+by=c does have a solution, then all such solution are given by x=xnot+(b/d)t and y=ynot-(a/d)t. Where d is gcd(a,b) and xnot and ynot are the particular solutions to the equation and t ranges over the integers.

So, the solutions(in integer) for our equation are:
x=500+5t.  and y=-4250-43t.
where t ranges over the integers.

>>Now, find all the positive solutions to the Diophantine equation 172x+20y=1000.

In such case, we need to find all the values of t such that:
x=500+5t>0 and y=-4250-43t>0
    t>-100      and t<-98.84
since t must be an integer, so t<=99, so t ranges over: -100<t<=99
so, t=-99 and there is only one positive solution,that is:
x=500+5*(-99)=5
y=-4250-43*(-99)=7.

Sample Code:

	#include<bits/stdc++.h>
	using namespace std;
	int x,y,d;
	void extendedEuclid(int a, int b)
	{
	if (b == 0)
	{
	x = 1;
	y = 0;
	d = a;
	return;
	}
	extendedEuclid(b,a%b);
	int x1 = y;
	int y1 = x-(a/b)*y;
	x = x1;
	y = y1;
	}
	int main()
	{
	int a,b,c,tt1,tt2;
	cin>>c>>a>>b; //ax+by=c
	extendedEuclid(a,b);
	if(c%d!=0) {cout<<"No integral solution"<<endl;return 0;} //if gcd(a,b) doesn't divide constant c.then their is no solution
	//cout<<x<<' '<<y<<endl;
	int p=(c/d);
	int xnot=x*p;
	int ynot=y*p;
	//cout<<xnot<<' '<<ynot<<endl; //this is the particular solution
	double t1=((floor)(-xnot)*d)/((floor)(b));
	double t2=((floor)(ynot*d)/(floor)(a));
	if(t1<0) tt1=floor(t1);
	else tt1=ceil(t1);
	if(t1<0) tt2=floor(t2);
	else tt2=ceil(t2);
	cout<<tt1<<" "<<tt2<<endl; //for any integer between tt1 and tt2,the solution will be positive
	int t=tt2;
	x=xnot+(b/d)*t;
	y=ynot-(a/d)*t;
	cout<<x<<' '<<y<<endl;
	return 0;
	}

view raw diophantine.cpp hosted with ❤ by GitHub

Problems: