# Problem on Linear Diophantine Equation over 3 variables

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

-
what is given in your equation? – Victor Mar 31 '12 at 17:14
@Victor: $a,b,c,d$, obviously – t.b. Mar 31 '12 at 17:16
Some details depend on relationships between greatest common divisors. For example, if $\gcd(a,b,c)$ does not divide $d$, there are no solutions. But generally there is a two-parameter infinite family of solutions. Individual solutions can be found using the Extended Euclidean algorithm. Situation is simplest if $\gcd(a,b)=\gcd(b,c)=\gcd(c,a)=1$. Then from two suitably chosen solutions, can find a formula for all. Is your problem really about specific numbers, or is it general? – André Nicolas Mar 31 '12 at 17:16
So the answer is in terms of a,b,c? – Victor Mar 31 '12 at 17:17

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

-
Thank you very much for your help. – user12290 Apr 1 '12 at 12:34