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,

linear where CodeCogsEqn and  c are all integers andCodeCogsEqn(1) are integer variables.

Case 1: 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

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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: