# 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.

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

-

Another example done with Maple: $$pol:= 37+13\,n-88\,i-90\,e+53\,k-96\,a+72\,b-28\,l+62\,z+16\,r-83\,v+83\,s- 48\,x+9\,t+47\,d-87\,c-91\,h-10\,o+44\,g+71\,q-82\,p+43\,f-60\,u+5\,m- 19\,y+98\,w;$$ $$isolve(pol);$$ produces $$\left\{ a={\it \_Z1},b={\it \_Z2},c={\it \_Z3},d={\it \_Z4},e={\it \_Z5},f={\it \_Z6},g={\it \_Z7},h={\it \_Z8},i={\it \_Z9},k={\it \_Z10 },l={\it \_Z11},m=-57-39\,{\it \_Z15}-28\,{\it \_Z16}-29\,{\it \_Z17}- 39\,{\it \_Z18}+12\,{\it \_Z19}-33\,{\it \_Z20}-32\,{\it \_Z21}-40\,{ \it \_Z22}-21\,{\it \_Z23}-62\,{\it \_Z24}-23\,{\it \_Z10}-44\,{\it \_Z11}-15\,{\it \_Z12}+2\,{\it \_Z13}+4\,{\it \_Z14}-59\,{\it \_Z4}+18 \,{\it \_Z5}-21\,{\it \_Z6}-46\,{\it \_Z7}-19\,{\it \_Z8}-32\,{\it \_Z9}-18\,{\it \_Z1}+5\,{\it \_Z3}-64\,{\it \_Z2},n={\it \_Z12},o={ \it \_Z13},p={\it \_Z14},q={\it \_Z15},r={\it \_Z16},s={\it \_Z17},t={ \it \_Z18},u={\it \_Z19},v={\it \_Z20},w={\it \_Z21},x={\it \_Z22},y={ \it \_Z23},z=4+3\,{\it \_Z1}+4\,{\it \_Z2}+{\it \_Z3}+4\,{\it \_Z4}+{ \it \_Z6}+3\,{\it \_Z7}+3\,{\it \_Z8}+4\,{\it \_Z9}+{\it \_Z10}+4\,{ \it \_Z11}+{\it \_Z12}+{\it \_Z14}+2\,{\it \_Z15}+2\,{\it \_Z16}+{\it \_Z17}+3\,{\it \_Z18}+4\,{\it \_Z20}+{\it \_Z21}+4\,{\it \_Z22}+2\,{ \it \_Z23}+5\,{\it \_Z24} \right\}$$

-
How does Maple do it? –  Nick ODell Jun 28 '13 at 15:00
Do you ask how a calculator finds $\log(4.6)$? There is a difference between an algorithm and its realization. Have you tried to solve a diophantine equation with 24 unknowns by hand? Good luck! It is difficult to look into Maple codes. Doing it by the printlevel:=35 command, I see that Maple uses tools of linear algebra. –  user64494 Jun 28 '13 at 20:38
Do you ask how a calculator finds log(4.6)? That seems like an interesting question. I should ask that sometime. It is difficult to look into Maple codes. So, if I want to write a program to solve Diophantine equations, and I don't have two grand to shell out for Maple, then I'm just SOL? –  Nick ODell Jun 28 '13 at 21:48
@ Nick ODell: Does your last sentence deal with the question under consideration? –  user64494 Jun 29 '13 at 5:28
If you described how Maple works, then you would have a good answer. As is, it's rather like replying to the question "How do I do long division?" with "Use a calculator." –  Nick ODell Jun 29 '13 at 5:41