Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

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

2 Answers 2

up vote 4 down vote accepted

The diophantine equation $ax+by = r$ can be solved if and only if $\gcd(a,b)|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.

share|improve this answer

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.

share|improve this answer
1  
...in the worst case! NP-completeness doesn't imply that e.g. a problem is hard on average. –  Qiaochu Yuan May 15 '12 at 6:03
    
@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. –  Gerry Myerson May 15 '12 at 7:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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