Solving the equation in natural numbers

Question

How can I find the solutions in natural numbers for the following equation?

$$a_{1}x_{1}+a_{2}x_{2}+\cdots +a_{n}x_{n}=b$$

Where $x_{1},...,x_{n}$ are unknown.

I want to find the whole of solutions in algorithmic method.

Answer 1

If you are looking for integer solutions, then integer solutions to the equation exists iff $\gcd(a_1,a_2,\ldots,a_n)$ divides $b$. This is known as generalized Bezout's lemma and solutions can be obtained algorithmically using generalized Euclid's algorithm.

If you are looking for natural number solutions, then obtain the class of infinite solutions using the above method and enforce non-negativity to obtain natural number solutions.

For instance, if you are looking for non-negative integer solutions to $$2x+3y+5z=13$$ we proceed as follows. Since $\gcd(3,5)=1$, set $w=3y+5z$, which gives us $$2x+w = 13$$ A solution is given by $(x,w) = (3,7)$. Hence, all solution are given by $(x,w) = (3+m,7-2m)$. Now let us solve $3y+5z=w = 7-2m$. A solution to this is given by $(y,z) = (-1+m,2-m)$. Hence, all solutions are given by $(y,z) = (-1+m-5n,2-m+3n)$. Hence, all integer solutions are given by $$(x,y,z) = (3+m,-1+m-5n,2-m+3n)$$ Enforcing $x,y,z \geq 0$, we obtain that $m \geq -3$, $-1+m-5n \geq 0$ and $2-m+3n \geq 0$. This gives us $m \geq -3$ and $\dfrac{m-2}3\leq n \leq \dfrac{m-1}5$, which in turn gives us that $5m-10 \leq 3m-3 \implies 2m \leq 7$. Hence, $m \in \{0,\pm1,\pm2,\pm3\}$. Obtain the value of $n$ for each $m$ and hence solve for $x,y,z$. 

Answer 2

@user17762 has the perfect answer for integer numbers. For engineering, you can extend this problem even with $x_{i} \in \mathbb{R}^{N}$ Assume that the problem has $n$ unknown variables, the number of independent equations are $m$, so:

• If $m = n$, the problem is trivial (full rank)
• If $m <n $, the problem is low-rank (NP-hard). You can apply some theories such as convex optimization to solve.