0
$\begingroup$

I have to solve a linear Diophantine equation in more than 2 variables> I sort of have an idea of how to solve it, but I'm not clear how. One of the problems is this:

$$12x + 21y +9z + 15w = 9$$

How can I go about solving it?

$\endgroup$
  • $\begingroup$ $$4x+7y+3z+5w=3\iff 4x+7y+5w=3(1-z)$$ We can set $x=7t+2,y=-4t-1\implies 1+5w=3(1-z)\iff 5(w-1)=-3(z+1)$ $\implies w=-3u+1,z=5u-1$ $\endgroup$ – lab bhattacharjee Nov 26 '13 at 4:46
  • $\begingroup$ but then from this, i can solve for u, then for w, then z? $\endgroup$ – user98447 Nov 26 '13 at 4:51
  • $\begingroup$ these are the parameterized solutions for $x,y,z,w$ we can choose any value of $t,u$ $\endgroup$ – lab bhattacharjee Nov 26 '13 at 5:10
5
$\begingroup$

It's the same way, you find the gcd of 2 numbers.
Say for the general equation: $ax + by + cz + dw = p$

Step 1: Find $x_0$ and $y_0$ such that $ax_0 + by_0 = \gcd(a,b) = d_1$
Using Euclidean algorithm, (the one we learn in school to find gcd of two numbers)

For example: $\gcd(12,21)=\gcd(12,(21-12=9))= \gcd((12-9=3),9)=3$
$\implies3 = 12-(21-12) = 12\cdot2-21\cdot1\implies$ Required $(x_0,y_0)=(2,-1)$

Step 2 : Now the problem is reduced to $d_1m + cz + dw = p$
i.e., $(m,z,w)$ is a solution $\implies(mx_0, my_0, z, w)$ is also a solution

Step 3 : Now find $(m_0,z_0)$ such that $d_1m_0 + cz_0 = \gcd(d_1,c) =d_2$
Now the problem reduces to $d_2n + dw = p$
Similary find $(n_0,w_0)$ such that $d_2n_0 + dw_0 = \gcd(d_2,d) = g$

Now we have $(x_1,y_1,z_1,w_1)$ such that $ax_1 + by_1 + cz_1 + dw_1 = g$
Also note that $g=\gcd(a,b,c,d)$ and $g$ must divide $p (g|p)$, if not there is no integral solution to the original equation.
$\implies p = gk$ for some $k$ in integer

$\implies (kx_1,ky_1,kz_1,kw_1) $is a solution to the given eqn.

Generating other Solutions:

$(x,y,z,w)$ is a solution, then
$(x + t\cdot bcd, y + t\cdot acd, z - t\cdot abd, z - t\cdot abc)$ are solutions for any integer $t$.
Note this is not an exhaustive list of solutions and we can generate other sets by changing the $\pm$ before $t$ appropriately.

Hope this helps.

$\endgroup$
2
$\begingroup$

You probably know how to write down all solutions to $12x+21y=A$, where $A$ is any integer: there are no solutions unless $\gcd(12,21)=3$ divides $A$. If $3$ divides $A$, then a particular solution is $A/3$ times a particular solution to $12x+21y=3$, which you can take to be $(x,y) = (2,-1)$. Then the general solution must add all solutions to $12x+21y=0$, which are of the form $(7m,-4m)$. Therefore the solutions to $12x+21y=A$ are all of the form $(x,y) = \frac A3(2,-1)+(7m,-4m)$ for all integers $m$, and each such pair is a solution.

To solve the problem at hand, simply take $A=9-9z-15w$, where $z$ and $w$ are any integers. We obtain the general solution $$ (x,y,z,w) = \big( \tfrac{2A}3+7m, -\tfrac A3-4m, z,w \big) = \big( 6-6z-10w+7m, -3+3z+5w-4m, z, w \big) $$ for any integers $z,w,m$.

(There are lots of ways to write down these solutions, which form a three-dimensional lattice. Starting with a different pair in place of $z,y$ would result in the same solution set written in a different way.)

$\endgroup$
  • $\begingroup$ The explanation will be a little clearer if the equation is divided by 3 first. And there is a typo. +4m should be -4m in final value of y. $\endgroup$ – user96614 Nov 26 '13 at 5:44
  • $\begingroup$ thanks for noting the typo. I think dividing by 3 first makes some things clearer but obscures other things (e.g., the role of the gcd of the coefficients). $\endgroup$ – Greg Martin Nov 26 '13 at 8:15
2
$\begingroup$

[Please refer also to the image after the last paragraph. The image is also available in PDF.]

A Guiding Principle

A guiding principle for finding integer solutions to the linear equation or system of linear equations is to express the original variables in terms of parameter variables. In other words, the original variables are in a basic solution.

Definition. A variable is in a basic solution if it has a coefficient of 1 in one and only one equation, and considered a dependent variable.

Definition. A basic variable is a dependent variable in a basic solution. By enumerating integer values for the parameter variables, integer solutions are found for the original variables.

Constraint and Variable Generation Step

One way of generating a parameter variable and corresponding equation to support the main idea would be to find an equation where an original variable is not a basic variable, and generate a new parameter variable and corresponding equation for the equation found. Every coefficient for the new equation is the remainder of the corresponding coefficient in the equation divided by the coefficient of the selected original variable. The right-hand constant for the new equation is the remainder of the right-hand constant in the original equation divided by the coefficient of the selected variable. The new system of equations is the previous equations plus the newly generated equation. After solving the new system of equations, if there is still an original variable that is not expressed as a function of parameter variables only, then repeat the “Constraint and Variable Generation Step”. In other words, if an original variable is not a basic variable, then repeat the “Constraint and Variable Generation Step”.

Stopping Criteria: If every original variable is in the basic solution, stop; a solution has been found. If the latest equation added consists of only one parameter variable, stop. If the parameter variable is an integer then there is a unique integer solution; otherwise, there is no integer solution.

Hints For a linear system of equations with more than one equation, it may be worthwhile to perform substitution in Z to express the linear system in diagonal form: if〖 a〗_ij is a diagonal entry then |a_ij |≥1 and a_hj=0 where h≠i. Then proceed with the Constraint and Variable Generation Step.

A Solution to 12x+21y+9z+15w=9

The solution is presented in two columns. The first column contains all the relevant “computations” or “steps in the proof”. The second column was used to guide in the creation of the rows in the first column by presenting the linear system of equations being created. The substitution process was not included in the presentation but the result of each substitution process for converting a linear system to a diagonal form or basic solution is presented in the second column. In all intermediate cases, the newly appended equation is added on the basic solution of the previous linear system.

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.