7
$\begingroup$

$$ 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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ would the downvoter care to comment? $\endgroup$ – robjohn Feb 11 '15 at 9:34
  • $\begingroup$ 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 */ $\endgroup$ – user3680510 Feb 11 '15 at 10:21
  • 1
    $\begingroup$ @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$ $\endgroup$ – robjohn Feb 11 '15 at 22:04
  • 1
    $\begingroup$ 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. $\endgroup$ – robjohn Feb 12 '15 at 0:47
  • 1
    $\begingroup$ 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$). $\endgroup$ – robjohn Feb 12 '15 at 9:32
1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ @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. $\endgroup$ – Senex Ægypti Parvi Feb 11 '15 at 9:36
  • $\begingroup$ @coffeemath: the final solution: $(x,y,z)=(4-2b-5a,b,3a-1)$ is integral, and that is what is important. $\endgroup$ – robjohn Feb 11 '15 at 10:06
  • $\begingroup$ @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? $\endgroup$ – robjohn Feb 11 '15 at 10:34
  • $\begingroup$ @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. $\endgroup$ – Senex Ægypti Parvi Feb 11 '15 at 13:06
  • $\begingroup$ @Senex Yes, I agree that in the final parametrization all are integers, so the temporary variables don't matter. (Deleting initial comment...) $\endgroup$ – coffeemath Feb 11 '15 at 13:14
0
$\begingroup$

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

$\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.