multiply different residue classes












0












$begingroup$


I am trying to solve a problem.
Proof that $300^{3000} equiv 1 bmod 1001$
So after a bit of puzzeling I found that $1001 = 7*11*13$
and I have prooved that:




  • $300^{3000} equiv 1 ;(bmod 7;)$

  • $300^{3000} equiv 1 ;(bmod 11;)$

  • $300^{3000} equiv 1 ;(bmod 13;)$


Now I wish to conclude that therefore $300^{3000} equiv 1 bmod 1001$



But that hinges on the assumption that I can multiply residue classes somehow like:



$[1]_7 * [1]_{11} * [1]_{13} = [1]_{1001}$ or more general maybe:
$[a]_p * [b]_q * [c]_{13} = [abc]_{pqr}$



Now we have some things that may help such as the factors $p,r,r$ being (co)prime in this case... but exaclty based on what can we draw such a conclusion ?



I was thiking of that somehow we can use Bezout, which guarantees that if $gcd(p,q)=1 => (exists x,y in mathbb{Z});(px+qy=1)$



but after scribbling some papers full of almosts...I want to ask you guys for some direction. Thanks!






elementary-number-theory modular-arithmetic







share|cite|improve this question









$endgroup$








  • 3




    $begingroup$
    The chinese remainder theorem is the key for your problem.
    $endgroup$
    – Peter
    Jan 12 at 13:03
















0












$begingroup$


I am trying to solve a problem.
Proof that $300^{3000} equiv 1 bmod 1001$
So after a bit of puzzeling I found that $1001 = 7*11*13$
and I have prooved that:




  • $300^{3000} equiv 1 ;(bmod 7;)$

  • $300^{3000} equiv 1 ;(bmod 11;)$

  • $300^{3000} equiv 1 ;(bmod 13;)$


Now I wish to conclude that therefore $300^{3000} equiv 1 bmod 1001$



But that hinges on the assumption that I can multiply residue classes somehow like:



$[1]_7 * [1]_{11} * [1]_{13} = [1]_{1001}$ or more general maybe:
$[a]_p * [b]_q * [c]_{13} = [abc]_{pqr}$



Now we have some things that may help such as the factors $p,r,r$ being (co)prime in this case... but exaclty based on what can we draw such a conclusion ?



I was thiking of that somehow we can use Bezout, which guarantees that if $gcd(p,q)=1 => (exists x,y in mathbb{Z});(px+qy=1)$



but after scribbling some papers full of almosts...I want to ask you guys for some direction. Thanks!






elementary-number-theory modular-arithmetic







share|cite|improve this question









$endgroup$








  • 3




    $begingroup$
    The chinese remainder theorem is the key for your problem.
    $endgroup$
    – Peter
    Jan 12 at 13:03














0












0








0





$begingroup$


I am trying to solve a problem.
Proof that $300^{3000} equiv 1 bmod 1001$
So after a bit of puzzeling I found that $1001 = 7*11*13$
and I have prooved that:




  • $300^{3000} equiv 1 ;(bmod 7;)$

  • $300^{3000} equiv 1 ;(bmod 11;)$

  • $300^{3000} equiv 1 ;(bmod 13;)$


Now I wish to conclude that therefore $300^{3000} equiv 1 bmod 1001$



But that hinges on the assumption that I can multiply residue classes somehow like:



$[1]_7 * [1]_{11} * [1]_{13} = [1]_{1001}$ or more general maybe:
$[a]_p * [b]_q * [c]_{13} = [abc]_{pqr}$



Now we have some things that may help such as the factors $p,r,r$ being (co)prime in this case... but exaclty based on what can we draw such a conclusion ?



I was thiking of that somehow we can use Bezout, which guarantees that if $gcd(p,q)=1 => (exists x,y in mathbb{Z});(px+qy=1)$



but after scribbling some papers full of almosts...I want to ask you guys for some direction. Thanks!






elementary-number-theory modular-arithmetic







share|cite|improve this question









$endgroup$




I am trying to solve a problem.
Proof that $300^{3000} equiv 1 bmod 1001$
So after a bit of puzzeling I found that $1001 = 7*11*13$
and I have prooved that:




  • $300^{3000} equiv 1 ;(bmod 7;)$

  • $300^{3000} equiv 1 ;(bmod 11;)$

  • $300^{3000} equiv 1 ;(bmod 13;)$


