Sign up ×
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.

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.

share|cite|improve this question
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

1 Answer 1

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 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?)

share|cite|improve this answer

Your Answer


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.