# Linear Diophantine Equations in Three Variables

$$3x+6y+5z=7$$ The general solution to this linear Diophantine equation is as described here (Page 7-8) is:

$$x = 5k+2l+14$$ $$y = -l$$ $$z = -7-k$$ $$k,l \in \mathbb{Z}$$

If I plug the original equation into Wolframalpha the solution is: $$y = 5n+2x+2$$ $$z =-6n-3x-1$$ $$n \in \mathbb{Z}$$

I can rewrite this as:

$$x = l$$ $$y = 5k+2l+2$$ $$z = -6k-3l-1$$ $$k,l \in \mathbb{Z}$$

However now two equations depend on two variables ($k,l$) and one on one variable $l$. In the first solution one equation depends on two variables and two on one variable.

Questions:

How can I come from a representation like the one from wolfram alpha for the general solution to one where all equations depend on one distinct variable except one equation.

Is there always such a representation?

## 3 Answers

One way to solve this is to note that $(3,6)=3$ and solve, for $w=x+2y$, $$3w+5z=7\tag{1}$$ Using the Extended Euclidean Algorithm as implemented in this answer $$\begin{array}{r} &&1&1&2\\\hline 1&0&1&-1&3\\ 0&1&-1&2&-5\\ 5&3&2&1&0\\ \end{array}\tag{2}$$ Thus, the second to last column gives a particular solution: $$3(2)+5(-1)=1\stackrel{\times7}{\implies}3(14)+5(-7)=7\tag{3}$$ and the last column gives the homogenous solution, which we add to get the general solution: $$3(\overbrace{14-5k}^w)+5(\overbrace{-7+3k}^z)=7\tag{4}$$ Now, we solve for $w=1x+2y=14-5k$ in the same manner we got from $(1)$ to $(4)$: $$1(\overbrace{14-5k+2j}^x)+2(\overbrace{0-j}^y)=\overbrace{14-5k}^w\tag{5}$$ Multiply $(5)$ by $3$ and plug into $(4)$: $$3(\overbrace{14-5k+2j}^x)+6(\overbrace{-j}^y)+5(\overbrace{-7+3k}^z)=7\tag{6}$$

