How to determine a possible solution when an equation has multiple unknowns

Question

Suppose we have an equation

$$15 = 5i + 3j + 2k$$

where $i, j, k$ are non-negative integers. It is easy to find some values that make this equation true:

$$i=3, j=0, k=0$$ $$i=0, j=5, k=0$$ $$i=1, j=2, k=2$$ $$...$$

But if we change the equation to be something quite a bit more complex, it becomes much harder to determine if a solution exists. For example, consider the equation $$2038 = 17i + 8j + 7k$$

again where $i, j, k$ are non-negative integers. Is there a way to determine if a solution exists other than by trial and error?

Answer 1

One way of determining is finding the number of solutions in non-negative integers through the use of binomial theorem.

First we find the maximum allowable values of i,j and k .

For example in the equation $15=5i+3j+2k$ . The maximum value of i can be 3 ,similarly maximum values of j and k can be 5 and 7 respectively .

Now the number of solutions of this equations , is equal to the coefficient of $x^{15}$ in $(1+x^5+x^{10}+x^{15})(1+x^3+x^6+\ldots + x^{15})(1+x^2+x^4+\ldots+x^{14})$ .

If when finding the coefficient in this way , the coefficient comes out to be 0 , there are no solutions , otherwise , there are solutions possible .

Answer 2

For a single linear Diophantine equation (we seek nonnegative integer solutions), the simplest approach to feasibility (determining if any solution exists) is likely to put the smallest coefficient term on one side, everything else on the other. For your more complex example:

$$ 7k = 2038 - 17i - 8j $$

Now consider what this says modulo that smallest coeffcient, $7$:

$$ 0 \equiv 1 - 3i - j \bmod 7 $$

We can certainly find nonnegative integers $i,j$ that satisfy this condition, as for example $i=0$ and $j=1$. Moreover choosing smaller values will help us get a nonnegative value for $k$ when we plug $i,j$ back into the original equation (not reduced modulo $7$):

$$ 7k = 2038 - 17\cdot 0 - 8\cdot 1 = 2030 $$

Thus $i=0, j=1, k = 2030/7 = 290$ gives us one solution.

This kind of equation might fail to have nonnegative integers solutions in one of two ways. First, it might have no integer solutions. This would be the case if (and only if) the original coefficients of the integer variables have a greatest common divisor that does not divide the constant term. That is, whatever integer values you assign $i,j,k$, the original right-hand side will be a multiple of their coefficients' GCD, so the left-hand side (constant term) also needs to be a multiple of that GCD (else equality is impossible). Of course, if the constant is divisible by that, we want to go ahead and divide both sides by it, reducing to the case where the GCD is $1$.

Second, the equation might have integer solutions but no nonnegative integer solutions. This possibility is a little tougher to detect. It is closely related to the Frobenius problem. Suppose the coefficients on the right-hand side are values of different coins. We want to know if those denominations can be used get a sum of money represented by the constant term on the left-hand side. Since the number of each type of coin is a nonnegative integer, if it were possible, that would provide the existence of a solution to your equation.

The Frobenius problem asks us to find the largest integer that is a multiple of the coin denominations (coefficients in your equation) that cannot be expressed as a sum of money (solution to your equation). It turns out that there is such a number, and all the positive integers greater than that give equations that can be solved. So in broad terms, the bigger the constant term (relative to the coin denominations/coefficients), the more likely it will be that the equation has a solution.