Solve the congruence system $ xequiv m_i-1 pmod{m_i},$ for $,i = 1,ldots, k$












1














Find natural number $x$ so that
$$xequiv 9pmod{10},quad xequiv8pmod9,quad ...,quad xequiv 1pmod2$$










share|cite|improve this question





























    1














    Find natural number $x$ so that
    $$xequiv 9pmod{10},quad xequiv8pmod9,quad ...,quad xequiv 1pmod2$$










    share|cite|improve this question



























      1












      1








      1







      Find natural number $x$ so that
      $$xequiv 9pmod{10},quad xequiv8pmod9,quad ...,quad xequiv 1pmod2$$










      share|cite|improve this question















      Find natural number $x$ so that
      $$xequiv 9pmod{10},quad xequiv8pmod9,quad ...,quad xequiv 1pmod2$$







      elementary-number-theory






      share|cite|improve this question















      share|cite|improve this question













      share|cite|improve this question




      share|cite|improve this question








      edited Sep 4 '17 at 21:18









      Bill Dubuque

      208k29190626




      208k29190626










      asked Mar 16 '14 at 20:37









      user119081

      373




      373






















          3 Answers
          3






          active

          oldest

          votes


















          1














          Hint: The unnatural number $-1$ works.






          share|cite|improve this answer





















          • I ask for natural number not integer
            – user119081
            Mar 16 '14 at 20:44










          • @user119081: Yes, you did. But André's hint is still a good one. How could you find a second integer solution from that one? Could you make the second solution natural?
            – Charles
            Mar 16 '14 at 20:45










          • Yes, I know. But from my solution $-1$, which is not a natural number, one can find a natural number solution, indeed all natural number solutions. I am leaving the discovery of that, at least for a while, to you.
            – André Nicolas
            Mar 16 '14 at 20:46












          • I believe this should be exist a natural solution by extended Euclidean algorithm
            – user119081
            Mar 16 '14 at 20:48






          • 1




            While waiting, perhaps you can think of this. What number(s) can you add to my solution to get a natural number solution?
            – André Nicolas
            Mar 16 '14 at 20:52



















          1














          Since $,m_i-1equiv color{#c00}{-1}pmod{!m_i},$ we can apply $ $ CCRT = $rmcolor{#c00}{constant}$ case optimization of CRT



          $$begin{align} xequiv color{#c00}{-1}!!pmod{!m_i}&iff xequiv -1!!pmod{{rm lcm}{m_i}}\[.4em]
          text{or, without using CRT:} {rm all} m_i mid x+1 &iff {rm lcm}{m_i}mid x+1
          end{align}qquadqquad$$
          The latter equivalence is by the Universal Property of LCM (= definition of LCM in general)






          share|cite|improve this answer























          • It suffices to find any common multiple $,m,$ of all the moduli $,m_i$ (e.g. their product) and let $,x = m+1,,$ since then $,x-1 = m,$ is divisible by all $,m_i,,$ so, by above, is a solution.
            – Bill Dubuque
            Mar 16 '14 at 21:11





















          0














          begin{align}
          x &equiv 9 pmod{10} \
          x &equiv 8 pmod 9 \
          x &equiv 7 pmod 8 \
          x &equiv 6 pmod 7 \
          x &equiv 5 pmod 6 \
          x &equiv 4 pmod 5 \
          x &equiv 3 pmod 4 \
          x &equiv 2 pmod 3 \
          x &equiv 1 pmod 2 \
          end{align}



          Is equivalent to



          begin{align}
          x &equiv -1 pmod{10} \
          x &equiv -1 pmod 9 \
          x &equiv -1 pmod 8 \
          x &equiv -1 pmod 7 \
          x &equiv -1 pmod 6 \
          x &equiv -1 pmod 5 \
          x &equiv -1 pmod 4 \
          x &equiv -1 pmod 3 \
          x &equiv -1 pmod 2 \
          end{align}



          which is equivalent to



          $$x equiv -1 mod{operatorname{lcm}{2,3,4,5,6,7,8,9,10}}$$



          $$x equiv -1 pmod{2520}$$



          $$x equiv 2519 pmod{2520}$$






          share|cite|improve this answer























            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
            });


            }
            });














            draft saved

            draft discarded


















            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f714678%2fsolve-the-congruence-system-x-equiv-m-i-1-pmodm-i-for-i-1-ldots%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









            1














            Hint: The unnatural number $-1$ works.






            share|cite|improve this answer





















            • I ask for natural number not integer
              – user119081
              Mar 16 '14 at 20:44










            • @user119081: Yes, you did. But André's hint is still a good one. How could you find a second integer solution from that one? Could you make the second solution natural?
              – Charles
              Mar 16 '14 at 20:45










            • Yes, I know. But from my solution $-1$, which is not a natural number, one can find a natural number solution, indeed all natural number solutions. I am leaving the discovery of that, at least for a while, to you.
              – André Nicolas
              Mar 16 '14 at 20:46












            • I believe this should be exist a natural solution by extended Euclidean algorithm
              – user119081
              Mar 16 '14 at 20:48






            • 1




              While waiting, perhaps you can think of this. What number(s) can you add to my solution to get a natural number solution?
              – André Nicolas
              Mar 16 '14 at 20:52
















            1














            Hint: The unnatural number $-1$ works.






            share|cite|improve this answer





















            • I ask for natural number not integer
              – user119081
              Mar 16 '14 at 20:44










            • @user119081: Yes, you did. But André's hint is still a good one. How could you find a second integer solution from that one? Could you make the second solution natural?
              – Charles
              Mar 16 '14 at 20:45










            • Yes, I know. But from my solution $-1$, which is not a natural number, one can find a natural number solution, indeed all natural number solutions. I am leaving the discovery of that, at least for a while, to you.
              – André Nicolas
              Mar 16 '14 at 20:46












            • I believe this should be exist a natural solution by extended Euclidean algorithm
              – user119081
              Mar 16 '14 at 20:48






            • 1




              While waiting, perhaps you can think of this. What number(s) can you add to my solution to get a natural number solution?
              – André Nicolas
              Mar 16 '14 at 20:52














            1












            1








            1






            Hint: The unnatural number $-1$ works.






            share|cite|improve this answer












            Hint: The unnatural number $-1$ works.







            share|cite|improve this answer












            share|cite|improve this answer



            share|cite|improve this answer










            answered Mar 16 '14 at 20:41









            André Nicolas

            451k36421805




            451k36421805












            • I ask for natural number not integer
              – user119081
              Mar 16 '14 at 20:44










            • @user119081: Yes, you did. But André's hint is still a good one. How could you find a second integer solution from that one? Could you make the second solution natural?
              – Charles
              Mar 16 '14 at 20:45










            • Yes, I know. But from my solution $-1$, which is not a natural number, one can find a natural number solution, indeed all natural number solutions. I am leaving the discovery of that, at least for a while, to you.
              – André Nicolas
              Mar 16 '14 at 20:46












            • I believe this should be exist a natural solution by extended Euclidean algorithm
              – user119081
              Mar 16 '14 at 20:48






            • 1




              While waiting, perhaps you can think of this. What number(s) can you add to my solution to get a natural number solution?
              – André Nicolas
              Mar 16 '14 at 20:52


















            • I ask for natural number not integer
              – user119081
              Mar 16 '14 at 20:44










            • @user119081: Yes, you did. But André's hint is still a good one. How could you find a second integer solution from that one? Could you make the second solution natural?
              – Charles
              Mar 16 '14 at 20:45










            • Yes, I know. But from my solution $-1$, which is not a natural number, one can find a natural number solution, indeed all natural number solutions. I am leaving the discovery of that, at least for a while, to you.
              – André Nicolas
              Mar 16 '14 at 20:46












            • I believe this should be exist a natural solution by extended Euclidean algorithm
              – user119081
              Mar 16 '14 at 20:48






            • 1




              While waiting, perhaps you can think of this. What number(s) can you add to my solution to get a natural number solution?
              – André Nicolas
              Mar 16 '14 at 20:52
















            I ask for natural number not integer
            – user119081
            Mar 16 '14 at 20:44




            I ask for natural number not integer
            – user119081
            Mar 16 '14 at 20:44












            @user119081: Yes, you did. But André's hint is still a good one. How could you find a second integer solution from that one? Could you make the second solution natural?
            – Charles
            Mar 16 '14 at 20:45




            @user119081: Yes, you did. But André's hint is still a good one. How could you find a second integer solution from that one? Could you make the second solution natural?
            – Charles
            Mar 16 '14 at 20:45












            Yes, I know. But from my solution $-1$, which is not a natural number, one can find a natural number solution, indeed all natural number solutions. I am leaving the discovery of that, at least for a while, to you.
            – André Nicolas
            Mar 16 '14 at 20:46






            Yes, I know. But from my solution $-1$, which is not a natural number, one can find a natural number solution, indeed all natural number solutions. I am leaving the discovery of that, at least for a while, to you.
            – André Nicolas
            Mar 16 '14 at 20:46














            I believe this should be exist a natural solution by extended Euclidean algorithm
            – user119081
            Mar 16 '14 at 20:48




            I believe this should be exist a natural solution by extended Euclidean algorithm
            – user119081
            Mar 16 '14 at 20:48




            1




            1




            While waiting, perhaps you can think of this. What number(s) can you add to my solution to get a natural number solution?
            – André Nicolas
            Mar 16 '14 at 20:52




            While waiting, perhaps you can think of this. What number(s) can you add to my solution to get a natural number solution?
            – André Nicolas
            Mar 16 '14 at 20:52











            1














            Since $,m_i-1equiv color{#c00}{-1}pmod{!m_i},$ we can apply $ $ CCRT = $rmcolor{#c00}{constant}$ case optimization of CRT



            $$begin{align} xequiv color{#c00}{-1}!!pmod{!m_i}&iff xequiv -1!!pmod{{rm lcm}{m_i}}\[.4em]
            text{or, without using CRT:} {rm all} m_i mid x+1 &iff {rm lcm}{m_i}mid x+1
            end{align}qquadqquad$$
            The latter equivalence is by the Universal Property of LCM (= definition of LCM in general)






            share|cite|improve this answer























            • It suffices to find any common multiple $,m,$ of all the moduli $,m_i$ (e.g. their product) and let $,x = m+1,,$ since then $,x-1 = m,$ is divisible by all $,m_i,,$ so, by above, is a solution.
              – Bill Dubuque
              Mar 16 '14 at 21:11


















            1














            Since $,m_i-1equiv color{#c00}{-1}pmod{!m_i},$ we can apply $ $ CCRT = $rmcolor{#c00}{constant}$ case optimization of CRT



            $$begin{align} xequiv color{#c00}{-1}!!pmod{!m_i}&iff xequiv -1!!pmod{{rm lcm}{m_i}}\[.4em]
            text{or, without using CRT:} {rm all} m_i mid x+1 &iff {rm lcm}{m_i}mid x+1
            end{align}qquadqquad$$
            The latter equivalence is by the Universal Property of LCM (= definition of LCM in general)






            share|cite|improve this answer























            • It suffices to find any common multiple $,m,$ of all the moduli $,m_i$ (e.g. their product) and let $,x = m+1,,$ since then $,x-1 = m,$ is divisible by all $,m_i,,$ so, by above, is a solution.
              – Bill Dubuque
              Mar 16 '14 at 21:11
















            1












            1








            1






            Since $,m_i-1equiv color{#c00}{-1}pmod{!m_i},$ we can apply $ $ CCRT = $rmcolor{#c00}{constant}$ case optimization of CRT



            $$begin{align} xequiv color{#c00}{-1}!!pmod{!m_i}&iff xequiv -1!!pmod{{rm lcm}{m_i}}\[.4em]
            text{or, without using CRT:} {rm all} m_i mid x+1 &iff {rm lcm}{m_i}mid x+1
            end{align}qquadqquad$$
            The latter equivalence is by the Universal Property of LCM (= definition of LCM in general)






            share|cite|improve this answer














            Since $,m_i-1equiv color{#c00}{-1}pmod{!m_i},$ we can apply $ $ CCRT = $rmcolor{#c00}{constant}$ case optimization of CRT



            $$begin{align} xequiv color{#c00}{-1}!!pmod{!m_i}&iff xequiv -1!!pmod{{rm lcm}{m_i}}\[.4em]
            text{or, without using CRT:} {rm all} m_i mid x+1 &iff {rm lcm}{m_i}mid x+1
            end{align}qquadqquad$$
            The latter equivalence is by the Universal Property of LCM (= definition of LCM in general)







            share|cite|improve this answer














            share|cite|improve this answer



            share|cite|improve this answer








            edited Sep 4 '17 at 21:20

























            answered Mar 16 '14 at 20:52









            Bill Dubuque

            208k29190626




            208k29190626












            • It suffices to find any common multiple $,m,$ of all the moduli $,m_i$ (e.g. their product) and let $,x = m+1,,$ since then $,x-1 = m,$ is divisible by all $,m_i,,$ so, by above, is a solution.
              – Bill Dubuque
              Mar 16 '14 at 21:11




















            • It suffices to find any common multiple $,m,$ of all the moduli $,m_i$ (e.g. their product) and let $,x = m+1,,$ since then $,x-1 = m,$ is divisible by all $,m_i,,$ so, by above, is a solution.
              – Bill Dubuque
              Mar 16 '14 at 21:11


















            It suffices to find any common multiple $,m,$ of all the moduli $,m_i$ (e.g. their product) and let $,x = m+1,,$ since then $,x-1 = m,$ is divisible by all $,m_i,,$ so, by above, is a solution.
            – Bill Dubuque
            Mar 16 '14 at 21:11






            It suffices to find any common multiple $,m,$ of all the moduli $,m_i$ (e.g. their product) and let $,x = m+1,,$ since then $,x-1 = m,$ is divisible by all $,m_i,,$ so, by above, is a solution.
            – Bill Dubuque
            Mar 16 '14 at 21:11













            0














            begin{align}
            x &equiv 9 pmod{10} \
            x &equiv 8 pmod 9 \
            x &equiv 7 pmod 8 \
            x &equiv 6 pmod 7 \
            x &equiv 5 pmod 6 \
            x &equiv 4 pmod 5 \
            x &equiv 3 pmod 4 \
            x &equiv 2 pmod 3 \
            x &equiv 1 pmod 2 \
            end{align}



            Is equivalent to



            begin{align}
            x &equiv -1 pmod{10} \
            x &equiv -1 pmod 9 \
            x &equiv -1 pmod 8 \
            x &equiv -1 pmod 7 \
            x &equiv -1 pmod 6 \
            x &equiv -1 pmod 5 \
            x &equiv -1 pmod 4 \
            x &equiv -1 pmod 3 \
            x &equiv -1 pmod 2 \
            end{align}



            which is equivalent to



            $$x equiv -1 mod{operatorname{lcm}{2,3,4,5,6,7,8,9,10}}$$



            $$x equiv -1 pmod{2520}$$



            $$x equiv 2519 pmod{2520}$$






            share|cite|improve this answer




























              0














              begin{align}
              x &equiv 9 pmod{10} \
              x &equiv 8 pmod 9 \
              x &equiv 7 pmod 8 \
              x &equiv 6 pmod 7 \
              x &equiv 5 pmod 6 \
              x &equiv 4 pmod 5 \
              x &equiv 3 pmod 4 \
              x &equiv 2 pmod 3 \
              x &equiv 1 pmod 2 \
              end{align}



              Is equivalent to



              begin{align}
              x &equiv -1 pmod{10} \
              x &equiv -1 pmod 9 \
              x &equiv -1 pmod 8 \
              x &equiv -1 pmod 7 \
              x &equiv -1 pmod 6 \
              x &equiv -1 pmod 5 \
              x &equiv -1 pmod 4 \
              x &equiv -1 pmod 3 \
              x &equiv -1 pmod 2 \
              end{align}



              which is equivalent to



              $$x equiv -1 mod{operatorname{lcm}{2,3,4,5,6,7,8,9,10}}$$



              $$x equiv -1 pmod{2520}$$



              $$x equiv 2519 pmod{2520}$$






              share|cite|improve this answer


























                0












                0








                0






                begin{align}
                x &equiv 9 pmod{10} \
                x &equiv 8 pmod 9 \
                x &equiv 7 pmod 8 \
                x &equiv 6 pmod 7 \
                x &equiv 5 pmod 6 \
                x &equiv 4 pmod 5 \
                x &equiv 3 pmod 4 \
                x &equiv 2 pmod 3 \
                x &equiv 1 pmod 2 \
                end{align}



                Is equivalent to



                begin{align}
                x &equiv -1 pmod{10} \
                x &equiv -1 pmod 9 \
                x &equiv -1 pmod 8 \
                x &equiv -1 pmod 7 \
                x &equiv -1 pmod 6 \
                x &equiv -1 pmod 5 \
                x &equiv -1 pmod 4 \
                x &equiv -1 pmod 3 \
                x &equiv -1 pmod 2 \
                end{align}



                which is equivalent to



                $$x equiv -1 mod{operatorname{lcm}{2,3,4,5,6,7,8,9,10}}$$



                $$x equiv -1 pmod{2520}$$



                $$x equiv 2519 pmod{2520}$$






                share|cite|improve this answer














                begin{align}
                x &equiv 9 pmod{10} \
                x &equiv 8 pmod 9 \
                x &equiv 7 pmod 8 \
                x &equiv 6 pmod 7 \
                x &equiv 5 pmod 6 \
                x &equiv 4 pmod 5 \
                x &equiv 3 pmod 4 \
                x &equiv 2 pmod 3 \
                x &equiv 1 pmod 2 \
                end{align}



                Is equivalent to



                begin{align}
                x &equiv -1 pmod{10} \
                x &equiv -1 pmod 9 \
                x &equiv -1 pmod 8 \
                x &equiv -1 pmod 7 \
                x &equiv -1 pmod 6 \
                x &equiv -1 pmod 5 \
                x &equiv -1 pmod 4 \
                x &equiv -1 pmod 3 \
                x &equiv -1 pmod 2 \
                end{align}



                which is equivalent to



                $$x equiv -1 mod{operatorname{lcm}{2,3,4,5,6,7,8,9,10}}$$



                $$x equiv -1 pmod{2520}$$



                $$x equiv 2519 pmod{2520}$$







                share|cite|improve this answer














                share|cite|improve this answer



                share|cite|improve this answer








                edited Feb 17 '17 at 7:58

























                answered Feb 16 '17 at 14:40









                steven gregory

                17.7k32257




                17.7k32257






























                    draft saved

                    draft discarded




















































                    Thanks for contributing an answer to Mathematics Stack Exchange!


                    • Please be sure to answer the question. Provide details and share your research!

                    But avoid



                    • Asking for help, clarification, or responding to other answers.

                    • Making statements based on opinion; back them up with references or personal experience.


                    Use MathJax to format equations. MathJax reference.


                    To learn more, see our tips on writing great answers.





                    Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


                    Please pay close attention to the following guidance:


                    • Please be sure to answer the question. Provide details and share your research!

                    But avoid



                    • Asking for help, clarification, or responding to other answers.

                    • Making statements based on opinion; back them up with references or personal experience.


                    To learn more, see our tips on writing great answers.




                    draft saved


                    draft discarded














                    StackExchange.ready(
                    function () {
                    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f714678%2fsolve-the-congruence-system-x-equiv-m-i-1-pmodm-i-for-i-1-ldots%23new-answer', 'question_page');
                    }
                    );

                    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







                    Popular posts from this blog

                    Plaza Victoria

                    Puebla de Zaragoza

                    Musa