Mixing
Find the smallest natural number using Chinese Remainder Theorem
$begingroup$
Question is find the smallest natural number x such that,
$xequiv 1 (mod 2)$
$xequiv 2 (mod 3)$
$xequiv 3 (mod 4)$
$xequiv 4 (mod 5)$
$xequiv 5 (mod 6)$
$xequiv 6 (mod 7)$
$xequiv 7 (mod 8)$
$xequiv 8 (mod 9)$
$xequiv 9 (mod 10)$
$xequiv 10 (mod 11)$
$xequiv 11 (mod 12)$
$xequiv 0 (mod 13)$
I have been trying to use chinese remainder theorem to solve it, before I began I employed ChineseRemainder function of Wolfram to make sure I wasnt wasting precious time which gave me the result 277199 which works. However when I use the proof of theorem, I cannot even get over the first step where I must find inverse modulo: $b_1 frac{6227020800}{2}equiv 1(mod2)$ which I presume is $0cdot frac{6227020800}{2} + 2cdot 1 equiv 1$ hence 0?
I am somewhat confused. Friend did it using another method, but I would like to learn how to use chinese remainder theorem.
$xequiv a_1 b_1 frac{M}{m_1} + ... + a_k b_k frac{M}{m_k}(mod M),$
elementary-number-theory chinese-remainder-theorem
asked Jan 26 at 18:33
C. EkinciC. Ekinci
957
$endgroup$
|
show 2 more comments
$begingroup$
Question is find the smallest natural number x such that,
$xequiv 1 (mod 2)$
$xequiv 2 (mod 3)$
$xequiv 3 (mod 4)$
$xequiv 4 (mod 5)$
$xequiv 5 (mod 6)$
$xequiv 6 (mod 7)$
$xequiv 7 (mod 8)$
$xequiv 8 (mod 9)$
$xequiv 9 (mod 10)$
$xequiv 10 (mod 11)$
$xequiv 11 (mod 12)$
$xequiv 0 (mod 13)$
I have been trying to use chinese remainder theorem to solve it, before I began I employed ChineseRemainder function of Wolfram to make sure I wasnt wasting precious time which gave me the result 277199 which works. However when I use the proof of theorem, I cannot even get over the first step where I must find inverse modulo: $b_1 frac{6227020800}{2}equiv 1(mod2)$ which I presume is $0cdot frac{6227020800}{2} + 2cdot 1 equiv 1$ hence 0?
I am somewhat confused. Friend did it using another method, but I would like to learn how to use chinese remainder theorem.
$xequiv a_1 b_1 frac{M}{m_1} + ... + a_k b_k frac{M}{m_k}(mod M),$
elementary-number-theory chinese-remainder-theorem
asked Jan 26 at 18:33
C. EkinciC. Ekinci
957
$endgroup$
1
$begingroup$
Hint: $ xequiv -1,$ mod $,2,3,ldots, 12 $ iff their lcm divides $,x+1 $
$endgroup$
– Bill Dubuque
Jan 26 at 18:38
$begingroup$
"However when I use the proof of theorem, I cannot even get over the first step where I must find inverse modulo: $frac M{m_1}=frac{6227020800}2$" Could you write out what proof and why exactly you are finding it? It's not clear what you are trying to do.
$endgroup$
– fleablood
Jan 26 at 18:38
$begingroup$
@fleablood mathworld.wolfram.com/ChineseRemainderTheorem.html
$endgroup$
– C. Ekinci
Jan 26 at 18:39
$begingroup$
I know what the CRT theorem is. I'm asking YOU to explain why you are doing that as the first step and why.
$endgroup$
– fleablood
Jan 26 at 18:40
$begingroup$
@fleablood So that I can find inverse modulo $b_i$ , in order to plug in to the equation...$xequiv a_1 b_1 frac{M}{m_1} + ... + a_k b_k frac{M}{m_k}(mod M),$
$endgroup$
– C. Ekinci
Jan 26 at 18:43
|
show 2 more comments
$begingroup$
Question is find the smallest natural number x such that,
$xequiv 1 (mod 2)$
$xequiv 2 (mod 3)$
$xequiv 3 (mod 4)$
$xequiv 4 (mod 5)$
$xequiv 5 (mod 6)$
$xequiv 6 (mod 7)$
$xequiv 7 (mod 8)$
$xequiv 8 (mod 9)$
$xequiv 9 (mod 10)$
$xequiv 10 (mod 11)$
$xequiv 11 (mod 12)$
$xequiv 0 (mod 13)$
I have been trying to use chinese remainder theorem to solve it, before I began I employed ChineseRemainder function of Wolfram to make sure I wasnt wasting precious time which gave me the result 277199 which works. However when I use the proof of theorem, I cannot even get over the first step where I must find inverse modulo: $b_1 frac{6227020800}{2}equiv 1(mod2)$ which I presume is $0cdot frac{6227020800}{2} + 2cdot 1 equiv 1$ hence 0?
I am somewhat confused. Friend did it using another method, but I would like to learn how to use chinese remainder theorem.
$xequiv a_1 b_1 frac{M}{m_1} + ... + a_k b_k frac{M}{m_k}(mod M),$
elementary-number-theory chinese-remainder-theorem
asked Jan 26 at 18:33
C. EkinciC. Ekinci
957
$endgroup$
Question is find the smallest natural number x such that,
$xequiv 1 (mod 2)$
$xequiv 2 (mod 3)$
$xequiv 3 (mod 4)$
$xequiv 4 (mod 5)$
$xequiv 5 (mod 6)$
$xequiv 6 (mod 7)$
$xequiv 7 (mod 8)$
$xequiv 8 (mod 9)$
$xequiv 9 (mod 10)$
$xequiv 10 (mod 11)$
$xequiv 11 (mod 12)$
$xequiv 0 (mod 13)$
I have been trying to use chinese remainder theorem to solve it, before I began I employed ChineseRemainder function of Wolfram to make sure I wasnt wasting precious time which gave me the result 277199 which works. However when I use the proof of theorem, I cannot even get over the first step where I must find inverse modulo: $b_1 frac{6227020800}{2}equiv 1(mod2)$ which I presume is $0cdot frac{6227020800}{2} + 2cdot 1 equiv 1$ hence 0?
I am somewhat confused. Friend did it using another method, but I would like to learn how to use chinese remainder theorem.
$xequiv a_1 b_1 frac{M}{m_1} + ... + a_k b_k frac{M}{m_k}(mod M),$
elementary-number-theory chinese-remainder-theorem
elementary-number-theory chinese-remainder-theorem
asked Jan 26 at 18:33
C. EkinciC. Ekinci
957
asked Jan 26 at 18:33
C. EkinciC. Ekinci
957
edited Jan 26 at 18:50
C. Ekinci
asked Jan 26 at 18:33
C. EkinciC. Ekinci
957
asked Jan 26 at 18:33
C. EkinciC. Ekinci
957
asked Jan 26 at 18:33
C. EkinciC. Ekinci
957
957
1
$begingroup$
Hint: $ xequiv -1,$ mod $,2,3,ldots, 12 $ iff their lcm divides $,x+1 $
$endgroup$
– Bill Dubuque
Jan 26 at 18:38
$begingroup$
"However when I use the proof of theorem, I cannot even get over the first step where I must find inverse modulo: $frac M{m_1}=frac{6227020800}2$" Could you write out what proof and why exactly you are finding it? It's not clear what you are trying to do.
$endgroup$
– fleablood
Jan 26 at 18:38
$begingroup$
@fleablood mathworld.wolfram.com/ChineseRemainderTheorem.html
$endgroup$
– C. Ekinci
Jan 26 at 18:39
$begingroup$
I know what the CRT theorem is. I'm asking YOU to explain why you are doing that as the first step and why.
$endgroup$
– fleablood
Jan 26 at 18:40
$begingroup$
@fleablood So that I can find inverse modulo $b_i$ , in order to plug in to the equation...$xequiv a_1 b_1 frac{M}{m_1} + ... + a_k b_k frac{M}{m_k}(mod M),$
$endgroup$
– C. Ekinci
Jan 26 at 18:43
|
show 2 more comments
1
$begingroup$
Hint: $ xequiv -1,$ mod $,2,3,ldots, 12 $ iff their lcm divides $,x+1 $
$endgroup$
– Bill Dubuque
Jan 26 at 18:38
$begingroup$
"However when I use the proof of theorem, I cannot even get over the first step where I must find inverse modulo: $frac M{m_1}=frac{6227020800}2$" Could you write out what proof and why exactly you are finding it? It's not clear what you are trying to do.
$endgroup$
– fleablood
Jan 26 at 18:38
$begingroup$
@fleablood mathworld.wolfram.com/ChineseRemainderTheorem.html
$endgroup$
– C. Ekinci
Jan 26 at 18:39
$begingroup$
I know what the CRT theorem is. I'm asking YOU to explain why you are doing that as the first step and why.
$endgroup$
– fleablood
Jan 26 at 18:40
$begingroup$
@fleablood So that I can find inverse modulo $b_i$ , in order to plug in to the equation...$xequiv a_1 b_1 frac{M}{m_1} + ... + a_k b_k frac{M}{m_k}(mod M),$
$endgroup$
– C. Ekinci
Jan 26 at 18:43
1
1
$begingroup$
Hint: $ xequiv -1,$ mod $,2,3,ldots, 12 $ iff their lcm divides $,x+1 $
$endgroup$
– Bill Dubuque
Jan 26 at 18:38
$begingroup$
Hint: $ xequiv -1,$ mod $,2,3,ldots, 12 $ iff their lcm divides $,x+1 $
$endgroup$
– Bill Dubuque
Jan 26 at 18:38
$begingroup$
"However when I use the proof of theorem, I cannot even get over the first step where I must find inverse modulo: $frac M{m_1}=frac{6227020800}2$" Could you write out what proof and why exactly you are finding it? It's not clear what you are trying to do.
$endgroup$
– fleablood
Jan 26 at 18:38
$begingroup$
"However when I use the proof of theorem, I cannot even get over the first step where I must find inverse modulo: $frac M{m_1}=frac{6227020800}2$" Could you write out what proof and why exactly you are finding it? It's not clear what you are trying to do.
$endgroup$
– fleablood
Jan 26 at 18:38
$begingroup$
@fleablood mathworld.wolfram.com/ChineseRemainderTheorem.html
$endgroup$
– C. Ekinci
Jan 26 at 18:39
$begingroup$
@fleablood mathworld.wolfram.com/ChineseRemainderTheorem.html
$endgroup$
– C. Ekinci
Jan 26 at 18:39
$begingroup$
I know what the CRT theorem is. I'm asking YOU to explain why you are doing that as the first step and why.
$endgroup$
– fleablood
Jan 26 at 18:40
$begingroup$
I know what the CRT theorem is. I'm asking YOU to explain why you are doing that as the first step and why.
$endgroup$
– fleablood
Jan 26 at 18:40
$begingroup$
@fleablood So that I can find inverse modulo $b_i$ , in order to plug in to the equation...$xequiv a_1 b_1 frac{M}{m_1} + ... + a_k b_k frac{M}{m_k}(mod M),$
$endgroup$
– C. Ekinci
Jan 26 at 18:43
$begingroup$
@fleablood So that I can find inverse modulo $b_i$ , in order to plug in to the equation...$xequiv a_1 b_1 frac{M}{m_1} + ... + a_k b_k frac{M}{m_k}(mod M),$
$endgroup$
– C. Ekinci
Jan 26 at 18:43
|
show 2 more comments
2 Answers
2
active
oldest
votes
$begingroup$
The Chinese remainder theorem is about relatively prime modulos. Having all the modulos from $2$ to $13$ is redundant.
$xequiv 1 mod 2; x equiv 3mod 4; xequiv 7mod 8$ are redundant and can be replaced with just $x equiv 7 pmod 8$.
Assuming the question is legitimate, we need not consider any $x equiv j pmod {2^km}$ and have to consider only $xequiv lpmod m$
i.e., this question can be reduced to.
$xequiv 7pmod 8$
$x equiv 8pmod 9$
$x equiv 4 pmod 5$
$x equiv 6pmod 7$
$x equiv 10 pmod {11}$
$x equiv 0 pmod {13}$.
All the rest are redundant, as the solution to the above is unique.
Note the solution to all but $x equiv 0 pmod {13}$ is $x equiv -1 pmod n$ for $n = 8,9,5,7,11$ so
$xequiv -1 pmod{8*9*5*7*11=27720}$ and $x equiv 0 pmod {13}$.
So you need to solve. $x = 27720k -1 = 13m$
$27720 equiv 4 pmod {13}$
So $x equiv 27720k - 1equiv 0 pmod {13}$
$equiv 4k -1 equiv 0 pmod {13}$
So $4k equiv 1 pmod {13}$ so we just have to find the inverse of $4 mod {13}$
And $4 times 10 = 40 equiv 1 pmod{13}$ and so $k = 10$
and $x equiv 277199 pmod {27720*13}$
edited Jan 27 at 3:39
J. W. Tanner
3,6551320
answered Jan 26 at 18:55
fleabloodfleablood
72.9k22789
$endgroup$
$begingroup$
God, I feel like an absolute moron... thanks.
$endgroup$
– C. Ekinci
Jan 26 at 18:58
add a comment |
$begingroup$
$2,3,ldots,12mid x+1iff 27720mid x+1$ since $27720$ is the lcm of the divisors.
So $, 13n = x = 27720,color{#c00} k - 1 $ so $bmod 13!:, color{#c00} kequiv dfrac{1}{27720}equivdfrac{ -12}4equiv -3equiv color{#c00}{10}$
hence $, x = 22720(color{#c00}{10}+13m)-1 = 277199 + 13cdot 27720,m$
answered Jan 26 at 19:00
Bill DubuqueBill Dubuque
212k29195654
$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%2f3088578%2ffind-the-smallest-natural-number-using-chinese-remainder-theorem%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The Chinese remainder theorem is about relatively prime modulos. Having all the modulos from $2$ to $13$ is redundant.
$xequiv 1 mod 2; x equiv 3mod 4; xequiv 7mod 8$ are redundant and can be replaced with just $x equiv 7 pmod 8$.
Assuming the question is legitimate, we need not consider any $x equiv j pmod {2^km}$ and have to consider only $xequiv lpmod m$
i.e., this question can be reduced to.
$xequiv 7pmod 8$
$x equiv 8pmod 9$
$x equiv 4 pmod 5$
$x equiv 6pmod 7$
$x equiv 10 pmod {11}$
$x equiv 0 pmod {13}$.
All the rest are redundant, as the solution to the above is unique.
Note the solution to all but $x equiv 0 pmod {13}$ is $x equiv -1 pmod n$ for $n = 8,9,5,7,11$ so
$xequiv -1 pmod{8*9*5*7*11=27720}$ and $x equiv 0 pmod {13}$.
So you need to solve. $x = 27720k -1 = 13m$
$27720 equiv 4 pmod {13}$
So $x equiv 27720k - 1equiv 0 pmod {13}$
$equiv 4k -1 equiv 0 pmod {13}$
So $4k equiv 1 pmod {13}$ so we just have to find the inverse of $4 mod {13}$
And $4 times 10 = 40 equiv 1 pmod{13}$ and so $k = 10$
and $x equiv 277199 pmod {27720*13}$
edited Jan 27 at 3:39
J. W. Tanner
3,6551320
answered Jan 26 at 18:55
fleabloodfleablood
72.9k22789
$endgroup$
$begingroup$
God, I feel like an absolute moron... thanks.
$endgroup$
– C. Ekinci
Jan 26 at 18:58
add a comment |
$begingroup$
The Chinese remainder theorem is about relatively prime modulos. Having all the modulos from $2$ to $13$ is redundant.
$xequiv 1 mod 2; x equiv 3mod 4; xequiv 7mod 8$ are redundant and can be replaced with just $x equiv 7 pmod 8$.
Assuming the question is legitimate, we need not consider any $x equiv j pmod {2^km}$ and have to consider only $xequiv lpmod m$
i.e., this question can be reduced to.
$xequiv 7pmod 8$
$x equiv 8pmod 9$
$x equiv 4 pmod 5$
$x equiv 6pmod 7$
$x equiv 10 pmod {11}$
$x equiv 0 pmod {13}$.
All the rest are redundant, as the solution to the above is unique.
Note the solution to all but $x equiv 0 pmod {13}$ is $x equiv -1 pmod n$ for $n = 8,9,5,7,11$ so
$xequiv -1 pmod{8*9*5*7*11=27720}$ and $x equiv 0 pmod {13}$.
So you need to solve. $x = 27720k -1 = 13m$
$27720 equiv 4 pmod {13}$
So $x equiv 27720k - 1equiv 0 pmod {13}$
$equiv 4k -1 equiv 0 pmod {13}$
So $4k equiv 1 pmod {13}$ so we just have to find the inverse of $4 mod {13}$
And $4 times 10 = 40 equiv 1 pmod{13}$ and so $k = 10$
and $x equiv 277199 pmod {27720*13}$
edited Jan 27 at 3:39
J. W. Tanner
3,6551320
answered Jan 26 at 18:55
fleabloodfleablood
72.9k22789
$endgroup$
$begingroup$
God, I feel like an absolute moron... thanks.
$endgroup$
– C. Ekinci
Jan 26 at 18:58
add a comment |
$begingroup$
The Chinese remainder theorem is about relatively prime modulos. Having all the modulos from $2$ to $13$ is redundant.
$xequiv 1 mod 2; x equiv 3mod 4; xequiv 7mod 8$ are redundant and can be replaced with just $x equiv 7 pmod 8$.
Assuming the question is legitimate, we need not consider any $x equiv j pmod {2^km}$ and have to consider only $xequiv lpmod m$
i.e., this question can be reduced to.
$xequiv 7pmod 8$
$x equiv 8pmod 9$
$x equiv 4 pmod 5$
$x equiv 6pmod 7$
$x equiv 10 pmod {11}$
$x equiv 0 pmod {13}$.
All the rest are redundant, as the solution to the above is unique.
Note the solution to all but $x equiv 0 pmod {13}$ is $x equiv -1 pmod n$ for $n = 8,9,5,7,11$ so
$xequiv -1 pmod{8*9*5*7*11=27720}$ and $x equiv 0 pmod {13}$.
So you need to solve. $x = 27720k -1 = 13m$
$27720 equiv 4 pmod {13}$
So $x equiv 27720k - 1equiv 0 pmod {13}$
$equiv 4k -1 equiv 0 pmod {13}$
So $4k equiv 1 pmod {13}$ so we just have to find the inverse of $4 mod {13}$
And $4 times 10 = 40 equiv 1 pmod{13}$ and so $k = 10$
and $x equiv 277199 pmod {27720*13}$
edited Jan 27 at 3:39
J. W. Tanner
3,6551320
answered Jan 26 at 18:55
fleabloodfleablood
72.9k22789
$endgroup$
The Chinese remainder theorem is about relatively prime modulos. Having all the modulos from $2$ to $13$ is redundant.
$xequiv 1 mod 2; x equiv 3mod 4; xequiv 7mod 8$ are redundant and can be replaced with just $x equiv 7 pmod 8$.
Assuming the question is legitimate, we need not consider any $x equiv j pmod {2^km}$ and have to consider only $xequiv lpmod m$
i.e., this question can be reduced to.
$xequiv 7pmod 8$
$x equiv 8pmod 9$
$x equiv 4 pmod 5$
$x equiv 6pmod 7$
$x equiv 10 pmod {11}$
$x equiv 0 pmod {13}$.
All the rest are redundant, as the solution to the above is unique.
Note the solution to all but $x equiv 0 pmod {13}$ is $x equiv -1 pmod n$ for $n = 8,9,5,7,11$ so
$xequiv -1 pmod{8*9*5*7*11=27720}$ and $x equiv 0 pmod {13}$.
So you need to solve. $x = 27720k -1 = 13m$
$27720 equiv 4 pmod {13}$
So $x equiv 27720k - 1equiv 0 pmod {13}$
$equiv 4k -1 equiv 0 pmod {13}$
So $4k equiv 1 pmod {13}$ so we just have to find the inverse of $4 mod {13}$
And $4 times 10 = 40 equiv 1 pmod{13}$ and so $k = 10$
and $x equiv 277199 pmod {27720*13}$
edited Jan 27 at 3:39
J. W. Tanner
3,6551320
answered Jan 26 at 18:55
fleabloodfleablood
72.9k22789
edited Jan 27 at 3:39
J. W. Tanner
3,6551320
edited Jan 27 at 3:39
J. W. Tanner
3,6551320
edited Jan 27 at 3:39
J. W. Tanner
3,6551320
3,6551320
answered Jan 26 at 18:55
fleabloodfleablood
72.9k22789
answered Jan 26 at 18:55
fleabloodfleablood
72.9k22789
answered Jan 26 at 18:55
fleabloodfleablood
72.9k22789
72.9k22789
$begingroup$
God, I feel like an absolute moron... thanks.
$endgroup$
– C. Ekinci
Jan 26 at 18:58
add a comment |
$begingroup$
God, I feel like an absolute moron... thanks.
$endgroup$
– C. Ekinci
Jan 26 at 18:58
$begingroup$
God, I feel like an absolute moron... thanks.
$endgroup$
– C. Ekinci
Jan 26 at 18:58
$begingroup$
God, I feel like an absolute moron... thanks.
$endgroup$
– C. Ekinci
Jan 26 at 18:58
add a comment |
$begingroup$
$2,3,ldots,12mid x+1iff 27720mid x+1$ since $27720$ is the lcm of the divisors.
So $, 13n = x = 27720,color{#c00} k - 1 $ so $bmod 13!:, color{#c00} kequiv dfrac{1}{27720}equivdfrac{ -12}4equiv -3equiv color{#c00}{10}$
hence $, x = 22720(color{#c00}{10}+13m)-1 = 277199 + 13cdot 27720,m$
answered Jan 26 at 19:00
Bill DubuqueBill Dubuque
212k29195654
$endgroup$
add a comment |
$begingroup$
$2,3,ldots,12mid x+1iff 27720mid x+1$ since $27720$ is the lcm of the divisors.
So $, 13n = x = 27720,color{#c00} k - 1 $ so $bmod 13!:, color{#c00} kequiv dfrac{1}{27720}equivdfrac{ -12}4equiv -3equiv color{#c00}{10}$
hence $, x = 22720(color{#c00}{10}+13m)-1 = 277199 + 13cdot 27720,m$
answered Jan 26 at 19:00
Bill DubuqueBill Dubuque
212k29195654
$endgroup$
add a comment |
$begingroup$
$2,3,ldots,12mid x+1iff 27720mid x+1$ since $27720$ is the lcm of the divisors.
So $, 13n = x = 27720,color{#c00} k - 1 $ so $bmod 13!:, color{#c00} kequiv dfrac{1}{27720}equivdfrac{ -12}4equiv -3equiv color{#c00}{10}$
hence $, x = 22720(color{#c00}{10}+13m)-1 = 277199 + 13cdot 27720,m$
answered Jan 26 at 19:00
Bill DubuqueBill Dubuque
212k29195654
$endgroup$
$2,3,ldots,12mid x+1iff 27720mid x+1$ since $27720$ is the lcm of the divisors.
So $, 13n = x = 27720,color{#c00} k - 1 $ so $bmod 13!:, color{#c00} kequiv dfrac{1}{27720}equivdfrac{ -12}4equiv -3equiv color{#c00}{10}$
hence $, x = 22720(color{#c00}{10}+13m)-1 = 277199 + 13cdot 27720,m$
answered Jan 26 at 19:00
Bill DubuqueBill Dubuque
212k29195654
answered Jan 26 at 19:00
Bill DubuqueBill Dubuque
212k29195654
answered Jan 26 at 19:00
Bill DubuqueBill Dubuque
212k29195654
answered Jan 26 at 19:00
Bill DubuqueBill Dubuque
212k29195654
212k29195654
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%2f3088578%2ffind-the-smallest-natural-number-using-chinese-remainder-theorem%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
1
$begingroup$
Hint: $ xequiv -1,$ mod $,2,3,ldots, 12 $ iff their lcm divides $,x+1 $
$endgroup$
– Bill Dubuque
Jan 26 at 18:38
$begingroup$
"However when I use the proof of theorem, I cannot even get over the first step where I must find inverse modulo: $frac M{m_1}=frac{6227020800}2$" Could you write out what proof and why exactly you are finding it? It's not clear what you are trying to do.
$endgroup$
– fleablood
Jan 26 at 18:38
$begingroup$
@fleablood mathworld.wolfram.com/ChineseRemainderTheorem.html
$endgroup$
– C. Ekinci
Jan 26 at 18:39
$begingroup$
I know what the CRT theorem is. I'm asking YOU to explain why you are doing that as the first step and why.
$endgroup$
– fleablood
Jan 26 at 18:40
$begingroup$
@fleablood So that I can find inverse modulo $b_i$ , in order to plug in to the equation...$xequiv a_1 b_1 frac{M}{m_1} + ... + a_k b_k frac{M}{m_k}(mod M),$
$endgroup$
– C. Ekinci
Jan 26 at 18:43