How do I solve a linear Diophantine equation with three unknowns?











up vote
7
down vote

favorite
6













Find one integer solution to the Diophantine equation
begin{equation*}
18x+14y+63z=5.
end{equation*}




If this were only a linear equation over $mathbb{Z}^2$, then I could easily solve it by using the extended Euclidean algorithm... but I have no idea how to do this with more than 2 unknowns...










share|cite|improve this question






















  • how much are you sure about the "existence" of "one integer solution"?????
    – user87543
    Oct 4 '13 at 1:44












  • See my answer (pointing to Cauchy's general solution) here: <math.stackexchange.com/questions/742684/…>
    – Kieren MacMillan
    Aug 23 '14 at 17:08















up vote
7
down vote

favorite
6













Find one integer solution to the Diophantine equation
begin{equation*}
18x+14y+63z=5.
end{equation*}




If this were only a linear equation over $mathbb{Z}^2$, then I could easily solve it by using the extended Euclidean algorithm... but I have no idea how to do this with more than 2 unknowns...










share|cite|improve this question






















  • how much are you sure about the "existence" of "one integer solution"?????
    – user87543
    Oct 4 '13 at 1:44












  • See my answer (pointing to Cauchy's general solution) here: <math.stackexchange.com/questions/742684/…>
    – Kieren MacMillan
    Aug 23 '14 at 17:08













up vote
7
down vote

favorite
6









up vote
7
down vote

favorite
6






6






Find one integer solution to the Diophantine equation
begin{equation*}
18x+14y+63z=5.
end{equation*}




If this were only a linear equation over $mathbb{Z}^2$, then I could easily solve it by using the extended Euclidean algorithm... but I have no idea how to do this with more than 2 unknowns...










share|cite|improve this question














Find one integer solution to the Diophantine equation
begin{equation*}
18x+14y+63z=5.
end{equation*}




If this were only a linear equation over $mathbb{Z}^2$, then I could easily solve it by using the extended Euclidean algorithm... but I have no idea how to do this with more than 2 unknowns...







elementary-number-theory diophantine-equations






share|cite|improve this question













share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










asked Oct 4 '13 at 1:42









agent154

3,637196397




3,637196397












  • how much are you sure about the "existence" of "one integer solution"?????
    – user87543
    Oct 4 '13 at 1:44












  • See my answer (pointing to Cauchy's general solution) here: <math.stackexchange.com/questions/742684/…>
    – Kieren MacMillan
    Aug 23 '14 at 17:08


















  • how much are you sure about the "existence" of "one integer solution"?????
    – user87543
    Oct 4 '13 at 1:44












  • See my answer (pointing to Cauchy's general solution) here: <math.stackexchange.com/questions/742684/…>
    – Kieren MacMillan
    Aug 23 '14 at 17:08
















how much are you sure about the "existence" of "one integer solution"?????
– user87543
Oct 4 '13 at 1:44






how much are you sure about the "existence" of "one integer solution"?????
– user87543
Oct 4 '13 at 1:44














See my answer (pointing to Cauchy's general solution) here: <math.stackexchange.com/questions/742684/…>
– Kieren MacMillan
Aug 23 '14 at 17:08




See my answer (pointing to Cauchy's general solution) here: <math.stackexchange.com/questions/742684/…>
– Kieren MacMillan
Aug 23 '14 at 17:08










3 Answers
3






active

oldest

votes

















up vote
8
down vote



accepted










You solve $18 u + 14 v = 2 = gcd(18,14).$ Solve $2 w + 63 z = 1.$ Combine to get $18 x + 14 y + 63 z = 1.$ Then multiply all by $5.$






share|cite|improve this answer

















  • 1




    Could you elaborate on the "combine" part? I get a solution to $18u+14v=2$ with $u=-3$, $v=4$. Then if I solve $2w+63z=1$, I get $w=-31$ and $z=1$. What do I combine where to get $18u+14v+63z=1$? I tried plugging in $u,v,z$ as I found them and I get $(-3)(18)+(4)(14)+63=65...
    – agent154
    Oct 4 '13 at 1:56






  • 2




    @agent154 $$(18u+14v)w + 63z = 1$$
    – Will Jagy
    Oct 4 '13 at 1:58






  • 1




    you have $18(-3)+14(4)=2$ and $2(-31)+63(1)=1$...from $18(-3)+14(4)=2$ you have $18(-3.(-31))+14(4.(-31))=2(-31)$.. now combine with $2(-31)+63(1)=1$..
    – user87543
    Oct 4 '13 at 1:58










  • OK, I did the math and it works out. Very complicated work to get used to... I suppose I just need to do it a few times to get familiar with the procedure.
    – agent154
    Oct 4 '13 at 2:02






  • 1




    @agent154, do $10x + 12 y + 15 z = 163.$
    – Will Jagy
    Oct 4 '13 at 2:15


















up vote
1
down vote













[For the following paragraphs, please refer to the figure at the end of the last paragraph (the figure is also available in PDF).]



The manipulations performed from steps (0) to (17) were designed to create the linear system of equations (0a), (5a), (11a) and (17a). The manipulations end when the absolute value of a coefficient of the latest equation added is 1 (see (17)).



Equation (0a) is given. It is possible to infer equations (5a), (11a) and (17a) from (0), (5) and (11) respectively without performing manipulations (0) to (17) directly. In every case, select the smallest absolute value coefficient, generate the next equation by replacing every coefficient with the remainder of the coefficient divided by the selected coefficient (smallest absolute value coefficient) – do the same with the right-hand constant – and add the new variable whose coefficient is the smallest absolute value coefficient. If the new equation has a greatest common divisor greater than one, divide the equation by the greatest common divisor (it may be necessary to divide this greatest common divisor from previous equations). Stop when the absolute value of a coefficient of the latest equation added is 1.
Then proceed to solve the linear systems of equations.



enter image description here






share|cite|improve this answer





















  • The extended euclidean algorithm can be presented much more simply - see my answer and its link.
    – Bill Dubuque
    Jun 27 '17 at 15:49






  • 1




    I found several errors in my answer. However instead of replacing the answer with a correction version, I am including a link to the correction: researchgate.net/publication/….
    – John Frederick Chionglo
    Jul 23 '17 at 9:13




















up vote
1
down vote













Hint $ color{#c00}{18!-!14},mid, 63!+!1 $ $, Rightarrow,16,(18!-! 14)-63 = 1.,$ Scale that by $,5,$ to finish.



Remark $ $ The idea is simply to search for a "small" linear combination $,n = color{#c00}{ia+jb},$ of two elements $,a,b,$ of $,{14,18,63},$ such that the 3rd element satisfies $ cequiv pm1 pmod n,,$ hence $, pm1 = c+kn = c + ki,a + kj,b,$ thus scaling by $pm n,$ yields $n$ as a linear combination of $a,b,c.,$ Above the first "small" number we see $, n = color{#c00}{18!-!14} = 4,$ works since $63equiv -1pmod {!4}.$



The reason for choosing $n$ "small" is that this increases the probability that $,cequiv pm1pmod{! n},,$ e.g. $100%$ chance if $n = 2,,$ $67%$ if $n = 3.,$ We know (by Bezout) that the smallest such $n$ is $,gcd(a,b),$ but - as we saw above - often simpler choices work such as $,b-a.$



More algorithmically, we can use the Extended Euclidean Algorithm to compute $rm,gcd(63,18,14) = 1,$ in a couple steps



$$begin{array}{rrr}
[1]& 63& 1& 0& 0\
[2]& 18& 0& 1& 0\
[3]& 14& 0& 0& 1\
[2] -[3], =, [4]& 4& !!0& 1& -1\
16[4] -[1], =,[5]& 1& -1& 16& !!!!-16
end{array}qquadqquadqquadquad$$



where the row $ n, a, b, c, d $ denotes that $ n = 63a + 18 b + 14 c. $ Thus the final row yields



$$quad 1 = -63 +16(18) - 16(14)$$



See here for another worked example.






share|cite|improve this answer























  • +1 For showing the extended euclidean algorithm approach-- a fine example.
    – Rustyn
    Jul 13 '17 at 7:42










  • @Rustyn I added a Remark that explains the idea behind the optimization employed in the Hint.
    – Bill Dubuque
    Jul 13 '17 at 14:42










  • Hey Bill, could you please help me with this question regarding the general solution of a multivariable, linear Diophantine equation?
    – TheSimpliFire
    Oct 17 at 16:12











Your Answer





StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f514105%2fhow-do-i-solve-a-linear-diophantine-equation-with-three-unknowns%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























3 Answers
3






active

oldest

votes








3 Answers
3






active

oldest

votes









active

oldest

votes






active

oldest

votes








up vote
8
down vote



accepted










You solve $18 u + 14 v = 2 = gcd(18,14).$ Solve $2 w + 63 z = 1.$ Combine to get $18 x + 14 y + 63 z = 1.$ Then multiply all by $5.$






share|cite|improve this answer

















  • 1




    Could you elaborate on the "combine" part? I get a solution to $18u+14v=2$ with $u=-3$, $v=4$. Then if I solve $2w+63z=1$, I get $w=-31$ and $z=1$. What do I combine where to get $18u+14v+63z=1$? I tried plugging in $u,v,z$ as I found them and I get $(-3)(18)+(4)(14)+63=65...
    – agent154
    Oct 4 '13 at 1:56






  • 2




    @agent154 $$(18u+14v)w + 63z = 1$$
    – Will Jagy
    Oct 4 '13 at 1:58






  • 1




    you have $18(-3)+14(4)=2$ and $2(-31)+63(1)=1$...from $18(-3)+14(4)=2$ you have $18(-3.(-31))+14(4.(-31))=2(-31)$.. now combine with $2(-31)+63(1)=1$..
    – user87543
    Oct 4 '13 at 1:58










  • OK, I did the math and it works out. Very complicated work to get used to... I suppose I just need to do it a few times to get familiar with the procedure.
    – agent154
    Oct 4 '13 at 2:02






  • 1




    @agent154, do $10x + 12 y + 15 z = 163.$
    – Will Jagy
    Oct 4 '13 at 2:15















up vote
8
down vote



accepted










You solve $18 u + 14 v = 2 = gcd(18,14).$ Solve $2 w + 63 z = 1.$ Combine to get $18 x + 14 y + 63 z = 1.$ Then multiply all by $5.$






share|cite|improve this answer

















  • 1




    Could you elaborate on the "combine" part? I get a solution to $18u+14v=2$ with $u=-3$, $v=4$. Then if I solve $2w+63z=1$, I get $w=-31$ and $z=1$. What do I combine where to get $18u+14v+63z=1$? I tried plugging in $u,v,z$ as I found them and I get $(-3)(18)+(4)(14)+63=65...
    – agent154
    Oct 4 '13 at 1:56






  • 2




    @agent154 $$(18u+14v)w + 63z = 1$$
    – Will Jagy
    Oct 4 '13 at 1:58






  • 1




    you have $18(-3)+14(4)=2$ and $2(-31)+63(1)=1$...from $18(-3)+14(4)=2$ you have $18(-3.(-31))+14(4.(-31))=2(-31)$.. now combine with $2(-31)+63(1)=1$..
    – user87543
    Oct 4 '13 at 1:58










  • OK, I did the math and it works out. Very complicated work to get used to... I suppose I just need to do it a few times to get familiar with the procedure.
    – agent154
    Oct 4 '13 at 2:02






  • 1




    @agent154, do $10x + 12 y + 15 z = 163.$
    – Will Jagy
    Oct 4 '13 at 2:15













up vote
8
down vote



accepted







up vote
8
down vote



accepted






You solve $18 u + 14 v = 2 = gcd(18,14).$ Solve $2 w + 63 z = 1.$ Combine to get $18 x + 14 y + 63 z = 1.$ Then multiply all by $5.$






share|cite|improve this answer












You solve $18 u + 14 v = 2 = gcd(18,14).$ Solve $2 w + 63 z = 1.$ Combine to get $18 x + 14 y + 63 z = 1.$ Then multiply all by $5.$







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered Oct 4 '13 at 1:45









Will Jagy

101k598198




101k598198








  • 1




    Could you elaborate on the "combine" part? I get a solution to $18u+14v=2$ with $u=-3$, $v=4$. Then if I solve $2w+63z=1$, I get $w=-31$ and $z=1$. What do I combine where to get $18u+14v+63z=1$? I tried plugging in $u,v,z$ as I found them and I get $(-3)(18)+(4)(14)+63=65...
    – agent154
    Oct 4 '13 at 1:56






  • 2




    @agent154 $$(18u+14v)w + 63z = 1$$
    – Will Jagy
    Oct 4 '13 at 1:58






  • 1




    you have $18(-3)+14(4)=2$ and $2(-31)+63(1)=1$...from $18(-3)+14(4)=2$ you have $18(-3.(-31))+14(4.(-31))=2(-31)$.. now combine with $2(-31)+63(1)=1$..
    – user87543
    Oct 4 '13 at 1:58










  • OK, I did the math and it works out. Very complicated work to get used to... I suppose I just need to do it a few times to get familiar with the procedure.
    – agent154
    Oct 4 '13 at 2:02






  • 1




    @agent154, do $10x + 12 y + 15 z = 163.$
    – Will Jagy
    Oct 4 '13 at 2:15














  • 1




    Could you elaborate on the "combine" part? I get a solution to $18u+14v=2$ with $u=-3$, $v=4$. Then if I solve $2w+63z=1$, I get $w=-31$ and $z=1$. What do I combine where to get $18u+14v+63z=1$? I tried plugging in $u,v,z$ as I found them and I get $(-3)(18)+(4)(14)+63=65...
    – agent154
    Oct 4 '13 at 1:56






  • 2




    @agent154 $$(18u+14v)w + 63z = 1$$
    – Will Jagy
    Oct 4 '13 at 1:58






  • 1




    you have $18(-3)+14(4)=2$ and $2(-31)+63(1)=1$...from $18(-3)+14(4)=2$ you have $18(-3.(-31))+14(4.(-31))=2(-31)$.. now combine with $2(-31)+63(1)=1$..
    – user87543
    Oct 4 '13 at 1:58










  • OK, I did the math and it works out. Very complicated work to get used to... I suppose I just need to do it a few times to get familiar with the procedure.
    – agent154
    Oct 4 '13 at 2:02






  • 1




    @agent154, do $10x + 12 y + 15 z = 163.$
    – Will Jagy
    Oct 4 '13 at 2:15








1




1




Could you elaborate on the "combine" part? I get a solution to $18u+14v=2$ with $u=-3$, $v=4$. Then if I solve $2w+63z=1$, I get $w=-31$ and $z=1$. What do I combine where to get $18u+14v+63z=1$? I tried plugging in $u,v,z$ as I found them and I get $(-3)(18)+(4)(14)+63=65...
– agent154
Oct 4 '13 at 1:56




Could you elaborate on the "combine" part? I get a solution to $18u+14v=2$ with $u=-3$, $v=4$. Then if I solve $2w+63z=1$, I get $w=-31$ and $z=1$. What do I combine where to get $18u+14v+63z=1$? I tried plugging in $u,v,z$ as I found them and I get $(-3)(18)+(4)(14)+63=65...
– agent154
Oct 4 '13 at 1:56




2




2




@agent154 $$(18u+14v)w + 63z = 1$$
– Will Jagy
Oct 4 '13 at 1:58




@agent154 $$(18u+14v)w + 63z = 1$$
– Will Jagy
Oct 4 '13 at 1:58




1




1




you have $18(-3)+14(4)=2$ and $2(-31)+63(1)=1$...from $18(-3)+14(4)=2$ you have $18(-3.(-31))+14(4.(-31))=2(-31)$.. now combine with $2(-31)+63(1)=1$..
– user87543
Oct 4 '13 at 1:58




you have $18(-3)+14(4)=2$ and $2(-31)+63(1)=1$...from $18(-3)+14(4)=2$ you have $18(-3.(-31))+14(4.(-31))=2(-31)$.. now combine with $2(-31)+63(1)=1$..
– user87543
Oct 4 '13 at 1:58












OK, I did the math and it works out. Very complicated work to get used to... I suppose I just need to do it a few times to get familiar with the procedure.
– agent154
Oct 4 '13 at 2:02




OK, I did the math and it works out. Very complicated work to get used to... I suppose I just need to do it a few times to get familiar with the procedure.
– agent154
Oct 4 '13 at 2:02




1




1




@agent154, do $10x + 12 y + 15 z = 163.$
– Will Jagy
Oct 4 '13 at 2:15




@agent154, do $10x + 12 y + 15 z = 163.$
– Will Jagy
Oct 4 '13 at 2:15










up vote
1
down vote













[For the following paragraphs, please refer to the figure at the end of the last paragraph (the figure is also available in PDF).]



The manipulations performed from steps (0) to (17) were designed to create the linear system of equations (0a), (5a), (11a) and (17a). The manipulations end when the absolute value of a coefficient of the latest equation added is 1 (see (17)).



Equation (0a) is given. It is possible to infer equations (5a), (11a) and (17a) from (0), (5) and (11) respectively without performing manipulations (0) to (17) directly. In every case, select the smallest absolute value coefficient, generate the next equation by replacing every coefficient with the remainder of the coefficient divided by the selected coefficient (smallest absolute value coefficient) – do the same with the right-hand constant – and add the new variable whose coefficient is the smallest absolute value coefficient. If the new equation has a greatest common divisor greater than one, divide the equation by the greatest common divisor (it may be necessary to divide this greatest common divisor from previous equations). Stop when the absolute value of a coefficient of the latest equation added is 1.
Then proceed to solve the linear systems of equations.



enter image description here






share|cite|improve this answer





















  • The extended euclidean algorithm can be presented much more simply - see my answer and its link.
    – Bill Dubuque
    Jun 27 '17 at 15:49






  • 1




    I found several errors in my answer. However instead of replacing the answer with a correction version, I am including a link to the correction: researchgate.net/publication/….
    – John Frederick Chionglo
    Jul 23 '17 at 9:13

















up vote
1
down vote













[For the following paragraphs, please refer to the figure at the end of the last paragraph (the figure is also available in PDF).]



The manipulations performed from steps (0) to (17) were designed to create the linear system of equations (0a), (5a), (11a) and (17a). The manipulations end when the absolute value of a coefficient of the latest equation added is 1 (see (17)).



Equation (0a) is given. It is possible to infer equations (5a), (11a) and (17a) from (0), (5) and (11) respectively without performing manipulations (0) to (17) directly. In every case, select the smallest absolute value coefficient, generate the next equation by replacing every coefficient with the remainder of the coefficient divided by the selected coefficient (smallest absolute value coefficient) – do the same with the right-hand constant – and add the new variable whose coefficient is the smallest absolute value coefficient. If the new equation has a greatest common divisor greater than one, divide the equation by the greatest common divisor (it may be necessary to divide this greatest common divisor from previous equations). Stop when the absolute value of a coefficient of the latest equation added is 1.
Then proceed to solve the linear systems of equations.



enter image description here






share|cite|improve this answer





















  • The extended euclidean algorithm can be presented much more simply - see my answer and its link.
    – Bill Dubuque
    Jun 27 '17 at 15:49






  • 1




    I found several errors in my answer. However instead of replacing the answer with a correction version, I am including a link to the correction: researchgate.net/publication/….
    – John Frederick Chionglo
    Jul 23 '17 at 9:13















up vote
1
down vote










up vote
1
down vote









[For the following paragraphs, please refer to the figure at the end of the last paragraph (the figure is also available in PDF).]



The manipulations performed from steps (0) to (17) were designed to create the linear system of equations (0a), (5a), (11a) and (17a). The manipulations end when the absolute value of a coefficient of the latest equation added is 1 (see (17)).



Equation (0a) is given. It is possible to infer equations (5a), (11a) and (17a) from (0), (5) and (11) respectively without performing manipulations (0) to (17) directly. In every case, select the smallest absolute value coefficient, generate the next equation by replacing every coefficient with the remainder of the coefficient divided by the selected coefficient (smallest absolute value coefficient) – do the same with the right-hand constant – and add the new variable whose coefficient is the smallest absolute value coefficient. If the new equation has a greatest common divisor greater than one, divide the equation by the greatest common divisor (it may be necessary to divide this greatest common divisor from previous equations). Stop when the absolute value of a coefficient of the latest equation added is 1.
Then proceed to solve the linear systems of equations.



enter image description here






share|cite|improve this answer












[For the following paragraphs, please refer to the figure at the end of the last paragraph (the figure is also available in PDF).]



The manipulations performed from steps (0) to (17) were designed to create the linear system of equations (0a), (5a), (11a) and (17a). The manipulations end when the absolute value of a coefficient of the latest equation added is 1 (see (17)).



Equation (0a) is given. It is possible to infer equations (5a), (11a) and (17a) from (0), (5) and (11) respectively without performing manipulations (0) to (17) directly. In every case, select the smallest absolute value coefficient, generate the next equation by replacing every coefficient with the remainder of the coefficient divided by the selected coefficient (smallest absolute value coefficient) – do the same with the right-hand constant – and add the new variable whose coefficient is the smallest absolute value coefficient. If the new equation has a greatest common divisor greater than one, divide the equation by the greatest common divisor (it may be necessary to divide this greatest common divisor from previous equations). Stop when the absolute value of a coefficient of the latest equation added is 1.
Then proceed to solve the linear systems of equations.



enter image description here







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered Oct 13 '15 at 5:28









John Frederick Chionglo

26215




26215












  • The extended euclidean algorithm can be presented much more simply - see my answer and its link.
    – Bill Dubuque
    Jun 27 '17 at 15:49






  • 1




    I found several errors in my answer. However instead of replacing the answer with a correction version, I am including a link to the correction: researchgate.net/publication/….
    – John Frederick Chionglo
    Jul 23 '17 at 9:13




















  • The extended euclidean algorithm can be presented much more simply - see my answer and its link.
    – Bill Dubuque
    Jun 27 '17 at 15:49






  • 1




    I found several errors in my answer. However instead of replacing the answer with a correction version, I am including a link to the correction: researchgate.net/publication/….
    – John Frederick Chionglo
    Jul 23 '17 at 9:13


















The extended euclidean algorithm can be presented much more simply - see my answer and its link.
– Bill Dubuque
Jun 27 '17 at 15:49




The extended euclidean algorithm can be presented much more simply - see my answer and its link.
– Bill Dubuque
Jun 27 '17 at 15:49




1




1




I found several errors in my answer. However instead of replacing the answer with a correction version, I am including a link to the correction: researchgate.net/publication/….
– John Frederick Chionglo
Jul 23 '17 at 9:13






I found several errors in my answer. However instead of replacing the answer with a correction version, I am including a link to the correction: researchgate.net/publication/….
– John Frederick Chionglo
Jul 23 '17 at 9:13












up vote
1
down vote













Hint $ color{#c00}{18!-!14},mid, 63!+!1 $ $, Rightarrow,16,(18!-! 14)-63 = 1.,$ Scale that by $,5,$ to finish.



Remark $ $ The idea is simply to search for a "small" linear combination $,n = color{#c00}{ia+jb},$ of two elements $,a,b,$ of $,{14,18,63},$ such that the 3rd element satisfies $ cequiv pm1 pmod n,,$ hence $, pm1 = c+kn = c + ki,a + kj,b,$ thus scaling by $pm n,$ yields $n$ as a linear combination of $a,b,c.,$ Above the first "small" number we see $, n = color{#c00}{18!-!14} = 4,$ works since $63equiv -1pmod {!4}.$



The reason for choosing $n$ "small" is that this increases the probability that $,cequiv pm1pmod{! n},,$ e.g. $100%$ chance if $n = 2,,$ $67%$ if $n = 3.,$ We know (by Bezout) that the smallest such $n$ is $,gcd(a,b),$ but - as we saw above - often simpler choices work such as $,b-a.$



More algorithmically, we can use the Extended Euclidean Algorithm to compute $rm,gcd(63,18,14) = 1,$ in a couple steps



$$begin{array}{rrr}
[1]& 63& 1& 0& 0\
[2]& 18& 0& 1& 0\
[3]& 14& 0& 0& 1\
[2] -[3], =, [4]& 4& !!0& 1& -1\
16[4] -[1], =,[5]& 1& -1& 16& !!!!-16
end{array}qquadqquadqquadquad$$



where the row $ n, a, b, c, d $ denotes that $ n = 63a + 18 b + 14 c. $ Thus the final row yields



$$quad 1 = -63 +16(18) - 16(14)$$



See here for another worked example.






share|cite|improve this answer























  • +1 For showing the extended euclidean algorithm approach-- a fine example.
    – Rustyn
    Jul 13 '17 at 7:42










  • @Rustyn I added a Remark that explains the idea behind the optimization employed in the Hint.
    – Bill Dubuque
    Jul 13 '17 at 14:42










  • Hey Bill, could you please help me with this question regarding the general solution of a multivariable, linear Diophantine equation?
    – TheSimpliFire
    Oct 17 at 16:12















up vote
1
down vote













Hint $ color{#c00}{18!-!14},mid, 63!+!1 $ $, Rightarrow,16,(18!-! 14)-63 = 1.,$ Scale that by $,5,$ to finish.



Remark $ $ The idea is simply to search for a "small" linear combination $,n = color{#c00}{ia+jb},$ of two elements $,a,b,$ of $,{14,18,63},$ such that the 3rd element satisfies $ cequiv pm1 pmod n,,$ hence $, pm1 = c+kn = c + ki,a + kj,b,$ thus scaling by $pm n,$ yields $n$ as a linear combination of $a,b,c.,$ Above the first "small" number we see $, n = color{#c00}{18!-!14} = 4,$ works since $63equiv -1pmod {!4}.$



The reason for choosing $n$ "small" is that this increases the probability that $,cequiv pm1pmod{! n},,$ e.g. $100%$ chance if $n = 2,,$ $67%$ if $n = 3.,$ We know (by Bezout) that the smallest such $n$ is $,gcd(a,b),$ but - as we saw above - often simpler choices work such as $,b-a.$



More algorithmically, we can use the Extended Euclidean Algorithm to compute $rm,gcd(63,18,14) = 1,$ in a couple steps



$$begin{array}{rrr}
[1]& 63& 1& 0& 0\
[2]& 18& 0& 1& 0\
[3]& 14& 0& 0& 1\
[2] -[3], =, [4]& 4& !!0& 1& -1\
16[4] -[1], =,[5]& 1& -1& 16& !!!!-16
end{array}qquadqquadqquadquad$$



where the row $ n, a, b, c, d $ denotes that $ n = 63a + 18 b + 14 c. $ Thus the final row yields



$$quad 1 = -63 +16(18) - 16(14)$$



See here for another worked example.






share|cite|improve this answer























  • +1 For showing the extended euclidean algorithm approach-- a fine example.
    – Rustyn
    Jul 13 '17 at 7:42










  • @Rustyn I added a Remark that explains the idea behind the optimization employed in the Hint.
    – Bill Dubuque
    Jul 13 '17 at 14:42










  • Hey Bill, could you please help me with this question regarding the general solution of a multivariable, linear Diophantine equation?
    – TheSimpliFire
    Oct 17 at 16:12













up vote
1
down vote










up vote
1
down vote









Hint $ color{#c00}{18!-!14},mid, 63!+!1 $ $, Rightarrow,16,(18!-! 14)-63 = 1.,$ Scale that by $,5,$ to finish.



Remark $ $ The idea is simply to search for a "small" linear combination $,n = color{#c00}{ia+jb},$ of two elements $,a,b,$ of $,{14,18,63},$ such that the 3rd element satisfies $ cequiv pm1 pmod n,,$ hence $, pm1 = c+kn = c + ki,a + kj,b,$ thus scaling by $pm n,$ yields $n$ as a linear combination of $a,b,c.,$ Above the first "small" number we see $, n = color{#c00}{18!-!14} = 4,$ works since $63equiv -1pmod {!4}.$



The reason for choosing $n$ "small" is that this increases the probability that $,cequiv pm1pmod{! n},,$ e.g. $100%$ chance if $n = 2,,$ $67%$ if $n = 3.,$ We know (by Bezout) that the smallest such $n$ is $,gcd(a,b),$ but - as we saw above - often simpler choices work such as $,b-a.$



More algorithmically, we can use the Extended Euclidean Algorithm to compute $rm,gcd(63,18,14) = 1,$ in a couple steps



$$begin{array}{rrr}
[1]& 63& 1& 0& 0\
[2]& 18& 0& 1& 0\
[3]& 14& 0& 0& 1\
[2] -[3], =, [4]& 4& !!0& 1& -1\
16[4] -[1], =,[5]& 1& -1& 16& !!!!-16
end{array}qquadqquadqquadquad$$



where the row $ n, a, b, c, d $ denotes that $ n = 63a + 18 b + 14 c. $ Thus the final row yields



$$quad 1 = -63 +16(18) - 16(14)$$



See here for another worked example.






share|cite|improve this answer














Hint $ color{#c00}{18!-!14},mid, 63!+!1 $ $, Rightarrow,16,(18!-! 14)-63 = 1.,$ Scale that by $,5,$ to finish.



Remark $ $ The idea is simply to search for a "small" linear combination $,n = color{#c00}{ia+jb},$ of two elements $,a,b,$ of $,{14,18,63},$ such that the 3rd element satisfies $ cequiv pm1 pmod n,,$ hence $, pm1 = c+kn = c + ki,a + kj,b,$ thus scaling by $pm n,$ yields $n$ as a linear combination of $a,b,c.,$ Above the first "small" number we see $, n = color{#c00}{18!-!14} = 4,$ works since $63equiv -1pmod {!4}.$



The reason for choosing $n$ "small" is that this increases the probability that $,cequiv pm1pmod{! n},,$ e.g. $100%$ chance if $n = 2,,$ $67%$ if $n = 3.,$ We know (by Bezout) that the smallest such $n$ is $,gcd(a,b),$ but - as we saw above - often simpler choices work such as $,b-a.$



More algorithmically, we can use the Extended Euclidean Algorithm to compute $rm,gcd(63,18,14) = 1,$ in a couple steps



$$begin{array}{rrr}
[1]& 63& 1& 0& 0\
[2]& 18& 0& 1& 0\
[3]& 14& 0& 0& 1\
[2] -[3], =, [4]& 4& !!0& 1& -1\
16[4] -[1], =,[5]& 1& -1& 16& !!!!-16
end{array}qquadqquadqquadquad$$



where the row $ n, a, b, c, d $ denotes that $ n = 63a + 18 b + 14 c. $ Thus the final row yields



$$quad 1 = -63 +16(18) - 16(14)$$



See here for another worked example.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited Nov 20 at 19:20

























answered Jun 27 '17 at 15:47









Bill Dubuque

207k29189624




207k29189624












  • +1 For showing the extended euclidean algorithm approach-- a fine example.
    – Rustyn
    Jul 13 '17 at 7:42










  • @Rustyn I added a Remark that explains the idea behind the optimization employed in the Hint.
    – Bill Dubuque
    Jul 13 '17 at 14:42










  • Hey Bill, could you please help me with this question regarding the general solution of a multivariable, linear Diophantine equation?
    – TheSimpliFire
    Oct 17 at 16:12


















  • +1 For showing the extended euclidean algorithm approach-- a fine example.
    – Rustyn
    Jul 13 '17 at 7:42










  • @Rustyn I added a Remark that explains the idea behind the optimization employed in the Hint.
    – Bill Dubuque
    Jul 13 '17 at 14:42










  • Hey Bill, could you please help me with this question regarding the general solution of a multivariable, linear Diophantine equation?
    – TheSimpliFire
    Oct 17 at 16:12
















+1 For showing the extended euclidean algorithm approach-- a fine example.
– Rustyn
Jul 13 '17 at 7:42




+1 For showing the extended euclidean algorithm approach-- a fine example.
– Rustyn
Jul 13 '17 at 7:42












@Rustyn I added a Remark that explains the idea behind the optimization employed in the Hint.
– Bill Dubuque
Jul 13 '17 at 14:42




@Rustyn I added a Remark that explains the idea behind the optimization employed in the Hint.
– Bill Dubuque
Jul 13 '17 at 14:42












Hey Bill, could you please help me with this question regarding the general solution of a multivariable, linear Diophantine equation?
– TheSimpliFire
Oct 17 at 16:12




Hey Bill, could you please help me with this question regarding the general solution of a multivariable, linear Diophantine equation?
– TheSimpliFire
Oct 17 at 16:12


















draft saved

draft discarded




















































Thanks for contributing an answer to Mathematics Stack Exchange!


  • Please be sure to answer the question. Provide details and share your research!

But avoid



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


Use MathJax to format equations. MathJax reference.


To learn more, see our tips on writing great answers.





Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


Please pay close attention to the following guidance:


  • Please be sure to answer the question. Provide details and share your research!

But avoid



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f514105%2fhow-do-i-solve-a-linear-diophantine-equation-with-three-unknowns%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







Popular posts from this blog

Ellipse (mathématiques)

Quarter-circle Tiles

Mont Emei