# 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

## 1 Answer

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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 14, "mathjax_display_tex": 3, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": false}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8840529918670654, "perplexity_flag": "head"}