Mixing
How to apply CRT to this congruence system?
$begingroup$
$x=1 pmod 8$
$x=5 pmod{12}$
8 and 12 are not coprime, I could break it to:
$x=1 pmod 2$
$x=1 pmod 4$
and
$x=5 pmod 3$
$x=5 pmod 4$
But what are the next steps to solve it? By the way, $x$ should be $17$ not sure how to get that number ...
Thanks in advance.
number-theory prime-numbers modular-arithmetic
edited Jan 16 at 15:58
Bernard
121k740116
asked Jan 16 at 14:50
Igor Igor
63
$endgroup$
add a comment |
$begingroup$
$x=1 pmod 8$
$x=5 pmod{12}$
8 and 12 are not coprime, I could break it to:
$x=1 pmod 2$
$x=1 pmod 4$
and
$x=5 pmod 3$
$x=5 pmod 4$
But what are the next steps to solve it? By the way, $x$ should be $17$ not sure how to get that number ...
Thanks in advance.
number-theory prime-numbers modular-arithmetic
edited Jan 16 at 15:58
Bernard
121k740116
asked Jan 16 at 14:50
Igor Igor
63
$endgroup$
$begingroup$
Do you mean CRT (the Chinese Remainder Theorem)?
$endgroup$
– Théophile
Jan 16 at 14:50
$begingroup$
@Théophile Yes indeed, I edited the title of the question.
$endgroup$
– Igor
Jan 16 at 14:52
1
$begingroup$
$12 = nm, n=3,m=4,gcd(n,m)=1$ so $x equiv 5 bmod nm$ iff $x equiv 5 bmod n,x equiv 5 bmod m$. In the opposite direction when you have $x equiv a bmod n,x equiv b bmod m$ the goal is to find $c = un+vm$ such that it becomes $x equiv c bmod nm$
$endgroup$
– reuns
Jan 16 at 14:57
$begingroup$
Rewrite your system as $xequiv 1pmod 8$ and $xequiv 2pmod 3$.
$endgroup$
– lulu
Jan 16 at 15:11
$begingroup$
Um.... you haven't actually stated what the question is you are trying to answer? I assume it is what is the smallest such value of $x$ or what is $x pmod {24}$. But you haven't said it.
$endgroup$
– fleablood
Jan 16 at 16:24
add a comment |
$begingroup$
$x=1 pmod 8$
$x=5 pmod{12}$
8 and 12 are not coprime, I could break it to:
$x=1 pmod 2$
$x=1 pmod 4$
and
$x=5 pmod 3$
$x=5 pmod 4$
But what are the next steps to solve it? By the way, $x$ should be $17$ not sure how to get that number ...
Thanks in advance.
number-theory prime-numbers modular-arithmetic
edited Jan 16 at 15:58
Bernard
121k740116
asked Jan 16 at 14:50
Igor Igor
63
$endgroup$
$x=1 pmod 8$
$x=5 pmod{12}$
8 and 12 are not coprime, I could break it to:
$x=1 pmod 2$
$x=1 pmod 4$
and
$x=5 pmod 3$
$x=5 pmod 4$
But what are the next steps to solve it? By the way, $x$ should be $17$ not sure how to get that number ...
Thanks in advance.
number-theory prime-numbers modular-arithmetic
number-theory prime-numbers modular-arithmetic
edited Jan 16 at 15:58
Bernard
121k740116
asked Jan 16 at 14:50
Igor Igor
63
edited Jan 16 at 15:58
Bernard
121k740116
asked Jan 16 at 14:50
Igor Igor
63
edited Jan 16 at 15:58
Bernard
121k740116
edited Jan 16 at 15:58
Bernard
121k740116
edited Jan 16 at 15:58
Bernard
121k740116
121k740116
asked Jan 16 at 14:50
Igor Igor
63
asked Jan 16 at 14:50
Igor Igor
63
asked Jan 16 at 14:50
Igor Igor
63
63
$begingroup$
Do you mean CRT (the Chinese Remainder Theorem)?
$endgroup$
– Théophile
Jan 16 at 14:50
$begingroup$
@Théophile Yes indeed, I edited the title of the question.
$endgroup$
– Igor
Jan 16 at 14:52
1
$begingroup$
$12 = nm, n=3,m=4,gcd(n,m)=1$ so $x equiv 5 bmod nm$ iff $x equiv 5 bmod n,x equiv 5 bmod m$. In the opposite direction when you have $x equiv a bmod n,x equiv b bmod m$ the goal is to find $c = un+vm$ such that it becomes $x equiv c bmod nm$
$endgroup$
– reuns
Jan 16 at 14:57
$begingroup$
Rewrite your system as $xequiv 1pmod 8$ and $xequiv 2pmod 3$.
$endgroup$
– lulu
Jan 16 at 15:11
$begingroup$
Um.... you haven't actually stated what the question is you are trying to answer? I assume it is what is the smallest such value of $x$ or what is $x pmod {24}$. But you haven't said it.
$endgroup$
– fleablood
Jan 16 at 16:24
add a comment |
$begingroup$
Do you mean CRT (the Chinese Remainder Theorem)?
$endgroup$
– Théophile
Jan 16 at 14:50
$begingroup$
@Théophile Yes indeed, I edited the title of the question.
$endgroup$
– Igor
Jan 16 at 14:52
1
$begingroup$
$12 = nm, n=3,m=4,gcd(n,m)=1$ so $x equiv 5 bmod nm$ iff $x equiv 5 bmod n,x equiv 5 bmod m$. In the opposite direction when you have $x equiv a bmod n,x equiv b bmod m$ the goal is to find $c = un+vm$ such that it becomes $x equiv c bmod nm$
$endgroup$
– reuns
Jan 16 at 14:57
$begingroup$
Rewrite your system as $xequiv 1pmod 8$ and $xequiv 2pmod 3$.
$endgroup$
– lulu
Jan 16 at 15:11
$begingroup$
Um.... you haven't actually stated what the question is you are trying to answer? I assume it is what is the smallest such value of $x$ or what is $x pmod {24}$. But you haven't said it.
$endgroup$
– fleablood
Jan 16 at 16:24
$begingroup$
Do you mean CRT (the Chinese Remainder Theorem)?
$endgroup$
– Théophile
Jan 16 at 14:50
$begingroup$
Do you mean CRT (the Chinese Remainder Theorem)?
$endgroup$
– Théophile
Jan 16 at 14:50
$begingroup$
@Théophile Yes indeed, I edited the title of the question.
$endgroup$
– Igor
Jan 16 at 14:52
$begingroup$
@Théophile Yes indeed, I edited the title of the question.
$endgroup$
– Igor
Jan 16 at 14:52
1
1
$begingroup$
$12 = nm, n=3,m=4,gcd(n,m)=1$ so $x equiv 5 bmod nm$ iff $x equiv 5 bmod n,x equiv 5 bmod m$. In the opposite direction when you have $x equiv a bmod n,x equiv b bmod m$ the goal is to find $c = un+vm$ such that it becomes $x equiv c bmod nm$
$endgroup$
– reuns
Jan 16 at 14:57
$begingroup$
$12 = nm, n=3,m=4,gcd(n,m)=1$ so $x equiv 5 bmod nm$ iff $x equiv 5 bmod n,x equiv 5 bmod m$. In the opposite direction when you have $x equiv a bmod n,x equiv b bmod m$ the goal is to find $c = un+vm$ such that it becomes $x equiv c bmod nm$
$endgroup$
– reuns
Jan 16 at 14:57
$begingroup$
Rewrite your system as $xequiv 1pmod 8$ and $xequiv 2pmod 3$.
$endgroup$
– lulu
Jan 16 at 15:11
$begingroup$
Rewrite your system as $xequiv 1pmod 8$ and $xequiv 2pmod 3$.
$endgroup$
– lulu
Jan 16 at 15:11
$begingroup$
Um.... you haven't actually stated what the question is you are trying to answer? I assume it is what is the smallest such value of $x$ or what is $x pmod {24}$. But you haven't said it.
$endgroup$
– fleablood
Jan 16 at 16:24
$begingroup$
Um.... you haven't actually stated what the question is you are trying to answer? I assume it is what is the smallest such value of $x$ or what is $x pmod {24}$. But you haven't said it.
$endgroup$
– fleablood
Jan 16 at 16:24
add a comment |
5 Answers
5
active
oldest
votes
$begingroup$
No point in figuring it out to any lesser power of $2$ than $2^3$.
Leave it at $xequiv 1 pmod 8$ but $x equiv 5 pmod {12}$ can be reduced to $xequiv 5 equiv 2 pmod 3$.
So CRT says there is a unique solution $pmod {28}$; $x equiv 17 pmod{24}$.
$x = A pmod {n_1}$ $(A = 1; n_1 = 8)$
$x = B pmod {n_2}$ $(B = 2; n_2 = 3)$
$m_1n_1 + m_2n_2 = 1$ (in this case $8m_1 + 3m_2 = 1$ so $m_1 =2; B=-5$ or $A=-1; B=3$ or .....)
Then $x = Am_2n_2 + Bn_1n_1pmod {n_1n_2}$.
$x = 1*(-5)*3 + 2*2*8= -15+32 = 17$.
There's utterly no point in reducing to $x equiv 5 pmod 4$ and $x equiv 5pmod 3$ as that will just get you back to $xequiv 2,5,8,11 pmod {12}$ and $x equiv 1,5 pmod 8$ which is worse than what you started with.
answered Jan 16 at 16:26
fleabloodfleablood
71.2k22686
$endgroup$
add a comment |
$begingroup$
Alternatively:
$$begin{cases}xequiv 1pmod{8}\ xequiv 5pmod{12}end{cases} Rightarrow begin{cases} x=8n+1\x=12m+5end{cases} Rightarrow 8n+1=12m+5 Rightarrow \
2n-3m=1 Rightarrow begin{cases}n=2+3k\m=1+2kend{cases} Rightarrow begin{cases} x=8(2+3k)\ x=12(1+2k)+5end{cases} Rightarrow \
x=24k+17 Rightarrow xequiv 17pmod{24}.$$
answered Jan 16 at 18:16
farruhotafarruhota
20.4k2739
$endgroup$
add a comment |
$begingroup$
Here is a way:
$$begin{cases}
xequiv 1pmod 8\xequiv 5pmod{12}
end{cases}iff begin{cases}
x -1equiv 0pmod 8\x -1equiv 4pmod{12}end{cases}iff
begin{cases}
frac{x -1}4equiv 0pmod 2\frac{x -1}4equiv 1pmod{3}
end{cases}$$
Now set $y=frac{x-1}4$. As $3-2=1$, the solutions of the last system of congruences is
$$ yequiv 0cdot 3- 1cdot 2 =-2pmod{6},$$
so that, multiplying by $4$,
$$x-1equiv -8 iff xequiv -7iff xequiv 17pmod{24}$$
answered Jan 16 at 16:10
BernardBernard
121k740116
$endgroup$
$begingroup$
This transformation happens quite naturally if we use the mod Distributive Law - see my answer.
$endgroup$
– Bill Dubuque
Jan 16 at 23:17
add a comment |
$begingroup$
The moduli gcd is $,d = (8,12) = 4,$ and $,4mid 5-1,$ so by CRT a solution uniquely exists mod ${rm lcm}(8,12) $ $ = 8(12)/4 = 24,,$ computable by $, abbmod ac = a(bbmod c) = $ $!bmod!$ Distributive Law.
$8mid x!-!1Rightarrow x!-!1bmod 24 = 8left[dfrac{color{#c00}x!-!1}8!bmod 3right] = 8left[dfrac{color{#c00}5!-!1}{2 }!bmod 3right]= 16, $ by $ begin{align}x&equiv 5 !!!pmod{!12}\ Rightarrow,color{#c00}x&equiv color{#c00}5!!!pmod{!3}end{align}$
Remark $ $ This works generally for $,xequiv apmod{!m}, xequiv bpmod{!n},$ when $,(m,n)=color{#0a0}{dmid b!-!a}$
$mmid x!-!a,Rightarrow,x!-!abmod mn/d = mleft[dfrac{x-a}mbmod n/dright] = mleft[dfrac{b-a}mbmod n/dright] $
Note $,dmid b!-!a,Rightarrow, dfrac{b-a}m = dfrac{color{#0a0}{(b-a)/d}}{m/d}$ and $,m/d,$ is invertible $!bmod n/d,$ by $,(m/d,n/d)= 1,,$ thus the fraction exists $bmod n/d$.
answered Jan 16 at 23:09
Bill DubuqueBill Dubuque
211k29193646
$endgroup$
add a comment |
$begingroup$
By CRT $,xequiv 5pmod{!12}!iff! xequiv 5pmod{!3},$ and $,color{#c00}{xequiv 5pmod{4}}$
But $,xequiv 1pmod{!8},Rightarrow,xequiv 1equiv 5pmod{!4},,$ hence $,color{#c00}{xequiv 5pmod{4}},$ is redundant, thus
$$begin{align} x&equiv 1!!pmod{8}\ x&equiv 5!!pmod{12}end{align}iff begin{array}{} xequiv 1 pmod{8}\ xequiv 5 pmod{3}end{array}qquad$$
so we have reduced it to a an equivalent system where the moduli are coprime. See my other answer for a convenient operational CRT method to solve (both!) of those congruence systems.
answered Jan 16 at 23:54
Bill DubuqueBill Dubuque
211k29193646
$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%2f3075823%2fhow-to-apply-crt-to-this-congruence-system%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
5 Answers
5
active
oldest
votes
5 Answers
5
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
No point in figuring it out to any lesser power of $2$ than $2^3$.
Leave it at $xequiv 1 pmod 8$ but $x equiv 5 pmod {12}$ can be reduced to $xequiv 5 equiv 2 pmod 3$.
So CRT says there is a unique solution $pmod {28}$; $x equiv 17 pmod{24}$.
$x = A pmod {n_1}$ $(A = 1; n_1 = 8)$
$x = B pmod {n_2}$ $(B = 2; n_2 = 3)$
$m_1n_1 + m_2n_2 = 1$ (in this case $8m_1 + 3m_2 = 1$ so $m_1 =2; B=-5$ or $A=-1; B=3$ or .....)
Then $x = Am_2n_2 + Bn_1n_1pmod {n_1n_2}$.
$x = 1*(-5)*3 + 2*2*8= -15+32 = 17$.
There's utterly no point in reducing to $x equiv 5 pmod 4$ and $x equiv 5pmod 3$ as that will just get you back to $xequiv 2,5,8,11 pmod {12}$ and $x equiv 1,5 pmod 8$ which is worse than what you started with.
answered Jan 16 at 16:26
fleabloodfleablood
71.2k22686
$endgroup$
add a comment |
$begingroup$
No point in figuring it out to any lesser power of $2$ than $2^3$.
Leave it at $xequiv 1 pmod 8$ but $x equiv 5 pmod {12}$ can be reduced to $xequiv 5 equiv 2 pmod 3$.
So CRT says there is a unique solution $pmod {28}$; $x equiv 17 pmod{24}$.
$x = A pmod {n_1}$ $(A = 1; n_1 = 8)$
$x = B pmod {n_2}$ $(B = 2; n_2 = 3)$
$m_1n_1 + m_2n_2 = 1$ (in this case $8m_1 + 3m_2 = 1$ so $m_1 =2; B=-5$ or $A=-1; B=3$ or .....)
Then $x = Am_2n_2 + Bn_1n_1pmod {n_1n_2}$.
$x = 1*(-5)*3 + 2*2*8= -15+32 = 17$.
There's utterly no point in reducing to $x equiv 5 pmod 4$ and $x equiv 5pmod 3$ as that will just get you back to $xequiv 2,5,8,11 pmod {12}$ and $x equiv 1,5 pmod 8$ which is worse than what you started with.
answered Jan 16 at 16:26
fleabloodfleablood
71.2k22686
$endgroup$
add a comment |
$begingroup$
No point in figuring it out to any lesser power of $2$ than $2^3$.
Leave it at $xequiv 1 pmod 8$ but $x equiv 5 pmod {12}$ can be reduced to $xequiv 5 equiv 2 pmod 3$.
So CRT says there is a unique solution $pmod {28}$; $x equiv 17 pmod{24}$.
$x = A pmod {n_1}$ $(A = 1; n_1 = 8)$
$x = B pmod {n_2}$ $(B = 2; n_2 = 3)$
$m_1n_1 + m_2n_2 = 1$ (in this case $8m_1 + 3m_2 = 1$ so $m_1 =2; B=-5$ or $A=-1; B=3$ or .....)
Then $x = Am_2n_2 + Bn_1n_1pmod {n_1n_2}$.
$x = 1*(-5)*3 + 2*2*8= -15+32 = 17$.
There's utterly no point in reducing to $x equiv 5 pmod 4$ and $x equiv 5pmod 3$ as that will just get you back to $xequiv 2,5,8,11 pmod {12}$ and $x equiv 1,5 pmod 8$ which is worse than what you started with.
answered Jan 16 at 16:26
fleabloodfleablood
71.2k22686
$endgroup$
No point in figuring it out to any lesser power of $2$ than $2^3$.
Leave it at $xequiv 1 pmod 8$ but $x equiv 5 pmod {12}$ can be reduced to $xequiv 5 equiv 2 pmod 3$.
So CRT says there is a unique solution $pmod {28}$; $x equiv 17 pmod{24}$.
$x = A pmod {n_1}$ $(A = 1; n_1 = 8)$
$x = B pmod {n_2}$ $(B = 2; n_2 = 3)$
$m_1n_1 + m_2n_2 = 1$ (in this case $8m_1 + 3m_2 = 1$ so $m_1 =2; B=-5$ or $A=-1; B=3$ or .....)
Then $x = Am_2n_2 + Bn_1n_1pmod {n_1n_2}$.
$x = 1*(-5)*3 + 2*2*8= -15+32 = 17$.
There's utterly no point in reducing to $x equiv 5 pmod 4$ and $x equiv 5pmod 3$ as that will just get you back to $xequiv 2,5,8,11 pmod {12}$ and $x equiv 1,5 pmod 8$ which is worse than what you started with.
answered Jan 16 at 16:26
fleabloodfleablood
71.2k22686
edited Jan 16 at 16:45
answered Jan 16 at 16:26
fleabloodfleablood
71.2k22686
answered Jan 16 at 16:26
fleabloodfleablood
71.2k22686
answered Jan 16 at 16:26
fleabloodfleablood
71.2k22686
71.2k22686
add a comment |
add a comment |
$begingroup$
Alternatively:
$$begin{cases}xequiv 1pmod{8}\ xequiv 5pmod{12}end{cases} Rightarrow begin{cases} x=8n+1\x=12m+5end{cases} Rightarrow 8n+1=12m+5 Rightarrow \
2n-3m=1 Rightarrow begin{cases}n=2+3k\m=1+2kend{cases} Rightarrow begin{cases} x=8(2+3k)\ x=12(1+2k)+5end{cases} Rightarrow \
x=24k+17 Rightarrow xequiv 17pmod{24}.$$
answered Jan 16 at 18:16
farruhotafarruhota
20.4k2739
$endgroup$
add a comment |
$begingroup$
Alternatively:
$$begin{cases}xequiv 1pmod{8}\ xequiv 5pmod{12}end{cases} Rightarrow begin{cases} x=8n+1\x=12m+5end{cases} Rightarrow 8n+1=12m+5 Rightarrow \
2n-3m=1 Rightarrow begin{cases}n=2+3k\m=1+2kend{cases} Rightarrow begin{cases} x=8(2+3k)\ x=12(1+2k)+5end{cases} Rightarrow \
x=24k+17 Rightarrow xequiv 17pmod{24}.$$
answered Jan 16 at 18:16
farruhotafarruhota
20.4k2739
$endgroup$
add a comment |
$begingroup$
Alternatively:
$$begin{cases}xequiv 1pmod{8}\ xequiv 5pmod{12}end{cases} Rightarrow begin{cases} x=8n+1\x=12m+5end{cases} Rightarrow 8n+1=12m+5 Rightarrow \
2n-3m=1 Rightarrow begin{cases}n=2+3k\m=1+2kend{cases} Rightarrow begin{cases} x=8(2+3k)\ x=12(1+2k)+5end{cases} Rightarrow \
x=24k+17 Rightarrow xequiv 17pmod{24}.$$
answered Jan 16 at 18:16
farruhotafarruhota
20.4k2739
$endgroup$
Alternatively:
$$begin{cases}xequiv 1pmod{8}\ xequiv 5pmod{12}end{cases} Rightarrow begin{cases} x=8n+1\x=12m+5end{cases} Rightarrow 8n+1=12m+5 Rightarrow \
2n-3m=1 Rightarrow begin{cases}n=2+3k\m=1+2kend{cases} Rightarrow begin{cases} x=8(2+3k)\ x=12(1+2k)+5end{cases} Rightarrow \
x=24k+17 Rightarrow xequiv 17pmod{24}.$$
answered Jan 16 at 18:16
farruhotafarruhota
20.4k2739
answered Jan 16 at 18:16
farruhotafarruhota
20.4k2739
answered Jan 16 at 18:16
farruhotafarruhota
20.4k2739
answered Jan 16 at 18:16
farruhotafarruhota
20.4k2739
20.4k2739
add a comment |
add a comment |
$begingroup$
Here is a way:
$$begin{cases}
xequiv 1pmod 8\xequiv 5pmod{12}
end{cases}iff begin{cases}
x -1equiv 0pmod 8\x -1equiv 4pmod{12}end{cases}iff
begin{cases}
frac{x -1}4equiv 0pmod 2\frac{x -1}4equiv 1pmod{3}
end{cases}$$
Now set $y=frac{x-1}4$. As $3-2=1$, the solutions of the last system of congruences is
$$ yequiv 0cdot 3- 1cdot 2 =-2pmod{6},$$
so that, multiplying by $4$,
$$x-1equiv -8 iff xequiv -7iff xequiv 17pmod{24}$$
answered Jan 16 at 16:10
BernardBernard
121k740116
$endgroup$
$begingroup$
This transformation happens quite naturally if we use the mod Distributive Law - see my answer.
$endgroup$
– Bill Dubuque
Jan 16 at 23:17
add a comment |
$begingroup$
Here is a way:
$$begin{cases}
xequiv 1pmod 8\xequiv 5pmod{12}
end{cases}iff begin{cases}
x -1equiv 0pmod 8\x -1equiv 4pmod{12}end{cases}iff
begin{cases}
frac{x -1}4equiv 0pmod 2\frac{x -1}4equiv 1pmod{3}
end{cases}$$
Now set $y=frac{x-1}4$. As $3-2=1$, the solutions of the last system of congruences is
$$ yequiv 0cdot 3- 1cdot 2 =-2pmod{6},$$
so that, multiplying by $4$,
$$x-1equiv -8 iff xequiv -7iff xequiv 17pmod{24}$$
answered Jan 16 at 16:10
BernardBernard
121k740116
$endgroup$
$begingroup$
This transformation happens quite naturally if we use the mod Distributive Law - see my answer.
$endgroup$
– Bill Dubuque
Jan 16 at 23:17
add a comment |
$begingroup$
Here is a way:
$$begin{cases}
xequiv 1pmod 8\xequiv 5pmod{12}
end{cases}iff begin{cases}
x -1equiv 0pmod 8\x -1equiv 4pmod{12}end{cases}iff
begin{cases}
frac{x -1}4equiv 0pmod 2\frac{x -1}4equiv 1pmod{3}
end{cases}$$
Now set $y=frac{x-1}4$. As $3-2=1$, the solutions of the last system of congruences is
$$ yequiv 0cdot 3- 1cdot 2 =-2pmod{6},$$
so that, multiplying by $4$,
$$x-1equiv -8 iff xequiv -7iff xequiv 17pmod{24}$$
answered Jan 16 at 16:10
BernardBernard
121k740116
$endgroup$
Here is a way:
$$begin{cases}
xequiv 1pmod 8\xequiv 5pmod{12}
end{cases}iff begin{cases}
x -1equiv 0pmod 8\x -1equiv 4pmod{12}end{cases}iff
begin{cases}
frac{x -1}4equiv 0pmod 2\frac{x -1}4equiv 1pmod{3}
end{cases}$$
Now set $y=frac{x-1}4$. As $3-2=1$, the solutions of the last system of congruences is
$$ yequiv 0cdot 3- 1cdot 2 =-2pmod{6},$$
so that, multiplying by $4$,
$$x-1equiv -8 iff xequiv -7iff xequiv 17pmod{24}$$
answered Jan 16 at 16:10
BernardBernard
121k740116
edited Jan 16 at 23:35
answered Jan 16 at 16:10
BernardBernard
121k740116
answered Jan 16 at 16:10
BernardBernard
121k740116
answered Jan 16 at 16:10
BernardBernard
121k740116
121k740116
$begingroup$
This transformation happens quite naturally if we use the mod Distributive Law - see my answer.
$endgroup$
– Bill Dubuque
Jan 16 at 23:17
add a comment |
$begingroup$
This transformation happens quite naturally if we use the mod Distributive Law - see my answer.
$endgroup$
– Bill Dubuque
Jan 16 at 23:17
$begingroup$
This transformation happens quite naturally if we use the mod Distributive Law - see my answer.
$endgroup$
– Bill Dubuque
Jan 16 at 23:17
$begingroup$
This transformation happens quite naturally if we use the mod Distributive Law - see my answer.
$endgroup$
– Bill Dubuque
Jan 16 at 23:17
add a comment |
$begingroup$
The moduli gcd is $,d = (8,12) = 4,$ and $,4mid 5-1,$ so by CRT a solution uniquely exists mod ${rm lcm}(8,12) $ $ = 8(12)/4 = 24,,$ computable by $, abbmod ac = a(bbmod c) = $ $!bmod!$ Distributive Law.
$8mid x!-!1Rightarrow x!-!1bmod 24 = 8left[dfrac{color{#c00}x!-!1}8!bmod 3right] = 8left[dfrac{color{#c00}5!-!1}{2 }!bmod 3right]= 16, $ by $ begin{align}x&equiv 5 !!!pmod{!12}\ Rightarrow,color{#c00}x&equiv color{#c00}5!!!pmod{!3}end{align}$
Remark $ $ This works generally for $,xequiv apmod{!m}, xequiv bpmod{!n},$ when $,(m,n)=color{#0a0}{dmid b!-!a}$
$mmid x!-!a,Rightarrow,x!-!abmod mn/d = mleft[dfrac{x-a}mbmod n/dright] = mleft[dfrac{b-a}mbmod n/dright] $
Note $,dmid b!-!a,Rightarrow, dfrac{b-a}m = dfrac{color{#0a0}{(b-a)/d}}{m/d}$ and $,m/d,$ is invertible $!bmod n/d,$ by $,(m/d,n/d)= 1,,$ thus the fraction exists $bmod n/d$.
answered Jan 16 at 23:09
Bill DubuqueBill Dubuque
211k29193646
$endgroup$
add a comment |
$begingroup$
The moduli gcd is $,d = (8,12) = 4,$ and $,4mid 5-1,$ so by CRT a solution uniquely exists mod ${rm lcm}(8,12) $ $ = 8(12)/4 = 24,,$ computable by $, abbmod ac = a(bbmod c) = $ $!bmod!$ Distributive Law.
$8mid x!-!1Rightarrow x!-!1bmod 24 = 8left[dfrac{color{#c00}x!-!1}8!bmod 3right] = 8left[dfrac{color{#c00}5!-!1}{2 }!bmod 3right]= 16, $ by $ begin{align}x&equiv 5 !!!pmod{!12}\ Rightarrow,color{#c00}x&equiv color{#c00}5!!!pmod{!3}end{align}$
Remark $ $ This works generally for $,xequiv apmod{!m}, xequiv bpmod{!n},$ when $,(m,n)=color{#0a0}{dmid b!-!a}$
$mmid x!-!a,Rightarrow,x!-!abmod mn/d = mleft[dfrac{x-a}mbmod n/dright] = mleft[dfrac{b-a}mbmod n/dright] $
Note $,dmid b!-!a,Rightarrow, dfrac{b-a}m = dfrac{color{#0a0}{(b-a)/d}}{m/d}$ and $,m/d,$ is invertible $!bmod n/d,$ by $,(m/d,n/d)= 1,,$ thus the fraction exists $bmod n/d$.
answered Jan 16 at 23:09
Bill DubuqueBill Dubuque
211k29193646
$endgroup$
add a comment |
$begingroup$
The moduli gcd is $,d = (8,12) = 4,$ and $,4mid 5-1,$ so by CRT a solution uniquely exists mod ${rm lcm}(8,12) $ $ = 8(12)/4 = 24,,$ computable by $, abbmod ac = a(bbmod c) = $ $!bmod!$ Distributive Law.
$8mid x!-!1Rightarrow x!-!1bmod 24 = 8left[dfrac{color{#c00}x!-!1}8!bmod 3right] = 8left[dfrac{color{#c00}5!-!1}{2 }!bmod 3right]= 16, $ by $ begin{align}x&equiv 5 !!!pmod{!12}\ Rightarrow,color{#c00}x&equiv color{#c00}5!!!pmod{!3}end{align}$
Remark $ $ This works generally for $,xequiv apmod{!m}, xequiv bpmod{!n},$ when $,(m,n)=color{#0a0}{dmid b!-!a}$
$mmid x!-!a,Rightarrow,x!-!abmod mn/d = mleft[dfrac{x-a}mbmod n/dright] = mleft[dfrac{b-a}mbmod n/dright] $
Note $,dmid b!-!a,Rightarrow, dfrac{b-a}m = dfrac{color{#0a0}{(b-a)/d}}{m/d}$ and $,m/d,$ is invertible $!bmod n/d,$ by $,(m/d,n/d)= 1,,$ thus the fraction exists $bmod n/d$.
answered Jan 16 at 23:09
Bill DubuqueBill Dubuque
211k29193646
$endgroup$
The moduli gcd is $,d = (8,12) = 4,$ and $,4mid 5-1,$ so by CRT a solution uniquely exists mod ${rm lcm}(8,12) $ $ = 8(12)/4 = 24,,$ computable by $, abbmod ac = a(bbmod c) = $ $!bmod!$ Distributive Law.
$8mid x!-!1Rightarrow x!-!1bmod 24 = 8left[dfrac{color{#c00}x!-!1}8!bmod 3right] = 8left[dfrac{color{#c00}5!-!1}{2 }!bmod 3right]= 16, $ by $ begin{align}x&equiv 5 !!!pmod{!12}\ Rightarrow,color{#c00}x&equiv color{#c00}5!!!pmod{!3}end{align}$
Remark $ $ This works generally for $,xequiv apmod{!m}, xequiv bpmod{!n},$ when $,(m,n)=color{#0a0}{dmid b!-!a}$
$mmid x!-!a,Rightarrow,x!-!abmod mn/d = mleft[dfrac{x-a}mbmod n/dright] = mleft[dfrac{b-a}mbmod n/dright] $
Note $,dmid b!-!a,Rightarrow, dfrac{b-a}m = dfrac{color{#0a0}{(b-a)/d}}{m/d}$ and $,m/d,$ is invertible $!bmod n/d,$ by $,(m/d,n/d)= 1,,$ thus the fraction exists $bmod n/d$.
answered Jan 16 at 23:09
Bill DubuqueBill Dubuque
211k29193646
edited Jan 16 at 23:36
answered Jan 16 at 23:09
Bill DubuqueBill Dubuque
211k29193646
answered Jan 16 at 23:09
Bill DubuqueBill Dubuque
211k29193646
answered Jan 16 at 23:09
Bill DubuqueBill Dubuque
211k29193646
211k29193646
add a comment |
add a comment |
$begingroup$
By CRT $,xequiv 5pmod{!12}!iff! xequiv 5pmod{!3},$ and $,color{#c00}{xequiv 5pmod{4}}$
But $,xequiv 1pmod{!8},Rightarrow,xequiv 1equiv 5pmod{!4},,$ hence $,color{#c00}{xequiv 5pmod{4}},$ is redundant, thus
$$begin{align} x&equiv 1!!pmod{8}\ x&equiv 5!!pmod{12}end{align}iff begin{array}{} xequiv 1 pmod{8}\ xequiv 5 pmod{3}end{array}qquad$$
so we have reduced it to a an equivalent system where the moduli are coprime. See my other answer for a convenient operational CRT method to solve (both!) of those congruence systems.
answered Jan 16 at 23:54
Bill DubuqueBill Dubuque
211k29193646
$endgroup$
add a comment |
$begingroup$
By CRT $,xequiv 5pmod{!12}!iff! xequiv 5pmod{!3},$ and $,color{#c00}{xequiv 5pmod{4}}$
But $,xequiv 1pmod{!8},Rightarrow,xequiv 1equiv 5pmod{!4},,$ hence $,color{#c00}{xequiv 5pmod{4}},$ is redundant, thus
$$begin{align} x&equiv 1!!pmod{8}\ x&equiv 5!!pmod{12}end{align}iff begin{array}{} xequiv 1 pmod{8}\ xequiv 5 pmod{3}end{array}qquad$$
so we have reduced it to a an equivalent system where the moduli are coprime. See my other answer for a convenient operational CRT method to solve (both!) of those congruence systems.
answered Jan 16 at 23:54
Bill DubuqueBill Dubuque
211k29193646
$endgroup$
add a comment |
$begingroup$
By CRT $,xequiv 5pmod{!12}!iff! xequiv 5pmod{!3},$ and $,color{#c00}{xequiv 5pmod{4}}$
But $,xequiv 1pmod{!8},Rightarrow,xequiv 1equiv 5pmod{!4},,$ hence $,color{#c00}{xequiv 5pmod{4}},$ is redundant, thus
$$begin{align} x&equiv 1!!pmod{8}\ x&equiv 5!!pmod{12}end{align}iff begin{array}{} xequiv 1 pmod{8}\ xequiv 5 pmod{3}end{array}qquad$$
so we have reduced it to a an equivalent system where the moduli are coprime. See my other answer for a convenient operational CRT method to solve (both!) of those congruence systems.
answered Jan 16 at 23:54
Bill DubuqueBill Dubuque
211k29193646
$endgroup$
By CRT $,xequiv 5pmod{!12}!iff! xequiv 5pmod{!3},$ and $,color{#c00}{xequiv 5pmod{4}}$
But $,xequiv 1pmod{!8},Rightarrow,xequiv 1equiv 5pmod{!4},,$ hence $,color{#c00}{xequiv 5pmod{4}},$ is redundant, thus
$$begin{align} x&equiv 1!!pmod{8}\ x&equiv 5!!pmod{12}end{align}iff begin{array}{} xequiv 1 pmod{8}\ xequiv 5 pmod{3}end{array}qquad$$
so we have reduced it to a an equivalent system where the moduli are coprime. See my other answer for a convenient operational CRT method to solve (both!) of those congruence systems.
answered Jan 16 at 23:54
Bill DubuqueBill Dubuque
211k29193646
answered Jan 16 at 23:54
Bill DubuqueBill Dubuque
211k29193646
answered Jan 16 at 23:54
Bill DubuqueBill Dubuque
211k29193646
answered Jan 16 at 23:54
Bill DubuqueBill Dubuque
211k29193646
211k29193646
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%2f3075823%2fhow-to-apply-crt-to-this-congruence-system%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$
Do you mean CRT (the Chinese Remainder Theorem)?
$endgroup$
– Théophile
Jan 16 at 14:50
$begingroup$
@Théophile Yes indeed, I edited the title of the question.
$endgroup$
– Igor
Jan 16 at 14:52
1
$begingroup$
$12 = nm, n=3,m=4,gcd(n,m)=1$ so $x equiv 5 bmod nm$ iff $x equiv 5 bmod n,x equiv 5 bmod m$. In the opposite direction when you have $x equiv a bmod n,x equiv b bmod m$ the goal is to find $c = un+vm$ such that it becomes $x equiv c bmod nm$
$endgroup$
– reuns
Jan 16 at 14:57
$begingroup$
Rewrite your system as $xequiv 1pmod 8$ and $xequiv 2pmod 3$.
$endgroup$
– lulu
Jan 16 at 15:11
$begingroup$
Um.... you haven't actually stated what the question is you are trying to answer? I assume it is what is the smallest such value of $x$ or what is $x pmod {24}$. But you haven't said it.
$endgroup$
– fleablood
Jan 16 at 16:24