# Solving a first-order diophantine equation with many terms

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.

• 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\} .$$ – user64494 Jun 28 '13 at 6:16
• I would say giving it to Maple qualifies as brute force. – Gerry Myerson Jun 28 '13 at 7:37
• @ Nick ODell:What do you mean by "brute force"? Solving equations with many unknowns in integers requires a big work. – user64494 Jun 28 '13 at 20:46
• @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. – Nick ODell Jun 28 '13 at 21:57
• @ 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. – 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.