Other answers will come from a reversible change of variables. The answer in $(6)$ is $$\begin{bmatrix} x\\ y\\ z \end{bmatrix} = \color{#C000FF} {\begin{bmatrix} 14&2&-5\\ 0&-1&0\\ -7&0&3 \end{bmatrix}} \begin{bmatrix} 1\\ j'\\ k' \end{bmatrix}\tag{7}$$ The first "solution" above does not work (mapping $l\leftrightarrow j$): \begin{align} 3x+6y+5z &=3(5k+2j+14)+6(-j)+5(-7-k)\\ &=7+10k\tag{8} \end{align}

If we change $z$ to $-7-3k$, the first solution above is \begin{align} \begin{bmatrix} x\\ y\\ z \end{bmatrix} &= \begin{bmatrix} 14&2&5\\ 0&-1&0\\ -7&0&-3 \end{bmatrix} \begin{bmatrix} 1\\ j\\ k \end{bmatrix}\\ &= \color{#C000FF} {\begin{bmatrix} 14&2&-5\\ 0&-1&0\\ -7&0&3 \end{bmatrix}} \begin{bmatrix} 1&0&0\\ 0&1&0\\ 0&0&-1 \end{bmatrix} \begin{bmatrix} 1\\ j\\ k \end{bmatrix}\tag{9} \end{align} which is the solution in $(6)$ under the reversible change $(j,k)=(j',-k')$.

The solution from Wolfram Alpha is \begin{align} \begin{bmatrix} x\\ y\\ z \end{bmatrix} &= \begin{bmatrix} 0&1&0\\ 2&2&5\\ -1&-3&-6 \end{bmatrix} \begin{bmatrix} 1\\ j\\ k \end{bmatrix}\\ &= \color{#C000FF} {\begin{bmatrix} 14&2&-5\\ 0&-1&0\\ -7&0&3 \end{bmatrix}} \begin{bmatrix} 1&0&0\\ -2&-2&-5\\ 2&-1&-2 \end{bmatrix} \begin{bmatrix} 1\\ j\\ k \end{bmatrix}\tag{10} \end{align} which is the solution in $(6)$ under the change $(j',k')=(-2-2j-5k,2-j-2k)$ and since $$\begin{bmatrix} 1&0&0\\ -2&-2&-5\\ 2&-1&-2 \end{bmatrix}^{-1} = \begin{bmatrix} 1&0&0\\ 14&2&-5\\ -6&-1&2 \end{bmatrix}\tag{11}$$ the change of variables is reversible: $(j,k)=(14+2j'-5k',-6-j'+2k')$.

• would the downvoter care to comment? – robjohn Feb 11 '15 at 9:34
• So to preserve the correct solution i can modify the solution matrix by multiplication with a invertible matrix! So i can use Gauß algorithm to come from one representation to the desired one! /* I'm an upvoter */ – user3680510 Feb 11 '15 at 10:21
• @user3680510: You only have two variables to play with. If you want to map two variables to two variables, You cannot alter the $1$ in $\begin{bmatrix}1\\j\\k\end{bmatrix}$. This is the only way to keep the transformation from $\mathbb{Z}^2\to\mathbb{Z}^2$ invertible. Your transformation matrix gives the transform $$\begin{bmatrix}1&-1&0\\0&1&0\\0&0&1\end{bmatrix} \begin{bmatrix}1\\j\\k\end{bmatrix} =\begin{bmatrix}1\\j'\\k'\end{bmatrix}$$ which forces $j=0$ – robjohn Feb 11 '15 at 22:04
• I can simplify it to $$\begin{bmatrix}61&151&167\end{bmatrix} \begin{bmatrix}46&-151&-77\\55&61&30\\0&0&1\end{bmatrix} \begin{bmatrix}1\\j\\k\end{bmatrix} =11111$$ but I see no reason why we should be able to reduce it to one variable per equation. – robjohn Feb 12 '15 at 0:47
• You can get from yours to mine with $$\begin{bmatrix}-411107&-119&-3\\55555&16&-1\\99999&29&2 \end{bmatrix} \begin{bmatrix}1&0&0\\-3459&2&1\\156&-29&-14 \end{bmatrix} =\begin{bmatrix}46&-151&-77\\55&61&30\\0&0&1\end{bmatrix}$$ I think it is possible in the other case since one of the coefficients ($6$) is a multiple of another ($3$). – robjohn Feb 12 '15 at 9:32

1142388    $3x+6y+5z=7$
$3x=7-6y-5z$
$x=\frac{7-6y-5z}3=2-2y-2z+\frac{1+z}3$
New variable $a=\frac{1+z}3$
$y$ had no fractional residue,
so set $y=b$, another new variable.
$z=3a-1$
$x=\frac{7-6b-5(3a-1)}3=4-2b-5a$
Is ${3(4-2b-5a)+6b+5(3a-1)}=7$
true?

• @coffeemath \\ We start off under the supposition that the $x$, $y$ and $z$ are integers. We then reärrange to come up with an expression for $x$. Still dealing with integers, right? We then separate an obviously integral expression [2-2y-2z] from a not-so-obvious one. Even though it's not-so-obvious that it is an integer, it still must be. – Senex Ægypti Parvi Feb 11 '15 at 9:36
• @coffeemath: the final solution: $(x,y,z)=(4-2b-5a,b,3a-1)$ is integral, and that is what is important. – robjohn Feb 11 '15 at 10:06
• @SenexÆgyptiParvi: part of the question is to explain how the different solutions (W|A and the OP's in particular) are related. Did you have ideas about that? – robjohn Feb 11 '15 at 10:34
• @robjohn \\ One could substitute, say, $a+17$ and $b-29$ for $a$ and $b$, respectively. The result of doing so would be equally valid; the magnitudes of the constant parts of the expressions for $x$, $y$ and $z$ would be larger, of course. I consider as canonical the "version" that minimizes those magnitudes. That's it for my ideas, robjohn. – Senex Ægypti Parvi Feb 11 '15 at 13:06
• @Senex Yes, I agree that in the final parametrization all are integers, so the temporary variables don't matter. (Deleting initial comment...) – coffeemath Feb 11 '15 at 13:14

A general method, consists in put the matrix $\begin{bmatrix}3&6&5\end{bmatrix}$ in Smith normal form: $$\begin{bmatrix}3&6&5\end{bmatrix}=\begin{bmatrix}1&0&0\end{bmatrix}\begin{bmatrix}3&6&5\\1&2&2\\0&1&0\end{bmatrix}.$$

A solution of the equation $3x+6y+5z=7$ is clearly $(x,y,z)=(0,7,-7)$. Clearly, a triple $(x,y,z)$ satisfies $3x+6y+5z=0$ if and only if: $$\begin{bmatrix}x\\y\\z\end{bmatrix}=\begin{bmatrix}3&6&5\\1&2&2\\0&1&0\end{bmatrix}^{-1}\begin{bmatrix}0\\k\\l\end{bmatrix}=\begin{bmatrix}2&-5&-2\\0&0&1\\-1&3&0\end{bmatrix}\begin{bmatrix}0\\k\\l\end{bmatrix}=\begin{bmatrix}-5k-2l\\l\\3k\end{bmatrix},$$

Thus, the set of all solutions of $3x+6y+5z=7$ are the triples of the form: $$(x,y,z)=(-5k-2l,7+l,-7+3k),$$ that's: $$\left\{\begin{matrix}x=-5k-2l\\y=7+l\\z=-7+3k\end{matrix}\right.$$