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.

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|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
add comment

2 Answers 2

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

share|improve this answer
add comment

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\} $$

share|improve this answer
    
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
add comment

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.