How to solve this modular congruence?
$begingroup$
I have a system of two modular congruences:
$x equiv k bmod{m}$
and
$x equiv 0 bmod{23}$
Where $k$ and $m$ are known quantities and I want to find $x$. I'm at a loss as to whether or not there's a closed form for this, and even if I find this value of $x$, how do I know what the next workable value of $x$ is? Would it be $x$, $x + 23m$, $x + 46m$, $x + 69m$, etc? Or is it multiples of $text{lcm}(23, m)$?
elementary-number-theory modular-arithmetic
asked Dec 10 '18 at 1:07
user624732user624732
32
$endgroup$
|
show 4 more comments
$begingroup$
I have a system of two modular congruences:
$x equiv k bmod{m}$
and
$x equiv 0 bmod{23}$
Where $k$ and $m$ are known quantities and I want to find $x$. I'm at a loss as to whether or not there's a closed form for this, and even if I find this value of $x$, how do I know what the next workable value of $x$ is? Would it be $x$, $x + 23m$, $x + 46m$, $x + 69m$, etc? Or is it multiples of $text{lcm}(23, m)$?
elementary-number-theory modular-arithmetic
asked Dec 10 '18 at 1:07
user624732user624732
32
$endgroup$
$begingroup$
I think you want the Chinese remainder theorem: en.wikipedia.org/wiki/Chinese_remainder_theorem
$endgroup$
– Ethan Bolker
Dec 10 '18 at 1:09
$begingroup$
@EthanBolker Problem is that requires coprime values, it's possible $k$ and $23$ are not coprime, $k$ can be any positive integer.
$endgroup$
– user624732
Dec 10 '18 at 1:09
$begingroup$
Chinese remainder theorem requires $gcd(m,23)$ divides $k$ in your system. There isn't a general restriction saying $k,m$ need to be coprime.
$endgroup$
– coffeemath
Dec 10 '18 at 1:22
$begingroup$
@coffeemath I think I meant $m$, $23$ is prime so $gcd(m, 23) = 1$ unless $m$ is a multiple of $23$. The Chinese Remainder Theorem for these two congruences involves the inverse of $23$ mod $m$ does it not?
$endgroup$
– user624732
Dec 10 '18 at 1:34
$begingroup$
If $m$ is a multiple of $23,$ then for a solution one requires $k$ also a multiple of $23.$ In that case the first congruence becomes stronger than (i.e. implies) the second. If gcd of $m,23$ is $1,$ it's the usual Chinese remainder theorem, solution unique mod $23m.$ Yes, I think one way to finish uses inverse of $23$ mod $m.$ But if $m$ isn't too large,, can get the solution directly using a program rather than finding that inverse.
$endgroup$
– coffeemath
Dec 10 '18 at 2:24
|
show 4 more comments
$begingroup$
I have a system of two modular congruences:
$x equiv k bmod{m}$
and
$x equiv 0 bmod{23}$
Where $k$ and $m$ are known quantities and I want to find $x$. I'm at a loss as to whether or not there's a closed form for this, and even if I find this value of $x$, how do I know what the next workable value of $x$ is? Would it be $x$, $x + 23m$, $x + 46m$, $x + 69m$, etc? Or is it multiples of $text{lcm}(23, m)$?
elementary-number-theory modular-arithmetic
asked Dec 10 '18 at 1:07
user624732user624732
32
$endgroup$
I have a system of two modular congruences:
$x equiv k bmod{m}$
and
$x equiv 0 bmod{23}$
Where $k$ and $m$ are known quantities and I want to find $x$. I'm at a loss as to whether or not there's a closed form for this, and even if I find this value of $x$, how do I know what the next workable value of $x$ is? Would it be $x$, $x + 23m$, $x + 46m$, $x + 69m$, etc? Or is it multiples of $text{lcm}(23, m)$?
elementary-number-theory modular-arithmetic
elementary-number-theory modular-arithmetic
asked Dec 10 '18 at 1:07
user624732user624732
32
asked Dec 10 '18 at 1:07
user624732user624732
32
edited Dec 10 '18 at 1:09
user624732
asked Dec 10 '18 at 1:07
user624732user624732
32
asked Dec 10 '18 at 1:07
user624732user624732
32
asked Dec 10 '18 at 1:07
user624732user624732
32
32
$begingroup$
I think you want the Chinese remainder theorem: en.wikipedia.org/wiki/Chinese_remainder_theorem
$endgroup$
– Ethan Bolker
Dec 10 '18 at 1:09
$begingroup$
@EthanBolker Problem is that requires coprime values, it's possible $k$ and $23$ are not coprime, $k$ can be any positive integer.
$endgroup$
– user624732
Dec 10 '18 at 1:09
$begingroup$
Chinese remainder theorem requires $gcd(m,23)$ divides $k$ in your system. There isn't a general restriction saying $k,m$ need to be coprime.
$endgroup$
– coffeemath
Dec 10 '18 at 1:22
$begingroup$
@coffeemath I think I meant $m$, $23$ is prime so $gcd(m, 23) = 1$ unless $m$ is a multiple of $23$. The Chinese Remainder Theorem for these two congruences involves the inverse of $23$ mod $m$ does it not?
$endgroup$
– user624732
Dec 10 '18 at 1:34
$begingroup$
If $m$ is a multiple of $23,$ then for a solution one requires $k$ also a multiple of $23.$ In that case the first congruence becomes stronger than (i.e. implies) the second. If gcd of $m,23$ is $1,$ it's the usual Chinese remainder theorem, solution unique mod $23m.$ Yes, I think one way to finish uses inverse of $23$ mod $m.$ But if $m$ isn't too large,, can get the solution directly using a program rather than finding that inverse.
$endgroup$
– coffeemath
Dec 10 '18 at 2:24
|
show 4 more comments
$begingroup$
I think you want the Chinese remainder theorem: en.wikipedia.org/wiki/Chinese_remainder_theorem
$endgroup$
– Ethan Bolker
Dec 10 '18 at 1:09
$begingroup$
@EthanBolker Problem is that requires coprime values, it's possible $k$ and $23$ are not coprime, $k$ can be any positive integer.
$endgroup$
– user624732
Dec 10 '18 at 1:09
$begingroup$
Chinese remainder theorem requires $gcd(m,23)$ divides $k$ in your system. There isn't a general restriction saying $k,m$ need to be coprime.
$endgroup$
– coffeemath
Dec 10 '18 at 1:22
$begingroup$
@coffeemath I think I meant $m$, $23$ is prime so $gcd(m, 23) = 1$ unless $m$ is a multiple of $23$. The Chinese Remainder Theorem for these two congruences involves the inverse of $23$ mod $m$ does it not?
$endgroup$
– user624732
Dec 10 '18 at 1:34
$begingroup$
If $m$ is a multiple of $23,$ then for a solution one requires $k$ also a multiple of $23.$ In that case the first congruence becomes stronger than (i.e. implies) the second. If gcd of $m,23$ is $1,$ it's the usual Chinese remainder theorem, solution unique mod $23m.$ Yes, I think one way to finish uses inverse of $23$ mod $m.$ But if $m$ isn't too large,, can get the solution directly using a program rather than finding that inverse.
$endgroup$
– coffeemath
Dec 10 '18 at 2:24
$begingroup$
I think you want the Chinese remainder theorem: en.wikipedia.org/wiki/Chinese_remainder_theorem
$endgroup$
– Ethan Bolker
Dec 10 '18 at 1:09
$begingroup$
I think you want the Chinese remainder theorem: en.wikipedia.org/wiki/Chinese_remainder_theorem
$endgroup$
– Ethan Bolker
Dec 10 '18 at 1:09
$begingroup$
@EthanBolker Problem is that requires coprime values, it's possible $k$ and $23$ are not coprime, $k$ can be any positive integer.
$endgroup$
– user624732
Dec 10 '18 at 1:09
$begingroup$
@EthanBolker Problem is that requires coprime values, it's possible $k$ and $23$ are not coprime, $k$ can be any positive integer.
$endgroup$
– user624732
Dec 10 '18 at 1:09
$begingroup$
Chinese remainder theorem requires $gcd(m,23)$ divides $k$ in your system. There isn't a general restriction saying $k,m$ need to be coprime.
$endgroup$
– coffeemath
Dec 10 '18 at 1:22
$begingroup$
Chinese remainder theorem requires $gcd(m,23)$ divides $k$ in your system. There isn't a general restriction saying $k,m$ need to be coprime.
$endgroup$
– coffeemath
Dec 10 '18 at 1:22
$begingroup$
@coffeemath I think I meant $m$, $23$ is prime so $gcd(m, 23) = 1$ unless $m$ is a multiple of $23$. The Chinese Remainder Theorem for these two congruences involves the inverse of $23$ mod $m$ does it not?
$endgroup$
– user624732
Dec 10 '18 at 1:34
$begingroup$
@coffeemath I think I meant $m$, $23$ is prime so $gcd(m, 23) = 1$ unless $m$ is a multiple of $23$. The Chinese Remainder Theorem for these two congruences involves the inverse of $23$ mod $m$ does it not?
$endgroup$
– user624732
Dec 10 '18 at 1:34
$begingroup$
If $m$ is a multiple of $23,$ then for a solution one requires $k$ also a multiple of $23.$ In that case the first congruence becomes stronger than (i.e. implies) the second. If gcd of $m,23$ is $1,$ it's the usual Chinese remainder theorem, solution unique mod $23m.$ Yes, I think one way to finish uses inverse of $23$ mod $m.$ But if $m$ isn't too large,, can get the solution directly using a program rather than finding that inverse.
$endgroup$
– coffeemath
Dec 10 '18 at 2:24
$begingroup$
If $m$ is a multiple of $23,$ then for a solution one requires $k$ also a multiple of $23.$ In that case the first congruence becomes stronger than (i.e. implies) the second. If gcd of $m,23$ is $1,$ it's the usual Chinese remainder theorem, solution unique mod $23m.$ Yes, I think one way to finish uses inverse of $23$ mod $m.$ But if $m$ isn't too large,, can get the solution directly using a program rather than finding that inverse.
$endgroup$
– coffeemath
Dec 10 '18 at 2:24
|
show 4 more comments
1 Answer
1
active
oldest
votes
$begingroup$
By the Chinese Remainder Theorem we can show that
$ x, equiv, 23(kcdot 23^{-1}bmod m), pmod{!23m} {rm if} 23nmid m$
$ x, equiv, 23(k/23bmod m/23) ,pmod{!m} {rm if} 23mid m,k$
$ x,$ fails to exist $ $ (i.e. no solution exists) $ {rm if} 23mid m, 23nmid k$
Remark $ $ We can unify all cases by using general modular fractions, yielding
$ x, equiv, 23left(dfrac{k}{23}bmod mright)$
answered Dec 10 '18 at 2:34
Bill DubuqueBill Dubuque
210k29192645
$endgroup$
$begingroup$
It was that middle case that was eluding me, I didn't realize I could divide everything by $23$ like that. Why does it work?
$endgroup$
– user624732
Dec 10 '18 at 2:44
$begingroup$
1st case = CRT; $ $ 2nd case: divide $, x = k + j,m $ by $23,Rightarrow,x/23 = k/23 + j,m/23$ $ $
$endgroup$
– Bill Dubuque
Dec 10 '18 at 2:45
$begingroup$
@user624732 I added a remark you may find helpful.
$endgroup$
– Bill Dubuque
Dec 10 '18 at 3:02
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%2f3033288%2fhow-to-solve-this-modular-congruence%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
By the Chinese Remainder Theorem we can show that
$ x, equiv, 23(kcdot 23^{-1}bmod m), pmod{!23m} {rm if} 23nmid m$
$ x, equiv, 23(k/23bmod m/23) ,pmod{!m} {rm if} 23mid m,k$
$ x,$ fails to exist $ $ (i.e. no solution exists) $ {rm if} 23mid m, 23nmid k$
Remark $ $ We can unify all cases by using general modular fractions, yielding
$ x, equiv, 23left(dfrac{k}{23}bmod mright)$
answered Dec 10 '18 at 2:34
Bill DubuqueBill Dubuque
210k29192645
$endgroup$
$begingroup$
It was that middle case that was eluding me, I didn't realize I could divide everything by $23$ like that. Why does it work?
$endgroup$
– user624732
Dec 10 '18 at 2:44
$begingroup$
1st case = CRT; $ $ 2nd case: divide $, x = k + j,m $ by $23,Rightarrow,x/23 = k/23 + j,m/23$ $ $
$endgroup$
– Bill Dubuque
Dec 10 '18 at 2:45
$begingroup$
@user624732 I added a remark you may find helpful.
$endgroup$
– Bill Dubuque
Dec 10 '18 at 3:02
add a comment |
$begingroup$
By the Chinese Remainder Theorem we can show that
$ x, equiv, 23(kcdot 23^{-1}bmod m), pmod{!23m} {rm if} 23nmid m$
$ x, equiv, 23(k/23bmod m/23) ,pmod{!m} {rm if} 23mid m,k$
$ x,$ fails to exist $ $ (i.e. no solution exists) $ {rm if} 23mid m, 23nmid k$
Remark $ $ We can unify all cases by using general modular fractions, yielding
$ x, equiv, 23left(dfrac{k}{23}bmod mright)$
answered Dec 10 '18 at 2:34
Bill DubuqueBill Dubuque
210k29192645
$endgroup$
$begingroup$
It was that middle case that was eluding me, I didn't realize I could divide everything by $23$ like that. Why does it work?
$endgroup$
– user624732
Dec 10 '18 at 2:44
$begingroup$
1st case = CRT; $ $ 2nd case: divide $, x = k + j,m $ by $23,Rightarrow,x/23 = k/23 + j,m/23$ $ $
$endgroup$
– Bill Dubuque
Dec 10 '18 at 2:45
$begingroup$
@user624732 I added a remark you may find helpful.
$endgroup$
– Bill Dubuque
Dec 10 '18 at 3:02
add a comment |
$begingroup$
By the Chinese Remainder Theorem we can show that
$ x, equiv, 23(kcdot 23^{-1}bmod m), pmod{!23m} {rm if} 23nmid m$
$ x, equiv, 23(k/23bmod m/23) ,pmod{!m} {rm if} 23mid m,k$
$ x,$ fails to exist $ $ (i.e. no solution exists) $ {rm if} 23mid m, 23nmid k$
Remark $ $ We can unify all cases by using general modular fractions, yielding
$ x, equiv, 23left(dfrac{k}{23}bmod mright)$
answered Dec 10 '18 at 2:34
Bill DubuqueBill Dubuque
210k29192645
$endgroup$
By the Chinese Remainder Theorem we can show that
$ x, equiv, 23(kcdot 23^{-1}bmod m), pmod{!23m} {rm if} 23nmid m$
$ x, equiv, 23(k/23bmod m/23) ,pmod{!m} {rm if} 23mid m,k$
$ x,$ fails to exist $ $ (i.e. no solution exists) $ {rm if} 23mid m, 23nmid k$
Remark $ $ We can unify all cases by using general modular fractions, yielding
$ x, equiv, 23left(dfrac{k}{23}bmod mright)$
answered Dec 10 '18 at 2:34
Bill DubuqueBill Dubuque
210k29192645
edited Dec 10 '18 at 3:02
answered Dec 10 '18 at 2:34
Bill DubuqueBill Dubuque
210k29192645
answered Dec 10 '18 at 2:34
Bill DubuqueBill Dubuque
210k29192645
answered Dec 10 '18 at 2:34
Bill DubuqueBill Dubuque
210k29192645
210k29192645
$begingroup$
It was that middle case that was eluding me, I didn't realize I could divide everything by $23$ like that. Why does it work?
$endgroup$
– user624732
Dec 10 '18 at 2:44
$begingroup$
1st case = CRT; $ $ 2nd case: divide $, x = k + j,m $ by $23,Rightarrow,x/23 = k/23 + j,m/23$ $ $
$endgroup$
– Bill Dubuque
Dec 10 '18 at 2:45
$begingroup$
@user624732 I added a remark you may find helpful.
$endgroup$
– Bill Dubuque
Dec 10 '18 at 3:02
add a comment |
$begingroup$
It was that middle case that was eluding me, I didn't realize I could divide everything by $23$ like that. Why does it work?
$endgroup$
– user624732
Dec 10 '18 at 2:44
$begingroup$
1st case = CRT; $ $ 2nd case: divide $, x = k + j,m $ by $23,Rightarrow,x/23 = k/23 + j,m/23$ $ $
$endgroup$
– Bill Dubuque
Dec 10 '18 at 2:45
$begingroup$
@user624732 I added a remark you may find helpful.
$endgroup$
– Bill Dubuque
Dec 10 '18 at 3:02
$begingroup$
It was that middle case that was eluding me, I didn't realize I could divide everything by $23$ like that. Why does it work?
$endgroup$
– user624732
Dec 10 '18 at 2:44
$begingroup$
It was that middle case that was eluding me, I didn't realize I could divide everything by $23$ like that. Why does it work?
$endgroup$
– user624732
Dec 10 '18 at 2:44
$begingroup$
1st case = CRT; $ $ 2nd case: divide $, x = k + j,m $ by $23,Rightarrow,x/23 = k/23 + j,m/23$ $ $
$endgroup$
– Bill Dubuque
Dec 10 '18 at 2:45
$begingroup$
1st case = CRT; $ $ 2nd case: divide $, x = k + j,m $ by $23,Rightarrow,x/23 = k/23 + j,m/23$ $ $
$endgroup$
– Bill Dubuque
Dec 10 '18 at 2:45
$begingroup$
@user624732 I added a remark you may find helpful.
$endgroup$
– Bill Dubuque
Dec 10 '18 at 3:02
$begingroup$
@user624732 I added a remark you may find helpful.
$endgroup$
– Bill Dubuque
Dec 10 '18 at 3:02
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%2f3033288%2fhow-to-solve-this-modular-congruence%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$
I think you want the Chinese remainder theorem: en.wikipedia.org/wiki/Chinese_remainder_theorem
$endgroup$
– Ethan Bolker
Dec 10 '18 at 1:09
$begingroup$
@EthanBolker Problem is that requires coprime values, it's possible $k$ and $23$ are not coprime, $k$ can be any positive integer.
$endgroup$
– user624732
Dec 10 '18 at 1:09
$begingroup$
Chinese remainder theorem requires $gcd(m,23)$ divides $k$ in your system. There isn't a general restriction saying $k,m$ need to be coprime.
$endgroup$
– coffeemath
Dec 10 '18 at 1:22
$begingroup$
@coffeemath I think I meant $m$, $23$ is prime so $gcd(m, 23) = 1$ unless $m$ is a multiple of $23$. The Chinese Remainder Theorem for these two congruences involves the inverse of $23$ mod $m$ does it not?
$endgroup$
– user624732
Dec 10 '18 at 1:34
$begingroup$
If $m$ is a multiple of $23,$ then for a solution one requires $k$ also a multiple of $23.$ In that case the first congruence becomes stronger than (i.e. implies) the second. If gcd of $m,23$ is $1,$ it's the usual Chinese remainder theorem, solution unique mod $23m.$ Yes, I think one way to finish uses inverse of $23$ mod $m.$ But if $m$ isn't too large,, can get the solution directly using a program rather than finding that inverse.
$endgroup$
– coffeemath
Dec 10 '18 at 2:24