16
$\begingroup$

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?

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

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.

Gerry Myerson has already addressed the other part of your question.

$\endgroup$
3
$\begingroup$

The 0-1 problem is called the subset sum problem. There is a lot of literature on it. It is known to be NP-complete, which implies that no one knows an algorithm guaranteed to solve it that improves much on brute force.

$\endgroup$
  • 1
    $\begingroup$ ...in the worst case! NP-completeness doesn't imply that e.g. a problem is hard on average. $\endgroup$ – Qiaochu Yuan May 15 '12 at 6:03
  • $\begingroup$ @Qiaochu, true. But I think subset-sum is one that's hard on average. In any event, as I wrote, there is a lot of literature. All OP has to do is type "subset sum" into Google to see what comes up. $\endgroup$ – Gerry Myerson May 15 '12 at 7:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.