# (Diophantine?) Equations With Multiple Variables

A normal linear Diophantine equation would be some: $ax + by = c$ where $a$ and $b$ are constants. Solution can be found using Euclid's Extended Algorithm.

But what about for longer equations such as: $ax + by + cz = d$?

Is there a way to solve these kinds of equations for more than two variables?

It's this question that I've been asking myself. Say that I have some equation:

$aw + bx + cy + dz = e$

Such that $a, b, c, d$ are constants and $w, x, y, z$ are either 0 or 1. I want to be able to show if a solution exists for some $e$.

Of course, there's always the brute force method to solve, but is there anything more elegant?

• Is your question about the general Diophantine equation or the subset sum problem? – Bill Dubuque May 15 '12 at 14:55

The diophantine equation $$ax+by = r$$ can be solved if and only if $$\gcd(a,b)\mid r$$. In that case, the Euclidean algorithm provides an effective way of finding all solutions.

The key to this is that the collection of all possible values of $$ax+by$$ is precisely the set of all multiples of $$\gcd(a,b)$$.

Now consider $$ax+by+cz = t$$. This is equivalent to solving $$\gcd(a,b)w + cz = t$$, since any solution to the latter yields a solution of the former (by suitable choice of $$x$$ and $$y$$ so that $$ax+by = \gcd(a,b)w$$) and conversely, any solution to $$ax+by+cz=t$$ yields a solution to $$\gcd(a,b)w+cz = t$$. Thus, the diophantine equation $$ax+by+cz=t$$ is equivalent to the diophantine equation $$\gcd(a,b)w+cz=t$$, which can be solved if and only if $$\gcd(\gcd(a,b),c) = \gcd(a,b,c)$$ divides $$t$$.

Similar considerations yield that the diophantine equation $$a_1x_1+a_2x_2+\cdots+a_kx_k = d$$ with $$k\gt 0$$ has a solution if and only if $$\gcd(a_1,a_2,\ldots,a_k)$$ divides $$d$$. When it does, the Euclidean algorithm provides an effective way of finding the solutions.