# Solving linear Diophantine equation

When the first week of the GSoC comes to an end, I was able to finish implementing solver for the linear Diophantine equations. A linear Diophantine equation is an equation of the form,

where and *c* are all integers and are integer variables.

**Case 1: ***n = 2*

*n = 2*

If the linear Diophantine equations has only two variables (*n = 2*), extended Euclid’s algorithm can be used to find the solutions. If solvable, we will have to introduce one parameter. The general form of the equation when* n = 2* can be expressed as *ax + by = c. *This is solvable if and only if gcd(a, b) divides c. i.e *gcd(c, gcd(a, b)) = gcd(a, b)*. Here gcd stands for *greatest common divisor.* Let* x0* and* y0* be a solution, then it can be easily noticed that,* x0 + bt* and *y0 -at* are also solutions. We can use this fact to find all the solutions when an initial solution has been found.

*Solution of 10x + 14y = 10*

We start by dividing both sides of the equation by* gcd(a, b)*. If *gcd(a, b)* does not divide *c*, then there are no solutions.* gcd(4, 6) = 2* and* 2* divides *10* so this is solvable and dividing by 2 yields,* 5x + 7y = 5.* Now we should apply extended Euclid’s algorithm. What the algorithm does is finding three values *x0, y0* and *d* such that *ax0 + by0 = d*. Here *d = gcd(a, b)*. Since we divided the equation by *gcd(a, b)* at the very beginning,* d* will always be *1* in our case. Below is a simplified version of the algorithm used in the solver.

def extended_euclid(a, b):

if b == 0:

return (1, 0, a)

else:

x0, y0, d = extended_euclid(b, a%b)

x, y = y0, x0 – (a//b) * y0

return x, y, d

extended_euclid(5, 7) returns (3, -2 , 1), i.e *5*3 – 7*2 = 1*. Following is the procedure if you were work this out manually.

*7 = 5*1 + 2*

*5 = 2*2 + 1*

*2 = 1*2 + 0*

Now starting from the line before the last one we can start going back, *1 = 5 – 2*2 = 5 – 2*(7 – 5*1) = 3*5 – 2*7* which gives the desired result. Multiplying* 5*3 +7*(-2) = 1 *by *5* we get *5*15 +7*(-10) = 5* which implies that* 15* and* -10* are solutions of the initial equation. So all the solutions can be expressed as*, x = 15+7t, y = -10-5t* where *t* is an integer.

**Case 2:*** n > 2*

*n > 2*

If *n > 2*, we can express two of the variables using the rest of the variables and a parameter. Below is an example for this case.

*Solution of 2x + 3y + 4z = 5*

Let’s set* x = x* and assume* y = ax + bm + c* and* z = dx + em + f* where *a, b, c, d, e, f* are constants to be found. *m* is the introduced parameter. Plug in these in original equation,

*2x + 3(ax + bm + c) + 4(dx + em + f) = 5*

By comparing the two sides we get the set of equations*, 3c + 4f = 5*, * 2 + 3a + 4d = 0* and *3b + 4e = 0* all of which are two variable linear DEs. If these can be solved, these will yield infinite number of solutions and any pair of values will be acceptable for* (a, d), (b, e)* and *(c, f)*. In this example all three equations are solvable and* (a, d) = (2, -2) , (b, e) = (4, -3)* and *(e, f) = (3, -1)* would do the trick. Then the general solution is,* x = x, y = 2x + 4m + 3* and* z = -2x – 3m – 1*

In the solver module when more than two variables are involved it is rearranged leaving two variable in one side and all the other variables and constant term in the other side. For example *2x + 3y + 4z = 5* is assumed to be in the form* 2x + 3y = 5 – 4z*. Then it finds a separate solution for each of the two equations *2x + 3y = 5 –>(1)* and* 2x + 3y = -4z –>(2)*. First equation returns a parametric solution as discussed in case 1 and the solutions for second one can be found by finding a basic solution(not parametric) for* 2x + 3y = -4* and multiplying it by* z. *Adding the two solutions for* (1)* and* (2)* yields the solution of the original equation.

- Posted in: GSoC-2013-SymPy
- Tagged: Diophantine Equations, Linear diophantine Equation, Number Theory

## Recent Comments