Given a linear Diophantine equation with many terms, for example

$aw + bx + cy + dz = e$

How do you work out $w, x, y, z$, without brute force? $a, b, c, d, e$ are given; they are also natural numbers. $a, b, c, d$ are co-prime. $w, x, y, z$ can be any integer.

I've seen this algorithm, but it looks like it only works for 2 terms. I want an algorithm that can work for any number of terms.

There are an infinite number of solutions, any of them are fine, but ones where $w$ and friends are closer to zero are better.

Context: I'm trying to extend the answer given here to multiple terms.

  • $\begingroup$ Maple does it. For example, $$isolve(4x+5y+7z+3t = 16);$$ produces $$\left\{ t=3-6\,{\it \_Z1}-4\,{\it \_Z2}-7\,{\it \_Z3},x={\it \_Z1},y= {\it \_Z2},z=1+2\,{\it \_Z1}+{\it \_Z2}+3\,{\it \_Z3} \right\} . $$ $\endgroup$
    – user64494
    Jun 28 '13 at 6:16
  • $\begingroup$ I would say giving it to Maple qualifies as brute force. $\endgroup$ Jun 28 '13 at 7:37
  • $\begingroup$ @ Nick ODell:What do you mean by "brute force"? Solving equations with many unknowns in integers requires a big work. $\endgroup$
    – user64494
    Jun 28 '13 at 20:46
  • $\begingroup$ @user64494 You can solve this by cycling $w$ and friends through all possible integers. This is a rather slow approach, because if $w$ and friends are all over 1000, for example, it takes more than a trillion iterations. Seeing as there's a faster approach when you have 2 terms, I thought there might be a faster one when you have many terms. Not knowing how Maple solves this, I couldn't say whether it uses brute force. $\endgroup$
    – Nick ODell
    Jun 28 '13 at 21:57
  • $\begingroup$ @ Nick ODell: Because Maple 17 successfully finds the infinite set of solutions in the case under consideration, it is clear that Maple does not use "brute force" in your understanding. $\endgroup$
    – user64494
    Jun 29 '13 at 5:24

A method is given in Leon Bernstein's paper, The linear diophantine equation in $n$ variables and its application to generalized Fibonacci numbers, available at http://www.fq.math.ca/Scanned/6-3/bernstein.pdf I believe this is from the June 1968 issue of the Fibonacci Quarterly, pages 3 to 63.

See also (Diophantine?) Equations With Multiple Variables? (perhaps the current question should be closed as a duplicate of this older one?)


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.