Now I wish to conclude that therefore $300^{3000} equiv 1 bmod 1001$



But that hinges on the assumption that I can multiply residue classes somehow like:



$[1]_7 * [1]_{11} * [1]_{13} = [1]_{1001}$ or more general maybe:
$[a]_p * [b]_q * [c]_{13} = [abc]_{pqr}$



Now we have some things that may help such as the factors $p,r,r$ being (co)prime in this case... but exaclty based on what can we draw such a conclusion ?



I was thiking of that somehow we can use Bezout, which guarantees that if $gcd(p,q)=1 => (exists x,y in mathbb{Z});(px+qy=1)$



but after scribbling some papers full of almosts...I want to ask you guys for some direction. Thanks!






elementary-number-theory modular-arithmetic




elementary-number-theory modular-arithmetic






share|cite|improve this question













share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










asked Jan 12 at 12:56









ChaiChai

1276




1276








  • 3




    $begingroup$
    The chinese remainder theorem is the key for your problem.
    $endgroup$
    – Peter
    Jan 12 at 13:03














  • 3




    $begingroup$
    The chinese remainder theorem is the key for your problem.
    $endgroup$
    – Peter
    Jan 12 at 13:03








3




3




$begingroup$
The chinese remainder theorem is the key for your problem.
$endgroup$
– Peter
Jan 12 at 13:03




$begingroup$
The chinese remainder theorem is the key for your problem.
$endgroup$
– Peter
Jan 12 at 13:03










4 Answers
4






active

oldest

votes


















1












$begingroup$

You can't multiply the residue classes like that. If all three were congruent to $2$, the answer would be $2$, not $8$. As others have said, the Chinese Remainder Theorem is the thing. But you can proceed as follows. Let $x=300^{3000}$. Then $xequiv 1 pmod{7}$ tells us that $x=7r+1$ for some integer $r$. Put this in the second congruence to see that



$$x = 7r+1 equiv 1 pmod{11}.$$



Solve this for $r$ in the usual way to get $requiv 0 pmod{11}$, which is to say $r=11s$ for some integer $s.$ Then we have $x=7(11s)+1$. Plug this into the last congruence to get



$$x=77s+1 equiv 1pmod{13}.$$



Solve this in the usual way to get $sequiv 0 pmod{13}$, or $s=13t$ for some integer $t$. Now you have



$$x = 77(13t)+1 =1001t+1 equiv 1 pmod{1001}.$$






share|cite|improve this answer









$endgroup$













  • $begingroup$
    Thank you! ice and clean answer! Now that i see it, it seems so simple! :)
    $endgroup$
    – Chai
    Jan 12 at 14:30










  • $begingroup$
    @Chai This is - at the heart - a property of $,{rm lcm},$ - one that is so fundamental in number theory that one must know it well to be proficient. See my answer and the linked answers for more on that.
    $endgroup$
    – Bill Dubuque
    Jan 12 at 15:22





















0












$begingroup$

If you have a calculator, here's a long way to do it. $$300^{3000}equiv(-90)^{1500}equiv92^{750}equiv456^{375}equiv(456^2)^{187}cdot 456equiv((-272)^2)^{93}cdot(-272)cdot456equiv(-90)^{93}cdot92$$$$(-90)^{93}cdot92equiv(90^2)^{46}cdot90cdot92equiv92^{46}cdot272equiv(456^2)^{11}cdot456cdot272equiv -272^{12}cdot456equiv-90^6cdot456$$$$-90^6cdot456equiv-92^3cdot456equiv(-90)cdot456equiv1$$






share|cite|improve this answer









$endgroup$













  • $begingroup$
    heheh yes, the short way is to type it in a computer... but the idea is to proof it without the aid of such :)
    $endgroup$
    – Chai
    Jan 12 at 13:29










  • $begingroup$
    I meant for a standard calculator, you can easily evaluate the square of a number.
    $endgroup$
    – TheSimpliFire
    Jan 12 at 13:30










  • $begingroup$
    Note that there is the cycle $90,92,456,272$
    $endgroup$
    – TheSimpliFire
    Jan 12 at 13:31



















