Mixing
How do I solve a linear Diophantine equation with three unknowns?
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
asked Oct 4 '13 at 1:42
agent154
3,642196397
add a comment |
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
asked Oct 4 '13 at 1:42
agent154
3,642196397
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
add a comment |
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
asked Oct 4 '13 at 1:42
agent154
3,642196397
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
elementary-number-theory diophantine-equations
asked Oct 4 '13 at 1:42
agent154
3,642196397
asked Oct 4 '13 at 1:42
agent154
3,642196397
asked Oct 4 '13 at 1:42
agent154
3,642196397
asked Oct 4 '13 at 1:42
agent154
3,642196397
asked Oct 4 '13 at 1:42
agent154
3,642196397
3,642196397
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
add a comment |
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
add a comment |
3 Answers
3
active
oldest
votes
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.$
answered Oct 4 '13 at 1:45
Will Jagy
101k599199
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
|
show 2 more comments
[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.
answered Oct 13 '15 at 5:28
John Frederick Chionglo
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
add a comment |
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.
answered Jun 27 '17 at 15:47
Bill Dubuque
208k29190628
+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 '18 at 16:12
add a comment |
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',
autoActivateHeartbeat: false,
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
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
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.$
answered Oct 4 '13 at 1:45
Will Jagy
101k599199
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
|
show 2 more comments
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.$
answered Oct 4 '13 at 1:45
Will Jagy
101k599199
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
|
show 2 more comments
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.$
answered Oct 4 '13 at 1:45
Will Jagy
101k599199
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.$
answered Oct 4 '13 at 1:45
Will Jagy
101k599199
answered Oct 4 '13 at 1:45
Will Jagy
101k599199
answered Oct 4 '13 at 1:45
Will Jagy
101k599199
answered Oct 4 '13 at 1:45
Will Jagy
101k599199
101k599199
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
|
show 2 more comments
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
|
show 2 more comments
[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.
answered Oct 13 '15 at 5:28
John Frederick Chionglo
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
add a comment |
[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.
answered Oct 13 '15 at 5:28
John Frederick Chionglo
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
add a comment |
[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.
answered Oct 13 '15 at 5:28
John Frederick Chionglo
26215
[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.
answered Oct 13 '15 at 5:28
John Frederick Chionglo
26215
answered Oct 13 '15 at 5:28
John Frederick Chionglo
26215
answered Oct 13 '15 at 5:28
John Frederick Chionglo
26215
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
add a comment |
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
add a comment |
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.
answered Jun 27 '17 at 15:47
Bill Dubuque
208k29190628
+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 '18 at 16:12
add a comment |
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.
answered Jun 27 '17 at 15:47
Bill Dubuque
208k29190628
+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 '18 at 16:12
add a comment |
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.
answered Jun 27 '17 at 15:47
Bill Dubuque
208k29190628
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.
answered Jun 27 '17 at 15:47
Bill Dubuque
208k29190628
edited Nov 20 '18 at 19:20
answered Jun 27 '17 at 15:47
Bill Dubuque
208k29190628
answered Jun 27 '17 at 15:47
Bill Dubuque
208k29190628
answered Jun 27 '17 at 15:47
Bill Dubuque
208k29190628
208k29190628
+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 '18 at 16:12
add a comment |
+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 '18 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 '18 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 '18 at 16:12
add a comment |
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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
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