# Solving a special case of linear Diophantine equations with constraints in 3 variables [closed]

I want to solve the following problem:

$$7x+8y+10z=38$$

such that $$x, y$$ and $$z$$ are non-negative integers

and $$x+y+z \le 5$$

Also, if I have a starting solution of $$x=2$$, $$y=3$$, and $$z=0$$, is there any way to generate the other solutions?

• with this small space, it's feasible to go through all possible (x,y,z) tuples and evaluate the function $f(x,y,z)=7x+8y+10z$ with all possible values x,y,z \in [0..5], given that there is only 6*6*6 different alternative parameter combinations. Once you generated the tuples, you need to filter out the tuples which do not satisfy the 2 conditions. – tp1 Jun 10 at 17:57
• Thanks tp1. But I want to understand the solution method so that I can be able to solve large problem of such kind. Evaluating all possible values will work with such small problems but not the large ones. – user321821 Jun 10 at 18:22
• A general algorithm is described in this answer – Bill Dubuque Jun 10 at 21:40

## 1 Answer

$$7x+8y+10z=38\tag{1}$$

An argument $$mod$$ $$2$$ shows that $$x$$ is even, then let $$x=2m.$$

$$7x+8y+10z\equiv 38 \pmod{7} \implies y+3z\equiv 3 \pmod{7}.$$
Hence let $$y = -3z+7n+3.$$

Substitute $$x = 2m$$ and $$y = -3z+7n+3$$ to equation $$(1)$$, then we get $$14m-14z+56n = 14.$$
Hence we get $$z = m+4n-1.$$

Finally, we get $$(x,y,z)=(2m, -3m-5n+6, m+4n-1).$$
$$m,n$$ are integers. $$y$$ is non negative if $$3m+5n \le 6.$$

Thus, solutions corresponding to $$(m,n)=(0,1),(1,0),(2,0)$$ are $$(x,y,z)=(0, 1, 3),(2, 3, 0),(4, 0, 1).\\$$

Another approach:
An argument mod 2 shows that $$x$$ is even, then $$x$$ must be $$0 , 2$$ or $$4.$$

$$\bullet\ \pmb{x=0}:$$

$$7x+8y+10z=38 \implies 8y+10z=38.$$

$$8y+10z\equiv 38 \pmod{5} \implies y\equiv 1 \pmod{5}.$$

Hence we get $$y=1$$ and $$z=3.$$

$$\bullet\ \pmb{x=2}:$$

$$7x+8y+10z=38 \implies 8y+10z=24.$$

$$8y+10z\equiv 24 \pmod{5} \implies y\equiv 3 \pmod{5}.$$

Hence we get $$y=3$$ and $$z=0.$$

$$\bullet\ \pmb{x=4}:$$

$$7x+8y+10z=38 \implies 8y+10z=10.$$

$$8y+10z\equiv 10 \pmod{5} \implies y\equiv 0 \pmod{5}.$$

Hence we get $$y=0$$ and $$z=1.$$

• Thanks Tomita. Is there any way to know if we have a unique solution or no solutions at all? – user321821 Jun 11 at 14:37
• If you're just looking for the solution, the easiest way is brute force search: $0\le(x,y,z)\le5.$ – Tomita Jun 11 at 23:19