Linear Diophantine equation with three variables and a condition

Question

Let me start by saying that I'm new to Diophantine equations and my method certainly will not be the best possible one. I'm aware that a faster method of solving this particular case exists, but I want to know if what I did was correct and how I can finish the exercise.

$$39x + 55y + 70z = 3274$$ $$ x+y+z=69$$ $$x \ge 0, y \ge 0, z \ge 0$$

What I tried:

$$39x+55y=3274 - 70z$$

The GCD for 39 and 55 is one, so we can set aside $z=t$ to be a parameter, where $t$ is an integer. We proceed to solve this as a Diophantine equation with two variables.

I now need to use the extended Euclidean algorithm to express $1$ as a linear combination of $39$ and $55$.

I got that $1 = 24 \cdot 39 - 17 \cdot 55$

Now, the solution would be

$$x=78576 - 1680t + 55s$$ $$y=-55658 + 1190t - 39s$$ $$z=t$$

where $t$ and $s$ are integers. I got this from the formula that $x = \lambda_1 \cdot b + s \cdot a_2$ and $y = \lambda_2 \cdot b - s \cdot a_1$

Where $\lambda_1$ and $\lambda_2$ are the coefficients in the Euclidean algorithm, $b$ is $3274 - 70t$ and $a_1$ and $a_2$ are $39$ and $55$, respectively.

It's obvious that $t \ge 0$, and if I put that $x$ and $y$ are greater than zero, I get that

$$s \ge \frac{1680t-78576}{55}$$

and $$ s \le \frac{-55658+1190t}{39}$$

which makes $$ \frac{1680t-78576}{55} \le \frac{-55658+1190t}{39}$$

which is $$t \le 46.77$$

I now have the whole range of integers $[0, 46]$ which of course isn't feasible to do (as I'd have to plug them into the inequalities for $s$ and get even more cases.

How do I proceed from here? What do I do? I still have the condition $x+y+z=69$ but I feel like I'm missing something. Can it be really done this way, except that it's an unimaginably hefty job of testing each case?

Answer 1

The condition $x+y+z=69$ tells you that $$z=69-x-y.\tag{1}$$ The condition that $z\geq0$ is then equivalent to $x+y\leq69$.

Plug $(1)$ into your first equation to get $$3274=39x+55y+70(69-x-y)=-31x-15y+4830,$$ or equivalently $$31x+15y=1556,$$ with the conditions that $x,y\geq0$ and $x+y\leq69$.

Next note that reducing modulo $15$ and $31$ shows that \begin{eqnarray*} x&\equiv&11\pmod{15},\\ y&\equiv&19\pmod{31}, \end{eqnarray*} so $y\in\{19,50\}$ and $x\in\{11,26,41\}$. A quick check then shows that $(x,y)=(41,19)$ is the unique solution.

Answer 2

Since $x+y+z = 69$,

$39x+39y+39z=2691$.

Then $39x+55y+70z-(39x+39y+39z)=3274-2691=583$

One ends up with $16y+31z = 583$ whose general solution is well known by the theory of linear diophantine equations in two variables, and much more restricted by the positive requirement.

In this case, look at the equation$\mod {31}$ to make a further reduction to $16y \equiv 25 \pmod {31}$ which has the unique solution $y=19$ in the least residue system and note that outside of that there are no more as any larger solution gives $16y>583$.

The unique solution is forced from $y = 19$ and is $(41,19,9)$.