2
$\begingroup$

This question has two parts.

Part $1$:

I've been learning how to solve Linear Diophantine Equations (LDE) in 3 variables and so far, I've encountered two methods:

Method $1$:

Problem: Find positive integral solutions of $7x+11y+26z=123.$

Solution: The greatest coefficient is $26$ and $7+11+26z\leq 123,$ hence $z\leq 4.$ Therefore the only possibilities are: $$z=1, 7x+11y=97,\text{ of which there is one solution }(6,5),$$ $$z=2, 7x+11y=71,\text{ of which there is one solution }(7,2),$$ $$z=3, 7x+11y=45,\text{ of which there is no solution},$$ $$z=4, 7x+11y=45,\text{ of which there is no solution}.$$ Thus there are two solutions in positive integers, namely $(6,5,1)$ and $(7,2,2)$.

Method $2$:

Problem: Determine integral solutions of $3x+4y+5z=6.$

Solution: We have $3x+4y\equiv 1 \pmod 5;$ hence $3x+4y=1+5s$ for some integer $s.$ Observe that $x=-1+3s, y=1-s$ satisfies this equation and therefore a general solution is $x=-1+3s+4t,y=1-s-3t$ for some $t.$ Substituting these values in original equation we get $z=1-s.$

Doubts regarding the above methods:

  1. Is Method $1$ a general way to solve LDEs in 3 variables or is it just a trick? Moreover, I noticed that it does not help one to solve the second LDE since $3+4+5z\leq 6\Rightarrow z\leq -0.2$ which basically means that we have no value of positive $z$ satisfying the equation. Does that mean that the second LDE does not have any positive integral solutions?
  2. How can we impose integral bounds on the parameters $s$ and $t$, if we want to obtain positive solutions? I tried to do the following: $$x\geq 0\Rightarrow -1+3s+4t\geq 0\Rightarrow 3s+4t\geq 1$$ $$y\geq 0\Rightarrow 1-s-3t\geq 0\Rightarrow s+3t\leq 1$$ $$z\geq 0\Rightarrow 1-s\geq 0\Rightarrow s\leq 1$$ Beyond this, I could not deduce anything meaningful.

Part $2$:

After having learned about the solvability of such equations, a natural question that comes to one's mind is: how many positive integral solutions does an LDE in three variables admit, for a given output. So suppose we have an LDE in three variables $$ax+by+cz=n,\text{ where }\gcd(a,b,c)|n$$ then how many triples $(x,y,z)$ exists such that $x,y,z\geq 0?$ I guess this is related to the last question in Part $1$ because if we can bound the parameters then we can simply get the number of solutions by counting the values satisfied by $s$ and $t$.

$\endgroup$
2
$\begingroup$

Method 1) is not a trick: it is the projection of the equation plane onto a 2D plane. To do that efficiently, you choose the variable (suppose $z$) with the highest coefficient, assign each possible value to it, and project it as line onto the plane of the remaining variables ($x,y$).
To determine the range of possible values for $z$, since you are requiring positive solutions (thus excluding the $0$) , you assign $1$ (the lowest) to $x$ and $y$ and then you get an inequality as in the example you gave.

Applying this method to the second example ($3x+4y+5z=6$) you correctly deduce that the possible range for $z$ is empty, since there are no positive solutions to this equation.

To my knowledge, unfortunately there is not a general "formula" to solve 3D LDE (not a simple one at least), and also algorithms to calculate them become computationally heavy for large coefficients.

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