Solving linear Diophantine equations in 3 variables

Question

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?

Answer 1

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.)

Answer 2

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.