1
$\begingroup$

How to solve $ax+by+cz=d$ over integers where $a,b,c,d$ are integers?

  • 0
    So the answer is in terms of a,b,c?2012-03-31

1 Answers 1

4

You can solve it using the same "row reduction" techniques used in the bivariate form of the extended Euclidean algorithm, viz. start with the given linear combinations

$\rm a \:=\: 1\cdot a + 0\cdot b + 0\cdot c$

$\rm b\: =\: 0\cdot a + 1\cdot b + 0\cdot c$

$\rm c\: =\: 0\cdot a + 0\cdot b + 1\cdot c$

then used the division algorithm to find smaller linear combinations of $\rm\:a,b,c\:$ till you reach $\rm\: g = gcd(a,b,c)\:$ expressed as a linear combination of $\rm\:a,b,c.$

The given equation has a solution iff $\rm\: g\ |\ d.\:$ If so, then a solution arises by scaling the the representation of $\rm\:g\:$ by $\rm\:d/g\:$ to yield a representation of $\rm\:d\:$ as a linear combination of $\rm\:a,b,c.$

  • 0
    Thank you very much for your help.2012-04-01