Mixing
Modular arithmetic method for solving equations
$begingroup$
I understand there is a method for solving simultaneous modular equations. For example;
$$x = 2 mod{3}$$
$$x = 3 mod{5}$$
$$x = 2 mod{7}$$
We find numbers equal to the product of every given modulo except one of them - giving $5 cdot 7$, $3 cdot 7$ and $3 cdot 5$. We then find the multiplicative inverses of these numbers with modulo equal to the number missing from the product. The numbers found are then 2, 1 and 1 in this case. The value of x is then given by:
$$x = 2 cdot (5 cdot 7) cdot 2 + 3 cdot (3 cdot 7) cdot 1 + 2 cdot (3 cdot 5) cdot 1 = 233 = 23 mod{3cdot5cdot7}$$
But I do not understand how this method correctly gives the value of $x$. I understand that the Chinese remainder theorem proves that there is a unique value of $0le x lt 3cdot5cdot7 mod{3cdot5cdot7}$ but can someone please explain why this method finds this value of x?
modular-arithmetic
asked Jan 31 at 17:09
Peter ForemanPeter Foreman
6,2611317
$endgroup$
add a comment |
$begingroup$
I understand there is a method for solving simultaneous modular equations. For example;
$$x = 2 mod{3}$$
$$x = 3 mod{5}$$
$$x = 2 mod{7}$$
We find numbers equal to the product of every given modulo except one of them - giving $5 cdot 7$, $3 cdot 7$ and $3 cdot 5$. We then find the multiplicative inverses of these numbers with modulo equal to the number missing from the product. The numbers found are then 2, 1 and 1 in this case. The value of x is then given by:
$$x = 2 cdot (5 cdot 7) cdot 2 + 3 cdot (3 cdot 7) cdot 1 + 2 cdot (3 cdot 5) cdot 1 = 233 = 23 mod{3cdot5cdot7}$$
But I do not understand how this method correctly gives the value of $x$. I understand that the Chinese remainder theorem proves that there is a unique value of $0le x lt 3cdot5cdot7 mod{3cdot5cdot7}$ but can someone please explain why this method finds this value of x?
modular-arithmetic
asked Jan 31 at 17:09
Peter ForemanPeter Foreman
6,2611317
$endgroup$
$begingroup$
It's not clear which part proves troublesome. Often it is the linearity that I describe in my answer. If it is something else then please elaborate and I can add further details.
$endgroup$
– Bill Dubuque
Jan 31 at 18:19
add a comment |
$begingroup$
I understand there is a method for solving simultaneous modular equations. For example;
$$x = 2 mod{3}$$
$$x = 3 mod{5}$$
$$x = 2 mod{7}$$
We find numbers equal to the product of every given modulo except one of them - giving $5 cdot 7$, $3 cdot 7$ and $3 cdot 5$. We then find the multiplicative inverses of these numbers with modulo equal to the number missing from the product. The numbers found are then 2, 1 and 1 in this case. The value of x is then given by:
$$x = 2 cdot (5 cdot 7) cdot 2 + 3 cdot (3 cdot 7) cdot 1 + 2 cdot (3 cdot 5) cdot 1 = 233 = 23 mod{3cdot5cdot7}$$
But I do not understand how this method correctly gives the value of $x$. I understand that the Chinese remainder theorem proves that there is a unique value of $0le x lt 3cdot5cdot7 mod{3cdot5cdot7}$ but can someone please explain why this method finds this value of x?
modular-arithmetic
asked Jan 31 at 17:09
Peter ForemanPeter Foreman
6,2611317
$endgroup$
I understand there is a method for solving simultaneous modular equations. For example;
$$x = 2 mod{3}$$
$$x = 3 mod{5}$$
$$x = 2 mod{7}$$
We find numbers equal to the product of every given modulo except one of them - giving $5 cdot 7$, $3 cdot 7$ and $3 cdot 5$. We then find the multiplicative inverses of these numbers with modulo equal to the number missing from the product. The numbers found are then 2, 1 and 1 in this case. The value of x is then given by:
$$x = 2 cdot (5 cdot 7) cdot 2 + 3 cdot (3 cdot 7) cdot 1 + 2 cdot (3 cdot 5) cdot 1 = 233 = 23 mod{3cdot5cdot7}$$
But I do not understand how this method correctly gives the value of $x$. I understand that the Chinese remainder theorem proves that there is a unique value of $0le x lt 3cdot5cdot7 mod{3cdot5cdot7}$ but can someone please explain why this method finds this value of x?
modular-arithmetic
modular-arithmetic
asked Jan 31 at 17:09
Peter ForemanPeter Foreman
6,2611317
asked Jan 31 at 17:09
Peter ForemanPeter Foreman
6,2611317
asked Jan 31 at 17:09
Peter ForemanPeter Foreman
6,2611317
asked Jan 31 at 17:09
Peter ForemanPeter Foreman
6,2611317
asked Jan 31 at 17:09
Peter ForemanPeter Foreman
6,2611317
6,2611317
$begingroup$
It's not clear which part proves troublesome. Often it is the linearity that I describe in my answer. If it is something else then please elaborate and I can add further details.
$endgroup$
– Bill Dubuque
Jan 31 at 18:19
add a comment |
$begingroup$
It's not clear which part proves troublesome. Often it is the linearity that I describe in my answer. If it is something else then please elaborate and I can add further details.
$endgroup$
– Bill Dubuque
Jan 31 at 18:19
$begingroup$
It's not clear which part proves troublesome. Often it is the linearity that I describe in my answer. If it is something else then please elaborate and I can add further details.
$endgroup$
– Bill Dubuque
Jan 31 at 18:19
$begingroup$
It's not clear which part proves troublesome. Often it is the linearity that I describe in my answer. If it is something else then please elaborate and I can add further details.
$endgroup$
– Bill Dubuque
Jan 31 at 18:19
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
This is a generalisation of the formula for the solutions of a system of two congruences modulo two coprime numbers $a$ and $b$?. This formula uses a Bézout's relation: $;ua+vb=1$ and it is:
$$begin{cases}
xequiv alphamod a,\
xequiv betamod b,
end{cases}
quadtext{which is }qquad xequiv beta ua+alpha vbmod ab$$
Indeed we have $;beta ua+alpha vbequiv alpha vbequiv alphamod a$ since hand $;vbequiv 1mod a$. Similarly modulo $b$.
Now, as $v equiv b^{-1}bmod a:$ and $;uequiv a^{-1}bmod b$, this formula can be written as
$$xequiv beta, a (a^{-1}bmod b)+alpha, b(b^{-1}bmod a)mod ab.$$
answered Jan 31 at 17:41
BernardBernard
124k741117
$endgroup$
$begingroup$
The brave anonymous downvoter struck again!
$endgroup$
– Bernard
Feb 1 at 20:47
add a comment |
$begingroup$
It helps to highlught linearity at the heart of the Chinese Remainder Theorem [CRT] formula.
$$begin{eqnarray}
x, = &a&!color{#0a0}{overbrace{(-5cdot 7)}^{large equiv, 1 ({rm mod} color{#c00}3)}} ,+, &b& overbrace{(color{#c00}3cdot 7)}^{large equiv, 1 ({rm mod} 5)}, +, &c&overbrace{(color{#c00}3cdot 5)}^{large equiv, 1 ({rm mod} 7)}quad {bf [CRT]}\ \
Rightarrow x,equiv, &a& ({rm mod} color{#c00}3), xequiv &b& ({rm mod} 4), xequiv &c& ({rm mod} 5)\
end{eqnarray}$$
since, e.g. reduced $ $ mod $ color{#c00}3,,$ the 2nd and 3rd summands are $equiv 0,,$ both having factors of $,color{#c00}3.,$
The key idea is that the braced terms are $equiv 1$ mod one modulus, and $equiv 0 $ mod all others. More clearly, if we write the system in vector form $ xequiv (a,b,c),$ mod $,(3,5,7)$ then $rm,[CRT]$ becomes
$qquad x, :=, a,color{#0a0}{(1,0,0)} + b,(0,1,0) + c,(0,0,1)equiv (a.b,c) $ as desired. $qquad [bf Linearity]$
by the green term $,color{#0a0}{g equiv 1} ({rm mod} 3), color{#0a0}{gequiv 0} ({rm mod} 5), color{#0a0}{gequiv 0} ({rm mod} 7), $ i.e. $ color{#0a0}{gequiv (1,0,0)} {rm mod} (3,5,7), $ and similarly for $,(0,1,0),$ and $,(0,0,1).$
Thus once we compute the solutions for the "basis" vectors $(1,0,0), (0,1,0), (0,0,1)$ we can exploit [Linearity] to generate the general solution as a linear combination of these basic solutions.
Solving the basic cases is easy: $,{color{#0a0}{5,7mid g},Rightarrow, 35mid g},, $ so $bmod 3!: color{#0a0}{1equiv g} equiv 35nequiv -n,Rightarrow, nequiv -1,,$ i.e. $,n,$ is the inverse of the product $36= 5cdot 7$ of all the other moduli. Thus the common CRT formula.
The innate algebraic structure will be clarified if you later study abstract algebra, where you will learn the ring theoretic view of CRT, and vector spaces and modules.
answered Jan 31 at 17:57
Bill DubuqueBill Dubuque
214k29196655
$endgroup$
add a comment |
$begingroup$
Taking Bill Dubuque's graphic answer and graphically expanding on it:
$x = 2 cdotoverbrace{ (5 cdot 7) cdot 2}^{equiv 1 pmod 3\ equiv 0 pmod 5\ equiv 0 pmod 7} + 3 cdot overbrace{(3 cdot 7) cdot 1}^{equiv 0 pmod 3\ equiv 1 pmod 5\ equiv 0 pmod 7} + 2 cdot overbrace{(3 cdot 5) cdot 1}^{equiv 0 pmod 3\ equiv 0 pmod 5\ equiv 1pmod 7}= overbrace{233}^{equiv 2 + 0 +0pmod 3\ equiv0+3+0 pmod 5\ equiv 0+0+2pmod 7}$
======
Think about what you, yourself just stated.
If take this sum $x = 2 cdot (5 cdot 7) cdot 2 + 3 cdot (3 cdot 7) cdot 1 + 2 cdot (3 cdot 5) cdot 1$ and $mod 3$ it, then $(5cdot 7)$ and $2$ are inverses so $2cdot[(5cdot 7)cdot 2]pmod 3equiv 2cdot 1pmod 3 equiv 2 pmod 3$. ANd the other terms are multiples of $3$ so they are $equiv 0 pmod 3$. So $xequiv 2 pmod 3$.
If you take that term $x = 2 cdot (5 cdot 7) cdot 2 + 3 cdot (3 cdot 7) cdot 1 + 2 cdot (3 cdot 5) cdot 1$ and $mod 5$ it, then $3cdot 7$ and $1$ are inverses so $3cdot[(3cdot 7) cdot 1] equiv 3 cdot 1 equiv 3 pmod 5$. ANd the other terms are multiples of $5$. So the sum $x equiv 3 pmod 5$.
And so on.
....
If you want to solve
$x equiv a pmod m$
$x equiv b pmod n$
$x equiv c pmod v$ then
And assuming you were able find $(nv)^{-1}mod m; (mv)^{-1}mod n; $and $(nm)^{-1}mod v$
Then Let $K = a(nv)^{-1}(nv) + b (mv)^{-1}(mv) + c(nm)^{-1}(nm)$
Note: $K pmod m equiv$
$a(nv)^{-1}(nv) + b (mv)^{-1}(mv) + c(nm)^{-1}(nm)pmod mequiv$
$a*1 + [b(mv)^{-1}v]m + [c(nm)^{-1}n]m pmod mequiv$
$a*1 + 0 + 0 equiv apmod m$.
And likewise:
$K pmod n equiv$
$a(nv)^{-1}(nv) + b (mv)^{-1}(mv) + c(nm)^{-1}(nm)pmod nequiv$
$[a(nv)^{-1}v]n + b*1 + [c(nm)^{-1}m]n pmod nequiv$
$0 + b*1 + 0 equiv bpmod n$.
And
$a(nv)^{-1}(nv) + b (mv)^{-1}(mv) + c(nm)^{-1}(nm)pmod vequiv$
$[a(nv)^-1n]v + [b(mv)^{-1}m]v + c*1 pmod vequiv$
$0 + 0 + c equiv cpmod m$.
So $K$ is A solution.
If $m,n,v$ are pairwise relative prime then $K$ is a unique solution upto $mod nmv$.
answered Jan 31 at 18:01
fleabloodfleablood
73.8k22891
$endgroup$
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%2f3095169%2fmodular-arithmetic-method-for-solving-equations%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
$begingroup$
This is a generalisation of the formula for the solutions of a system of two congruences modulo two coprime numbers $a$ and $b$?. This formula uses a Bézout's relation: $;ua+vb=1$ and it is:
$$begin{cases}
xequiv alphamod a,\
xequiv betamod b,
end{cases}
quadtext{which is }qquad xequiv beta ua+alpha vbmod ab$$
Indeed we have $;beta ua+alpha vbequiv alpha vbequiv alphamod a$ since hand $;vbequiv 1mod a$. Similarly modulo $b$.
Now, as $v equiv b^{-1}bmod a:$ and $;uequiv a^{-1}bmod b$, this formula can be written as
$$xequiv beta, a (a^{-1}bmod b)+alpha, b(b^{-1}bmod a)mod ab.$$
answered Jan 31 at 17:41
BernardBernard
124k741117
$endgroup$
$begingroup$
The brave anonymous downvoter struck again!
$endgroup$
– Bernard
Feb 1 at 20:47
add a comment |
$begingroup$
This is a generalisation of the formula for the solutions of a system of two congruences modulo two coprime numbers $a$ and $b$?. This formula uses a Bézout's relation: $;ua+vb=1$ and it is:
$$begin{cases}
xequiv alphamod a,\
xequiv betamod b,
end{cases}
quadtext{which is }qquad xequiv beta ua+alpha vbmod ab$$
Indeed we have $;beta ua+alpha vbequiv alpha vbequiv alphamod a$ since hand $;vbequiv 1mod a$. Similarly modulo $b$.
Now, as $v equiv b^{-1}bmod a:$ and $;uequiv a^{-1}bmod b$, this formula can be written as
$$xequiv beta, a (a^{-1}bmod b)+alpha, b(b^{-1}bmod a)mod ab.$$
answered Jan 31 at 17:41
BernardBernard
124k741117
$endgroup$
$begingroup$
The brave anonymous downvoter struck again!
$endgroup$
– Bernard
Feb 1 at 20:47
add a comment |
$begingroup$
This is a generalisation of the formula for the solutions of a system of two congruences modulo two coprime numbers $a$ and $b$?. This formula uses a Bézout's relation: $;ua+vb=1$ and it is:
$$begin{cases}
xequiv alphamod a,\
xequiv betamod b,
end{cases}
quadtext{which is }qquad xequiv beta ua+alpha vbmod ab$$
Indeed we have $;beta ua+alpha vbequiv alpha vbequiv alphamod a$ since hand $;vbequiv 1mod a$. Similarly modulo $b$.
Now, as $v equiv b^{-1}bmod a:$ and $;uequiv a^{-1}bmod b$, this formula can be written as
$$xequiv beta, a (a^{-1}bmod b)+alpha, b(b^{-1}bmod a)mod ab.$$
answered Jan 31 at 17:41
BernardBernard
124k741117
$endgroup$
This is a generalisation of the formula for the solutions of a system of two congruences modulo two coprime numbers $a$ and $b$?. This formula uses a Bézout's relation: $;ua+vb=1$ and it is:
$$begin{cases}
xequiv alphamod a,\
xequiv betamod b,
end{cases}
quadtext{which is }qquad xequiv beta ua+alpha vbmod ab$$
Indeed we have $;beta ua+alpha vbequiv alpha vbequiv alphamod a$ since hand $;vbequiv 1mod a$. Similarly modulo $b$.
Now, as $v equiv b^{-1}bmod a:$ and $;uequiv a^{-1}bmod b$, this formula can be written as
$$xequiv beta, a (a^{-1}bmod b)+alpha, b(b^{-1}bmod a)mod ab.$$
answered Jan 31 at 17:41
BernardBernard
124k741117
answered Jan 31 at 17:41
BernardBernard
124k741117
answered Jan 31 at 17:41
BernardBernard
124k741117
answered Jan 31 at 17:41
BernardBernard
124k741117
124k741117
$begingroup$
The brave anonymous downvoter struck again!
$endgroup$
– Bernard
Feb 1 at 20:47
add a comment |
$begingroup$
The brave anonymous downvoter struck again!
$endgroup$
– Bernard
Feb 1 at 20:47
$begingroup$
The brave anonymous downvoter struck again!
$endgroup$
– Bernard
Feb 1 at 20:47
$begingroup$
The brave anonymous downvoter struck again!
$endgroup$
– Bernard
Feb 1 at 20:47
add a comment |
$begingroup$
It helps to highlught linearity at the heart of the Chinese Remainder Theorem [CRT] formula.
$$begin{eqnarray}
x, = &a&!color{#0a0}{overbrace{(-5cdot 7)}^{large equiv, 1 ({rm mod} color{#c00}3)}} ,+, &b& overbrace{(color{#c00}3cdot 7)}^{large equiv, 1 ({rm mod} 5)}, +, &c&overbrace{(color{#c00}3cdot 5)}^{large equiv, 1 ({rm mod} 7)}quad {bf [CRT]}\ \
Rightarrow x,equiv, &a& ({rm mod} color{#c00}3), xequiv &b& ({rm mod} 4), xequiv &c& ({rm mod} 5)\
end{eqnarray}$$
since, e.g. reduced $ $ mod $ color{#c00}3,,$ the 2nd and 3rd summands are $equiv 0,,$ both having factors of $,color{#c00}3.,$
The key idea is that the braced terms are $equiv 1$ mod one modulus, and $equiv 0 $ mod all others. More clearly, if we write the system in vector form $ xequiv (a,b,c),$ mod $,(3,5,7)$ then $rm,[CRT]$ becomes
$qquad x, :=, a,color{#0a0}{(1,0,0)} + b,(0,1,0) + c,(0,0,1)equiv (a.b,c) $ as desired. $qquad [bf Linearity]$
by the green term $,color{#0a0}{g equiv 1} ({rm mod} 3), color{#0a0}{gequiv 0} ({rm mod} 5), color{#0a0}{gequiv 0} ({rm mod} 7), $ i.e. $ color{#0a0}{gequiv (1,0,0)} {rm mod} (3,5,7), $ and similarly for $,(0,1,0),$ and $,(0,0,1).$
Thus once we compute the solutions for the "basis" vectors $(1,0,0), (0,1,0), (0,0,1)$ we can exploit [Linearity] to generate the general solution as a linear combination of these basic solutions.
Solving the basic cases is easy: $,{color{#0a0}{5,7mid g},Rightarrow, 35mid g},, $ so $bmod 3!: color{#0a0}{1equiv g} equiv 35nequiv -n,Rightarrow, nequiv -1,,$ i.e. $,n,$ is the inverse of the product $36= 5cdot 7$ of all the other moduli. Thus the common CRT formula.
The innate algebraic structure will be clarified if you later study abstract algebra, where you will learn the ring theoretic view of CRT, and vector spaces and modules.
answered Jan 31 at 17:57
Bill DubuqueBill Dubuque
214k29196655
$endgroup$
add a comment |
$begingroup$
It helps to highlught linearity at the heart of the Chinese Remainder Theorem [CRT] formula.
$$begin{eqnarray}
x, = &a&!color{#0a0}{overbrace{(-5cdot 7)}^{large equiv, 1 ({rm mod} color{#c00}3)}} ,+, &b& overbrace{(color{#c00}3cdot 7)}^{large equiv, 1 ({rm mod} 5)}, +, &c&overbrace{(color{#c00}3cdot 5)}^{large equiv, 1 ({rm mod} 7)}quad {bf [CRT]}\ \
Rightarrow x,equiv, &a& ({rm mod} color{#c00}3), xequiv &b& ({rm mod} 4), xequiv &c& ({rm mod} 5)\
end{eqnarray}$$
since, e.g. reduced $ $ mod $ color{#c00}3,,$ the 2nd and 3rd summands are $equiv 0,,$ both having factors of $,color{#c00}3.,$
The key idea is that the braced terms are $equiv 1$ mod one modulus, and $equiv 0 $ mod all others. More clearly, if we write the system in vector form $ xequiv (a,b,c),$ mod $,(3,5,7)$ then $rm,[CRT]$ becomes
$qquad x, :=, a,color{#0a0}{(1,0,0)} + b,(0,1,0) + c,(0,0,1)equiv (a.b,c) $ as desired. $qquad [bf Linearity]$
by the green term $,color{#0a0}{g equiv 1} ({rm mod} 3), color{#0a0}{gequiv 0} ({rm mod} 5), color{#0a0}{gequiv 0} ({rm mod} 7), $ i.e. $ color{#0a0}{gequiv (1,0,0)} {rm mod} (3,5,7), $ and similarly for $,(0,1,0),$ and $,(0,0,1).$
Thus once we compute the solutions for the "basis" vectors $(1,0,0), (0,1,0), (0,0,1)$ we can exploit [Linearity] to generate the general solution as a linear combination of these basic solutions.
Solving the basic cases is easy: $,{color{#0a0}{5,7mid g},Rightarrow, 35mid g},, $ so $bmod 3!: color{#0a0}{1equiv g} equiv 35nequiv -n,Rightarrow, nequiv -1,,$ i.e. $,n,$ is the inverse of the product $36= 5cdot 7$ of all the other moduli. Thus the common CRT formula.
The innate algebraic structure will be clarified if you later study abstract algebra, where you will learn the ring theoretic view of CRT, and vector spaces and modules.
answered Jan 31 at 17:57
Bill DubuqueBill Dubuque
214k29196655
$endgroup$
add a comment |
$begingroup$
It helps to highlught linearity at the heart of the Chinese Remainder Theorem [CRT] formula.
$$begin{eqnarray}
x, = &a&!color{#0a0}{overbrace{(-5cdot 7)}^{large equiv, 1 ({rm mod} color{#c00}3)}} ,+, &b& overbrace{(color{#c00}3cdot 7)}^{large equiv, 1 ({rm mod} 5)}, +, &c&overbrace{(color{#c00}3cdot 5)}^{large equiv, 1 ({rm mod} 7)}quad {bf [CRT]}\ \
Rightarrow x,equiv, &a& ({rm mod} color{#c00}3), xequiv &b& ({rm mod} 4), xequiv &c& ({rm mod} 5)\
end{eqnarray}$$
since, e.g. reduced $ $ mod $ color{#c00}3,,$ the 2nd and 3rd summands are $equiv 0,,$ both having factors of $,color{#c00}3.,$
The key idea is that the braced terms are $equiv 1$ mod one modulus, and $equiv 0 $ mod all others. More clearly, if we write the system in vector form $ xequiv (a,b,c),$ mod $,(3,5,7)$ then $rm,[CRT]$ becomes
$qquad x, :=, a,color{#0a0}{(1,0,0)} + b,(0,1,0) + c,(0,0,1)equiv (a.b,c) $ as desired. $qquad [bf Linearity]$
by the green term $,color{#0a0}{g equiv 1} ({rm mod} 3), color{#0a0}{gequiv 0} ({rm mod} 5), color{#0a0}{gequiv 0} ({rm mod} 7), $ i.e. $ color{#0a0}{gequiv (1,0,0)} {rm mod} (3,5,7), $ and similarly for $,(0,1,0),$ and $,(0,0,1).$
Thus once we compute the solutions for the "basis" vectors $(1,0,0), (0,1,0), (0,0,1)$ we can exploit [Linearity] to generate the general solution as a linear combination of these basic solutions.
Solving the basic cases is easy: $,{color{#0a0}{5,7mid g},Rightarrow, 35mid g},, $ so $bmod 3!: color{#0a0}{1equiv g} equiv 35nequiv -n,Rightarrow, nequiv -1,,$ i.e. $,n,$ is the inverse of the product $36= 5cdot 7$ of all the other moduli. Thus the common CRT formula.
The innate algebraic structure will be clarified if you later study abstract algebra, where you will learn the ring theoretic view of CRT, and vector spaces and modules.
answered Jan 31 at 17:57
Bill DubuqueBill Dubuque
214k29196655
$endgroup$
It helps to highlught linearity at the heart of the Chinese Remainder Theorem [CRT] formula.
$$begin{eqnarray}
x, = &a&!color{#0a0}{overbrace{(-5cdot 7)}^{large equiv, 1 ({rm mod} color{#c00}3)}} ,+, &b& overbrace{(color{#c00}3cdot 7)}^{large equiv, 1 ({rm mod} 5)}, +, &c&overbrace{(color{#c00}3cdot 5)}^{large equiv, 1 ({rm mod} 7)}quad {bf [CRT]}\ \
Rightarrow x,equiv, &a& ({rm mod} color{#c00}3), xequiv &b& ({rm mod} 4), xequiv &c& ({rm mod} 5)\
end{eqnarray}$$
since, e.g. reduced $ $ mod $ color{#c00}3,,$ the 2nd and 3rd summands are $equiv 0,,$ both having factors of $,color{#c00}3.,$
The key idea is that the braced terms are $equiv 1$ mod one modulus, and $equiv 0 $ mod all others. More clearly, if we write the system in vector form $ xequiv (a,b,c),$ mod $,(3,5,7)$ then $rm,[CRT]$ becomes
$qquad x, :=, a,color{#0a0}{(1,0,0)} + b,(0,1,0) + c,(0,0,1)equiv (a.b,c) $ as desired. $qquad [bf Linearity]$
by the green term $,color{#0a0}{g equiv 1} ({rm mod} 3), color{#0a0}{gequiv 0} ({rm mod} 5), color{#0a0}{gequiv 0} ({rm mod} 7), $ i.e. $ color{#0a0}{gequiv (1,0,0)} {rm mod} (3,5,7), $ and similarly for $,(0,1,0),$ and $,(0,0,1).$
Thus once we compute the solutions for the "basis" vectors $(1,0,0), (0,1,0), (0,0,1)$ we can exploit [Linearity] to generate the general solution as a linear combination of these basic solutions.
Solving the basic cases is easy: $,{color{#0a0}{5,7mid g},Rightarrow, 35mid g},, $ so $bmod 3!: color{#0a0}{1equiv g} equiv 35nequiv -n,Rightarrow, nequiv -1,,$ i.e. $,n,$ is the inverse of the product $36= 5cdot 7$ of all the other moduli. Thus the common CRT formula.
The innate algebraic structure will be clarified if you later study abstract algebra, where you will learn the ring theoretic view of CRT, and vector spaces and modules.
answered Jan 31 at 17:57
Bill DubuqueBill Dubuque
214k29196655
edited Jan 31 at 18:32
answered Jan 31 at 17:57
Bill DubuqueBill Dubuque
214k29196655
answered Jan 31 at 17:57
Bill DubuqueBill Dubuque
214k29196655
answered Jan 31 at 17:57
Bill DubuqueBill Dubuque
214k29196655
214k29196655
add a comment |
add a comment |
$begingroup$
Taking Bill Dubuque's graphic answer and graphically expanding on it:
$x = 2 cdotoverbrace{ (5 cdot 7) cdot 2}^{equiv 1 pmod 3\ equiv 0 pmod 5\ equiv 0 pmod 7} + 3 cdot overbrace{(3 cdot 7) cdot 1}^{equiv 0 pmod 3\ equiv 1 pmod 5\ equiv 0 pmod 7} + 2 cdot overbrace{(3 cdot 5) cdot 1}^{equiv 0 pmod 3\ equiv 0 pmod 5\ equiv 1pmod 7}= overbrace{233}^{equiv 2 + 0 +0pmod 3\ equiv0+3+0 pmod 5\ equiv 0+0+2pmod 7}$
======
Think about what you, yourself just stated.
If take this sum $x = 2 cdot (5 cdot 7) cdot 2 + 3 cdot (3 cdot 7) cdot 1 + 2 cdot (3 cdot 5) cdot 1$ and $mod 3$ it, then $(5cdot 7)$ and $2$ are inverses so $2cdot[(5cdot 7)cdot 2]pmod 3equiv 2cdot 1pmod 3 equiv 2 pmod 3$. ANd the other terms are multiples of $3$ so they are $equiv 0 pmod 3$. So $xequiv 2 pmod 3$.
If you take that term $x = 2 cdot (5 cdot 7) cdot 2 + 3 cdot (3 cdot 7) cdot 1 + 2 cdot (3 cdot 5) cdot 1$ and $mod 5$ it, then $3cdot 7$ and $1$ are inverses so $3cdot[(3cdot 7) cdot 1] equiv 3 cdot 1 equiv 3 pmod 5$. ANd the other terms are multiples of $5$. So the sum $x equiv 3 pmod 5$.
And so on.
....
If you want to solve
$x equiv a pmod m$
$x equiv b pmod n$
$x equiv c pmod v$ then
And assuming you were able find $(nv)^{-1}mod m; (mv)^{-1}mod n; $and $(nm)^{-1}mod v$
Then Let $K = a(nv)^{-1}(nv) + b (mv)^{-1}(mv) + c(nm)^{-1}(nm)$
Note: $K pmod m equiv$
$a(nv)^{-1}(nv) + b (mv)^{-1}(mv) + c(nm)^{-1}(nm)pmod mequiv$
$a*1 + [b(mv)^{-1}v]m + [c(nm)^{-1}n]m pmod mequiv$
$a*1 + 0 + 0 equiv apmod m$.
And likewise:
$K pmod n equiv$
$a(nv)^{-1}(nv) + b (mv)^{-1}(mv) + c(nm)^{-1}(nm)pmod nequiv$
$[a(nv)^{-1}v]n + b*1 + [c(nm)^{-1}m]n pmod nequiv$
$0 + b*1 + 0 equiv bpmod n$.
And
$a(nv)^{-1}(nv) + b (mv)^{-1}(mv) + c(nm)^{-1}(nm)pmod vequiv$
$[a(nv)^-1n]v + [b(mv)^{-1}m]v + c*1 pmod vequiv$
$0 + 0 + c equiv cpmod m$.
So $K$ is A solution.
If $m,n,v$ are pairwise relative prime then $K$ is a unique solution upto $mod nmv$.
answered Jan 31 at 18:01
fleabloodfleablood
73.8k22891
$endgroup$
add a comment |
$begingroup$
Taking Bill Dubuque's graphic answer and graphically expanding on it:
$x = 2 cdotoverbrace{ (5 cdot 7) cdot 2}^{equiv 1 pmod 3\ equiv 0 pmod 5\ equiv 0 pmod 7} + 3 cdot overbrace{(3 cdot 7) cdot 1}^{equiv 0 pmod 3\ equiv 1 pmod 5\ equiv 0 pmod 7} + 2 cdot overbrace{(3 cdot 5) cdot 1}^{equiv 0 pmod 3\ equiv 0 pmod 5\ equiv 1pmod 7}= overbrace{233}^{equiv 2 + 0 +0pmod 3\ equiv0+3+0 pmod 5\ equiv 0+0+2pmod 7}$
======
Think about what you, yourself just stated.
If take this sum $x = 2 cdot (5 cdot 7) cdot 2 + 3 cdot (3 cdot 7) cdot 1 + 2 cdot (3 cdot 5) cdot 1$ and $mod 3$ it, then $(5cdot 7)$ and $2$ are inverses so $2cdot[(5cdot 7)cdot 2]pmod 3equiv 2cdot 1pmod 3 equiv 2 pmod 3$. ANd the other terms are multiples of $3$ so they are $equiv 0 pmod 3$. So $xequiv 2 pmod 3$.
If you take that term $x = 2 cdot (5 cdot 7) cdot 2 + 3 cdot (3 cdot 7) cdot 1 + 2 cdot (3 cdot 5) cdot 1$ and $mod 5$ it, then $3cdot 7$ and $1$ are inverses so $3cdot[(3cdot 7) cdot 1] equiv 3 cdot 1 equiv 3 pmod 5$. ANd the other terms are multiples of $5$. So the sum $x equiv 3 pmod 5$.
And so on.
....
If you want to solve
$x equiv a pmod m$
$x equiv b pmod n$
$x equiv c pmod v$ then
And assuming you were able find $(nv)^{-1}mod m; (mv)^{-1}mod n; $and $(nm)^{-1}mod v$
Then Let $K = a(nv)^{-1}(nv) + b (mv)^{-1}(mv) + c(nm)^{-1}(nm)$
Note: $K pmod m equiv$
$a(nv)^{-1}(nv) + b (mv)^{-1}(mv) + c(nm)^{-1}(nm)pmod mequiv$
$a*1 + [b(mv)^{-1}v]m + [c(nm)^{-1}n]m pmod mequiv$
$a*1 + 0 + 0 equiv apmod m$.
And likewise:
$K pmod n equiv$
$a(nv)^{-1}(nv) + b (mv)^{-1}(mv) + c(nm)^{-1}(nm)pmod nequiv$
$[a(nv)^{-1}v]n + b*1 + [c(nm)^{-1}m]n pmod nequiv$
$0 + b*1 + 0 equiv bpmod n$.
And
$a(nv)^{-1}(nv) + b (mv)^{-1}(mv) + c(nm)^{-1}(nm)pmod vequiv$
$[a(nv)^-1n]v + [b(mv)^{-1}m]v + c*1 pmod vequiv$
$0 + 0 + c equiv cpmod m$.
So $K$ is A solution.
If $m,n,v$ are pairwise relative prime then $K$ is a unique solution upto $mod nmv$.
answered Jan 31 at 18:01
fleabloodfleablood
73.8k22891
$endgroup$
add a comment |
$begingroup$
Taking Bill Dubuque's graphic answer and graphically expanding on it:
$x = 2 cdotoverbrace{ (5 cdot 7) cdot 2}^{equiv 1 pmod 3\ equiv 0 pmod 5\ equiv 0 pmod 7} + 3 cdot overbrace{(3 cdot 7) cdot 1}^{equiv 0 pmod 3\ equiv 1 pmod 5\ equiv 0 pmod 7} + 2 cdot overbrace{(3 cdot 5) cdot 1}^{equiv 0 pmod 3\ equiv 0 pmod 5\ equiv 1pmod 7}= overbrace{233}^{equiv 2 + 0 +0pmod 3\ equiv0+3+0 pmod 5\ equiv 0+0+2pmod 7}$
======
Think about what you, yourself just stated.
If take this sum $x = 2 cdot (5 cdot 7) cdot 2 + 3 cdot (3 cdot 7) cdot 1 + 2 cdot (3 cdot 5) cdot 1$ and $mod 3$ it, then $(5cdot 7)$ and $2$ are inverses so $2cdot[(5cdot 7)cdot 2]pmod 3equiv 2cdot 1pmod 3 equiv 2 pmod 3$. ANd the other terms are multiples of $3$ so they are $equiv 0 pmod 3$. So $xequiv 2 pmod 3$.
If you take that term $x = 2 cdot (5 cdot 7) cdot 2 + 3 cdot (3 cdot 7) cdot 1 + 2 cdot (3 cdot 5) cdot 1$ and $mod 5$ it, then $3cdot 7$ and $1$ are inverses so $3cdot[(3cdot 7) cdot 1] equiv 3 cdot 1 equiv 3 pmod 5$. ANd the other terms are multiples of $5$. So the sum $x equiv 3 pmod 5$.
And so on.
....
If you want to solve
$x equiv a pmod m$
$x equiv b pmod n$
$x equiv c pmod v$ then
And assuming you were able find $(nv)^{-1}mod m; (mv)^{-1}mod n; $and $(nm)^{-1}mod v$
Then Let $K = a(nv)^{-1}(nv) + b (mv)^{-1}(mv) + c(nm)^{-1}(nm)$
Note: $K pmod m equiv$
$a(nv)^{-1}(nv) + b (mv)^{-1}(mv) + c(nm)^{-1}(nm)pmod mequiv$
$a*1 + [b(mv)^{-1}v]m + [c(nm)^{-1}n]m pmod mequiv$
$a*1 + 0 + 0 equiv apmod m$.
And likewise:
$K pmod n equiv$
$a(nv)^{-1}(nv) + b (mv)^{-1}(mv) + c(nm)^{-1}(nm)pmod nequiv$
$[a(nv)^{-1}v]n + b*1 + [c(nm)^{-1}m]n pmod nequiv$
$0 + b*1 + 0 equiv bpmod n$.
And
$a(nv)^{-1}(nv) + b (mv)^{-1}(mv) + c(nm)^{-1}(nm)pmod vequiv$
$[a(nv)^-1n]v + [b(mv)^{-1}m]v + c*1 pmod vequiv$
$0 + 0 + c equiv cpmod m$.
So $K$ is A solution.
If $m,n,v$ are pairwise relative prime then $K$ is a unique solution upto $mod nmv$.
answered Jan 31 at 18:01
fleabloodfleablood
73.8k22891
$endgroup$
Taking Bill Dubuque's graphic answer and graphically expanding on it:
$x = 2 cdotoverbrace{ (5 cdot 7) cdot 2}^{equiv 1 pmod 3\ equiv 0 pmod 5\ equiv 0 pmod 7} + 3 cdot overbrace{(3 cdot 7) cdot 1}^{equiv 0 pmod 3\ equiv 1 pmod 5\ equiv 0 pmod 7} + 2 cdot overbrace{(3 cdot 5) cdot 1}^{equiv 0 pmod 3\ equiv 0 pmod 5\ equiv 1pmod 7}= overbrace{233}^{equiv 2 + 0 +0pmod 3\ equiv0+3+0 pmod 5\ equiv 0+0+2pmod 7}$
======
Think about what you, yourself just stated.
If take this sum $x = 2 cdot (5 cdot 7) cdot 2 + 3 cdot (3 cdot 7) cdot 1 + 2 cdot (3 cdot 5) cdot 1$ and $mod 3$ it, then $(5cdot 7)$ and $2$ are inverses so $2cdot[(5cdot 7)cdot 2]pmod 3equiv 2cdot 1pmod 3 equiv 2 pmod 3$. ANd the other terms are multiples of $3$ so they are $equiv 0 pmod 3$. So $xequiv 2 pmod 3$.
If you take that term $x = 2 cdot (5 cdot 7) cdot 2 + 3 cdot (3 cdot 7) cdot 1 + 2 cdot (3 cdot 5) cdot 1$ and $mod 5$ it, then $3cdot 7$ and $1$ are inverses so $3cdot[(3cdot 7) cdot 1] equiv 3 cdot 1 equiv 3 pmod 5$. ANd the other terms are multiples of $5$. So the sum $x equiv 3 pmod 5$.
And so on.
....
If you want to solve
$x equiv a pmod m$
$x equiv b pmod n$
$x equiv c pmod v$ then
And assuming you were able find $(nv)^{-1}mod m; (mv)^{-1}mod n; $and $(nm)^{-1}mod v$
Then Let $K = a(nv)^{-1}(nv) + b (mv)^{-1}(mv) + c(nm)^{-1}(nm)$
Note: $K pmod m equiv$
$a(nv)^{-1}(nv) + b (mv)^{-1}(mv) + c(nm)^{-1}(nm)pmod mequiv$
$a*1 + [b(mv)^{-1}v]m + [c(nm)^{-1}n]m pmod mequiv$
$a*1 + 0 + 0 equiv apmod m$.
And likewise:
$K pmod n equiv$
$a(nv)^{-1}(nv) + b (mv)^{-1}(mv) + c(nm)^{-1}(nm)pmod nequiv$
$[a(nv)^{-1}v]n + b*1 + [c(nm)^{-1}m]n pmod nequiv$
$0 + b*1 + 0 equiv bpmod n$.
And
$a(nv)^{-1}(nv) + b (mv)^{-1}(mv) + c(nm)^{-1}(nm)pmod vequiv$
$[a(nv)^-1n]v + [b(mv)^{-1}m]v + c*1 pmod vequiv$
$0 + 0 + c equiv cpmod m$.
So $K$ is A solution.
If $m,n,v$ are pairwise relative prime then $K$ is a unique solution upto $mod nmv$.
answered Jan 31 at 18:01
fleabloodfleablood
73.8k22891
edited Jan 31 at 18:38
answered Jan 31 at 18:01
fleabloodfleablood
73.8k22891
answered Jan 31 at 18:01
fleabloodfleablood
73.8k22891
answered Jan 31 at 18:01
fleabloodfleablood
73.8k22891
73.8k22891
add a comment |
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.
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%2f3095169%2fmodular-arithmetic-method-for-solving-equations%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
$begingroup$
It's not clear which part proves troublesome. Often it is the linearity that I describe in my answer. If it is something else then please elaborate and I can add further details.
$endgroup$
– Bill Dubuque
Jan 31 at 18:19