0












$begingroup$

Since $1$ is a solution to all three congruences, the Chinese remainder theorem tells us that it is the unique solution $pmod{1001}$.






share|cite|improve this answer











$endgroup$





















    0












    $begingroup$

    The inference follows immediately from the $rmcolor{#c00}{universal},$ property of $,{rm lcm}$ = least common multiple, viz.



    $ xequiv apmod{!k,m,n}!iff!$ $smash[t]{overbrace{k,m,nmid x!-!a!color{#c00}iff! ell := {rm lcm}(k,m,n)mid x!-!a}}$ $!iff! xequiv apmod{!ell}$



    So in the OP we have $ xequiv 1pmod{!7,11,13}iff xequiv 1pmod{7cdot 11cdot 13}$



    Remark $ $ Alternatively we can use CCRT = Constant-case of CRT (Chinese Remainder Theorem), which is equivalent to the above $,{rm lcm},$ property.






    share|cite|improve this answer











    $endgroup$













      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%2f3070872%2fmultiply-different-residue-classes%23new-answer', 'question_page');
      }
      );

      Post as a guest















      Required, but never shown

























      4 Answers
      4






      active

      oldest

      votes








      4 Answers
      4






      active

      oldest

      votes









      active

      oldest

      votes






      active

      oldest

      votes









      1












      $begingroup$

      You can't multiply the residue classes like that. If all three were congruent to $2$, the answer would be $2$, not $8$. As others have said, the Chinese Remainder Theorem is the thing. But you can proceed as follows. Let $x=300^{3000}$. Then $xequiv 1 pmod{7}$ tells us that $x=7r+1$ for some integer $r$. Put this in the second congruence to see that



      $$x = 7r+1 equiv 1 pmod{11}.$$



      Solve this for $r$ in the usual way to get $requiv 0 pmod{11}$, which is to say $r=11s$ for some integer $s.$ Then we have $x=7(11s)+1$. Plug this into the last congruence to get



      $$x=77s+1 equiv 1pmod{13}.$$



      Solve this in the usual way to get $sequiv 0 pmod{13}$, or $s=13t$ for some integer $t$. Now you have



      $$x = 77(13t)+1 =1001t+1 equiv 1 pmod{1001}.$$






      share|cite|improve this answer









      $endgroup$













      • $begingroup$
        Thank you! ice and clean answer! Now that i see it, it seems so simple! :)
        $endgroup$
        – Chai
        Jan 12 at 14:30










      • $begingroup$
        @Chai This is - at the heart - a property of $,{rm lcm},$ - one that is so fundamental in number theory that one must know it well to be proficient. See my answer and the linked answers for more on that.
        $endgroup$
        – Bill Dubuque
        Jan 12 at 15:22


















      1












      $begingroup$

      You can't multiply the residue classes like that. If all three were congruent to $2$, the answer would be $2$, not $8$. As others have said, the Chinese Remainder Theorem is the thing. But you can proceed as follows. Let $x=300^{3000}$. Then $xequiv 1 pmod{7}$ tells us that $x=7r+1$ for some integer $r$. Put this in the second congruence to see that



      $$x = 7r+1 equiv 1 pmod{11}.$$



      Solve this for $r$ in the usual way to get $requiv 0 pmod{11}$, which is to say $r=11s$ for some integer $s.$ Then we have $x=7(11s)+1$. Plug this into the last congruence to get



      $$x=77s+1 equiv 1pmod{13}.$$



      Solve this in the usual way to get $sequiv 0 pmod{13}$, or $s=13t$ for some integer $t$. Now you have



      $$x = 77(13t)+1 =1001t+1 equiv 1 pmod{1001}.$$






      share|cite|improve this answer









      $endgroup$













      • $begingroup$
        Thank you! ice and clean answer! Now that i see it, it seems so simple! :)
        $endgroup$
        – Chai
        Jan 12 at 14:30










      • $begingroup$
        @Chai This is - at the heart - a property of $,{rm lcm},$ - one that is so fundamental in number theory that one must know it well to be proficient. See my answer and the linked answers for more on that.
        $endgroup$
        – Bill Dubuque
        Jan 12 at 15:22
















      1












      1








      1





      $begingroup$

      You can't multiply the residue classes like that. If all three were congruent to $2$, the answer would be $2$, not $8$. As others have said, the Chinese Remainder Theorem is the thing. But you can proceed as follows. Let $x=300^{3000}$. Then $xequiv 1 pmod{7}$ tells us that $x=7r+1$ for some integer $r$. Put this in the second congruence to see that



      $$x = 7r+1 equiv 1 pmod{11}.$$



      Solve this for $r$ in the usual way to get $requiv 0 pmod{11}$, which is to say $r=11s$ for some integer $s.$ Then we have $x=7(11s)+1$. Plug this into the last congruence to get



      $$x=77s+1 equiv 1pmod{13}.$$



      Solve this in the usual way to get $sequiv 0 pmod{13}$, or $s=13t$ for some integer $t$. Now you have



      $$x = 77(13t)+1 =1001t+1 equiv 1 pmod{1001}.$$






      share|cite|improve this answer









      $endgroup$



      You can't multiply the residue classes like that. If all three were congruent to $2$, the answer would be $2$, not $8$. As others have said, the Chinese Remainder Theorem is the thing. But you can proceed as follows. Let $x=300^{3000}$. Then $xequiv 1 pmod{7}$ tells us that $x=7r+1$ for some integer $r$. Put this in the second congruence to see that



      $$x = 7r+1 equiv 1 pmod{11}.$$



      Solve this for $r$ in the usual way to get $requiv 0 pmod{11}$, which is to say $r=11s$ for some integer $s.$ Then we have $x=7(11s)+1$. Plug this into the last congruence to get



      $$x=77s+1 equiv 1pmod{13}.$$



      Solve this in the usual way to get $sequiv 0 pmod{13}$, or $s=13t$ for some integer $t$. Now you have



      $$x = 77(13t)+1 =1001t+1 equiv 1 pmod{1001}.$$







      share|cite|improve this answer












      share|cite|improve this answer



      share|cite|improve this answer










      answered Jan 12 at 14:12









      B. GoddardB. Goddard

      18.9k21440




      18.9k21440












      • $begingroup$
        Thank you! ice and clean answer! Now that i see it, it seems so simple! :)
        $endgroup$
        – Chai
        Jan 12 at 14:30










      • $begingroup$
        @Chai This is - at the heart - a property of $,{rm lcm},$ - one that is so fundamental in number theory that one must know it well to be proficient. See my answer and the linked answers for more on that.
        $endgroup$
        – Bill Dubuque
        Jan 12 at 15:22




















      • $begingroup$
        Thank you! ice and clean answer! Now that i see it, it seems so simple! :)
        $endgroup$
        – Chai
        Jan 12 at 14:30










      • $begingroup$
        @Chai This is - at the heart - a property of $,{rm lcm},$ - one that is so fundamental in number theory that one must know it well to be proficient. See my answer and the linked answers for more on that.
        $endgroup$
        – Bill Dubuque
        Jan 12 at 15:22


















      $begingroup$
      Thank you! ice and clean answer! Now that i see it, it seems so simple! :)
      $endgroup$
      – Chai
      Jan 12 at 14:30




      $begingroup$
      Thank you! ice and clean answer! Now that i see it, it seems so simple! :)
      $endgroup$
      – Chai
      Jan 12 at 14:30












      $begingroup$
      @Chai This is - at the heart - a property of $,{rm lcm},$ - one that is so fundamental in number theory that one must know it well to be proficient. See my answer and the linked answers for more on that.
      $endgroup$
      – Bill Dubuque
      Jan 12 at 15:22






      $begingroup$
      @Chai This is - at the heart - a property of $,{rm lcm},$ - one that is so fundamental in number theory that one must know it well to be proficient. See my answer and the linked answers for more on that.
      $endgroup$
      – Bill Dubuque
      Jan 12 at 15:22













      0












      $begingroup$

      If you have a calculator, here's a long way to do it. $$300^{3000}equiv(-90)^{1500}equiv92^{750}equiv456^{375}equiv(456^2)^{187}cdot 456equiv((-272)^2)^{93}cdot(-272)cdot456equiv(-90)^{93}cdot92$$$$(-90)^{93}cdot92equiv(90^2)^{46}cdot90cdot92equiv92^{46}cdot272equiv(456^2)^{11}cdot456cdot272equiv -272^{12}cdot456equiv-90^6cdot456$$$$-90^6cdot456equiv-92^3cdot456equiv(-90)cdot456equiv1$$






      share|cite|improve this answer









      $endgroup$













      • $begingroup$
        heheh yes, the short way is to type it in a computer... but the idea is to proof it without the aid of such :)
        $endgroup$
        – Chai
        Jan 12 at 13:29










      • $begingroup$
        I meant for a standard calculator, you can easily evaluate the square of a number.
        $endgroup$
        – TheSimpliFire
        Jan 12 at 13:30










      • $begingroup$
        Note that there is the cycle $90,92,456,272$
        $endgroup$
        – TheSimpliFire
        Jan 12 at 13:31
















      0












      $begingroup$

      If you have a calculator, here's a long way to do it. $$300^{3000}equiv(-90)^{1500}equiv92^{750}equiv456^{375}equiv(456^2)^{187}cdot 456equiv((-272)^2)^{93}cdot(-272)cdot456equiv(-90)^{93}cdot92$$$$(-90)^{93}cdot92equiv(90^2)^{46}cdot90cdot92equiv92^{46}cdot272equiv(456^2)^{11}cdot456cdot272equiv -272^{12}cdot456equiv-90^6cdot456$$$$-90^6cdot456equiv-92^3cdot456equiv(-90)cdot456equiv1$$






      share|cite|improve this answer









      $endgroup$













      • $begingroup$
        heheh yes, the short way is to type it in a computer... but the idea is to proof it without the aid of such :)
        $endgroup$
        – Chai
        Jan 12 at 13:29










      • $begingroup$
        I meant for a standard calculator, you can easily evaluate the square of a number.
        $endgroup$
        – TheSimpliFire
        Jan 12 at 13:30










      • $begingroup$
        Note that there is the cycle $90,92,456,272$
        $endgroup$
        – TheSimpliFire
        Jan 12 at 13:31














      0












      0








      0





      $begingroup$

      If you have a calculator, here's a long way to do it. $$300^{3000}equiv(-90)^{1500}equiv92^{750}equiv456^{375}equiv(456^2)^{187}cdot 456equiv((-272)^2)^{93}cdot(-272)cdot456equiv(-90)^{93}cdot92$$$$(-90)^{93}cdot92equiv(90^2)^{46}cdot90cdot92equiv92^{46}cdot272equiv(456^2)^{11}cdot456cdot272equiv -272^{12}cdot456equiv-90^6cdot456$$$$-90^6cdot456equiv-92^3cdot456equiv(-90)cdot456equiv1$$






      share|cite|improve this answer









      $endgroup$



      If you have a calculator, here's a long way to do it. $$300^{3000}equiv(-90)^{1500}equiv92^{750}equiv456^{375}equiv(456^2)^{187}cdot 456equiv((-272)^2)^{93}cdot(-272)cdot456equiv(-90)^{93}cdot92$$$$(-90)^{93}cdot92equiv(90^2)^{46}cdot90cdot92equiv92^{46}cdot272equiv(456^2)^{11}cdot456cdot272equiv -272^{12}cdot456equiv-90^6cdot456$$$$-90^6cdot456equiv-92^3cdot456equiv(-90)cdot456equiv1$$







      share|cite|improve this answer












      share|cite|improve this answer



      share|cite|improve this answer










      answered Jan 12 at 13:27









      TheSimpliFireTheSimpliFire

      12.4k62460




      12.4k62460












      • $begingroup$
        heheh yes, the short way is to type it in a computer... but the idea is to proof it without the aid of such :)
        $endgroup$
        – Chai
        Jan 12 at 13:29










      • $begingroup$
        I meant for a standard calculator, you can easily evaluate the square of a number.
        $endgroup$
        – TheSimpliFire
        Jan 12 at 13:30










      • $begingroup$
        Note that there is the cycle $90,92,456,272$
        $endgroup$
        – TheSimpliFire
        Jan 12 at 13:31


















      • $begingroup$
        heheh yes, the short way is to type it in a computer... but the idea is to proof it without the aid of such :)
        $endgroup$
        – Chai
        Jan 12 at 13:29










      • $begingroup$
        I meant for a standard calculator, you can easily evaluate the square of a number.
        $endgroup$
        – TheSimpliFire
        Jan 12 at 13:30










      • $begingroup$
        Note that there is the cycle $90,92,456,272$
        $endgroup$
        – TheSimpliFire
        Jan 12 at 13:31
















      $begingroup$
      heheh yes, the short way is to type it in a computer... but the idea is to proof it without the aid of such :)
      $endgroup$
      – Chai
      Jan 12 at 13:29




      $begingroup$
      heheh yes, the short way is to type it in a computer... but the idea is to proof it without the aid of such :)
      $endgroup$
      – Chai
      Jan 12 at 13:29












      $begingroup$
      I meant for a standard calculator, you can easily evaluate the square of a number.
      $endgroup$
      – TheSimpliFire
      Jan 12 at 13:30




      $begingroup$
      I meant for a standard calculator, you can easily evaluate the square of a number.
      $endgroup$
      – TheSimpliFire
      Jan 12 at 13:30












      $begingroup$
      Note that there is the cycle $90,92,456,272$
      $endgroup$
      – TheSimpliFire
      Jan 12 at 13:31




      $begingroup$
      Note that there is the cycle $90,92,456,272$
      $endgroup$
      – TheSimpliFire
      Jan 12 at 13:31











      0












      $begingroup$

      Since $1$ is a solution to all three congruences, the Chinese remainder theorem tells us that it is the unique solution $pmod{1001}$.






      share|cite|improve this answer











      $endgroup$


















        0












        $begingroup$

        Since $1$ is a solution to all three congruences, the Chinese remainder theorem tells us that it is the unique solution $pmod{1001}$.






        share|cite|improve this answer











        $endgroup$
















          0












          0








          0





          $begingroup$

          Since $1$ is a solution to all three congruences, the Chinese remainder theorem tells us that it is the unique solution $pmod{1001}$.






          share|cite|improve this answer











          $endgroup$



          Since $1$ is a solution to all three congruences, the Chinese remainder theorem tells us that it is the unique solution $pmod{1001}$.







          share|cite|improve this answer














          share|cite|improve this answer



          share|cite|improve this answer








          edited Jan 12 at 13:59

























          answered Jan 12 at 13:13









          Chris CusterChris Custer

          13.1k3827




          13.1k3827























              0












              $begingroup$

              The inference follows immediately from the $rmcolor{#c00}{universal},$ property of $,{rm lcm}$ = least common multiple, viz.



              $ xequiv apmod{!k,m,n}!iff!$ $smash[t]{overbrace{k,m,nmid x!-!a!color{#c00}iff! ell := {rm lcm}(k,m,n)mid x!-!a}}$ $!iff! xequiv apmod{!ell}$



              So in the OP we have $ xequiv 1pmod{!7,11,13}iff xequiv 1pmod{7cdot 11cdot 13}$



              Remark $ $ Alternatively we can use CCRT = Constant-case of CRT (Chinese Remainder Theorem), which is equivalent to the above $,{rm lcm},$ property.






              share|cite|improve this answer











              $endgroup$


















                0












                $begingroup$

                The inference follows immediately from the $rmcolor{#c00}{universal},$ property of $,{rm lcm}$ = least common multiple, viz.



                $ xequiv apmod{!k,m,n}!iff!$ $smash[t]{overbrace{k,m,nmid x!-!a!color{#c00}iff! ell := {rm lcm}(k,m,n)mid x!-!a}}$ $!iff! xequiv apmod{!ell}$



                So in the OP we have $ xequiv 1pmod{!7,11,13}iff xequiv 1pmod{7cdot 11cdot 13}$



                Remark $ $ Alternatively we can use CCRT = Constant-case of CRT (Chinese Remainder Theorem), which is equivalent to the above $,{rm lcm},$ property.






                share|cite|improve this answer











                $endgroup$
















                  0












                  0








                  0





                  $begingroup$

                  The inference follows immediately from the $rmcolor{#c00}{universal},$ property of $,{rm lcm}$ = least common multiple, viz.



                  $ xequiv apmod{!k,m,n}!iff!$ $smash[t]{overbrace{k,m,nmid x!-!a!color{#c00}iff! ell := {rm lcm}(k,m,n)mid x!-!a}}$ $!iff! xequiv apmod{!ell}$



                  So in the OP we have $ xequiv 1pmod{!7,11,13}iff xequiv 1pmod{7cdot 11cdot 13}$



                  Remark $ $ Alternatively we can use CCRT = Constant-case of CRT (Chinese Remainder Theorem), which is equivalent to the above $,{rm lcm},$ property.






                  share|cite|improve this answer











                  $endgroup$



                  The inference follows immediately from the $rmcolor{#c00}{universal},$ property of $,{rm lcm}$ = least common multiple, viz.



                  $ xequiv apmod{!k,m,n}!iff!$ $smash[t]{overbrace{k,m,nmid x!-!a!color{#c00}iff! ell := {rm lcm}(k,m,n)mid x!-!a}}$ $!iff! xequiv apmod{!ell}$



                  So in the OP we have $ xequiv 1pmod{!7,11,13}iff xequiv 1pmod{7cdot 11cdot 13}$



                  Remark $ $ Alternatively we can use CCRT = Constant-case of CRT (Chinese Remainder Theorem), which is equivalent to the above $,{rm lcm},$ property.







                  share|cite|improve this answer














                  share|cite|improve this answer



                  share|cite|improve this answer








                  edited Jan 12 at 15:35

























                  answered Jan 12 at 15:16









                  Bill DubuqueBill Dubuque

                  210k29192644




                  210k29192644






























                      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.




                      draft saved


                      draft discarded














                      StackExchange.ready(
                      function () {
                      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3070872%2fmultiply-different-residue-classes%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

                      MongoDB - Not Authorized To Execute Command

                      Image
                      .everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ height:90px;width:728px;box-sizing:border-box; } 0 I have successfully enabled authorization on MongoDB and I have created an account on the admin database and then I created an account for my database called test. The following connection string to connect to my test database works successfully: mongo --host 192.168.17.52 --port 27017 -u user1 -p password --authenticationDatabase test Only problem I have now is, I cannot execute commands such as: show dbs. I get the following error when I try to do so: "errmsg" : "not authorized on admin to execute command { listDatabases: 1.0, lsid: { id: UUID("a1d5bc0d-bc58-485e-b232-270758a89455") }, $db: "admin...
                      Read more

                      in spring boot 2.1 many test slices are not allowed anymore due to multiple @BootstrapWith

                      Image
                      1 I tried to upgrade a yummy sandwich made of two test slices (@JsonTest and @JdbcTest in my case, crunchy test code in between) adding spring boot 2.1 flavour to it. But it seems it was not much of a success. I cannot annotate my tests with many @...Test since they are now each bringing their own XxxTestContextBootstrapper. It used to work when they all used same SpringBootTestContextBootstrapper. @RunWith(SpringRunner.class) @JdbcTest @JsonTest public class Test { @Test public void test() { System.out.printn("Hello, World !"); } } The error I get from BootstrapUtils is illegalStateException : Configuration error: found multiple declarations of @BootstrapWith for test class I understand I might be doing something wrong here but is there an easy way I could load both Json and Jdbc contex...
                      Read more

                      How to fix TextFormField cause rebuild widget in Flutter

                      Image
                      .everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ height:90px;width:728px;box-sizing:border-box; } 0 I've got the same issue at #9280. I tried all solutions from that topic with/without GlobalKey for Scaffold and Form but the problem wasn't fixed. I tried to build a authentication form with login and signup. But the keyboard doesn't show when I tap the TextFormField at the first time. Then I try to input some letter from physical keyboard, the widget is rebuilt. Like this: login screen Nothing to be log when I run flutter run --verbose, so I logged manually. Every tapping on field, the widget called dispose -> init -> build. [√] Flutter (Channel beta, v1.0.0, on Microsoft Windows [Version 10.0.17763.195], ...
                      Read more