How to solve $108 = m^37 pmod 143$

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP











up vote
-1
down vote

favorite
1












I've tried this in Wolfram Alpha and got the value for $m$ that I expected, however I would like to know how to solve it rather than just the answer.










share|cite|improve this question























  • Do you mean $37^m$? $2^37$ is already around $1 cdot 10^11$.
    – Toby Mak
    Sep 8 at 3:56











  • $gcd(108, 143) = 1.$ May use $m^10 equiv 1 pmod 11$ and $m^12 equiv 1 pmod 13$
    – Will Jagy
    Sep 8 at 3:57










  • @WillJagy Your expression is incorrect. (As a sanity check, plug in $m=1,$ which doesn't solve the original problem)
    – Jason Kim
    Sep 8 at 4:06










  • @JasonKim I just reported Fermat's Little Theorem. It can be used to reduce the exponent $37$ in the cases of interest
    – Will Jagy
    Sep 8 at 4:09










  • Huh... when I apply it, I get $m^7equiv9pmod11,mequiv4pmod13.$
    – Jason Kim
    Sep 8 at 4:17














up vote
-1
down vote

favorite
1












I've tried this in Wolfram Alpha and got the value for $m$ that I expected, however I would like to know how to solve it rather than just the answer.










share|cite|improve this question























  • Do you mean $37^m$? $2^37$ is already around $1 cdot 10^11$.
    – Toby Mak
    Sep 8 at 3:56











  • $gcd(108, 143) = 1.$ May use $m^10 equiv 1 pmod 11$ and $m^12 equiv 1 pmod 13$
    – Will Jagy
    Sep 8 at 3:57










  • @WillJagy Your expression is incorrect. (As a sanity check, plug in $m=1,$ which doesn't solve the original problem)
    – Jason Kim
    Sep 8 at 4:06










  • @JasonKim I just reported Fermat's Little Theorem. It can be used to reduce the exponent $37$ in the cases of interest
    – Will Jagy
    Sep 8 at 4:09










  • Huh... when I apply it, I get $m^7equiv9pmod11,mequiv4pmod13.$
    – Jason Kim
    Sep 8 at 4:17












up vote
-1
down vote

favorite
1









up vote
-1
down vote

favorite
1






1





I've tried this in Wolfram Alpha and got the value for $m$ that I expected, however I would like to know how to solve it rather than just the answer.










share|cite|improve this question















I've tried this in Wolfram Alpha and got the value for $m$ that I expected, however I would like to know how to solve it rather than just the answer.







modular-arithmetic






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Sep 8 at 15:19









GoodDeeds

10.2k21335




10.2k21335










asked Sep 8 at 3:42









Nick Ryan

11




11











  • Do you mean $37^m$? $2^37$ is already around $1 cdot 10^11$.
    – Toby Mak
    Sep 8 at 3:56











  • $gcd(108, 143) = 1.$ May use $m^10 equiv 1 pmod 11$ and $m^12 equiv 1 pmod 13$
    – Will Jagy
    Sep 8 at 3:57










  • @WillJagy Your expression is incorrect. (As a sanity check, plug in $m=1,$ which doesn't solve the original problem)
    – Jason Kim
    Sep 8 at 4:06










  • @JasonKim I just reported Fermat's Little Theorem. It can be used to reduce the exponent $37$ in the cases of interest
    – Will Jagy
    Sep 8 at 4:09










  • Huh... when I apply it, I get $m^7equiv9pmod11,mequiv4pmod13.$
    – Jason Kim
    Sep 8 at 4:17
















  • Do you mean $37^m$? $2^37$ is already around $1 cdot 10^11$.
    – Toby Mak
    Sep 8 at 3:56











  • $gcd(108, 143) = 1.$ May use $m^10 equiv 1 pmod 11$ and $m^12 equiv 1 pmod 13$
    – Will Jagy
    Sep 8 at 3:57










  • @WillJagy Your expression is incorrect. (As a sanity check, plug in $m=1,$ which doesn't solve the original problem)
    – Jason Kim
    Sep 8 at 4:06










  • @JasonKim I just reported Fermat's Little Theorem. It can be used to reduce the exponent $37$ in the cases of interest
    – Will Jagy
    Sep 8 at 4:09










  • Huh... when I apply it, I get $m^7equiv9pmod11,mequiv4pmod13.$
    – Jason Kim
    Sep 8 at 4:17















Do you mean $37^m$? $2^37$ is already around $1 cdot 10^11$.
– Toby Mak
Sep 8 at 3:56





Do you mean $37^m$? $2^37$ is already around $1 cdot 10^11$.
– Toby Mak
Sep 8 at 3:56













$gcd(108, 143) = 1.$ May use $m^10 equiv 1 pmod 11$ and $m^12 equiv 1 pmod 13$
– Will Jagy
Sep 8 at 3:57




$gcd(108, 143) = 1.$ May use $m^10 equiv 1 pmod 11$ and $m^12 equiv 1 pmod 13$
– Will Jagy
Sep 8 at 3:57












@WillJagy Your expression is incorrect. (As a sanity check, plug in $m=1,$ which doesn't solve the original problem)
– Jason Kim
Sep 8 at 4:06




@WillJagy Your expression is incorrect. (As a sanity check, plug in $m=1,$ which doesn't solve the original problem)
– Jason Kim
Sep 8 at 4:06












@JasonKim I just reported Fermat's Little Theorem. It can be used to reduce the exponent $37$ in the cases of interest
– Will Jagy
Sep 8 at 4:09




@JasonKim I just reported Fermat's Little Theorem. It can be used to reduce the exponent $37$ in the cases of interest
– Will Jagy
Sep 8 at 4:09












Huh... when I apply it, I get $m^7equiv9pmod11,mequiv4pmod13.$
– Jason Kim
Sep 8 at 4:17




Huh... when I apply it, I get $m^7equiv9pmod11,mequiv4pmod13.$
– Jason Kim
Sep 8 at 4:17










4 Answers
4






active

oldest

votes

















up vote
1
down vote













Note that $37$ is coprime to $phi(143)(=phi(11times13)=120$).
So in the multiplicative group of order 120, consisting integers coprime to $143, xmapsto x^37$ is an automorphism of groups (suffices to know it is a bijection).



Its inverse is the map $xmapsto x^a$ with $a$ being the inverse of 37 mod 120. (It happens that $a=13$ here.)



So, for $x$ coprime to 143, we can factorize the identity map ( Euler's theorem states $x^120$ is 1 mod 143) $xmapsto x ^1 = (x^13)^37pmod 143$



Applying for your case $x=108$, we get $m=108^13pmod143= 69pmod143$.






share|cite|improve this answer





























    up vote
    0
    down vote













    We work in the ring $R=Bbb Z/143$.
    Its units form a group $R^times$ with $phi(143)=143cdotleft(1-frac 111right)left(1-frac 113right)=120$ elements. We want to solve in this group
    $$
    108=m^37 .
    $$
    We start from this, take the $13$.th power and get
    $$
    m=m^481=(m^37)^13=108^13=69
    $$
    in $R$. (We had to get the inverse of $37$ modulo $120$, it is $13$.)
    One checks that this is a solution, to have the converse too.




    sage search for the solution:



    sage: R = Zmod(143)
    sage: for m in R:
    ....: if m^37 == R(108):
    ....: print m
    ....:
    69
    sage: R(108)^13
    69





    share|cite|improve this answer



























      up vote
      0
      down vote













      By Euler's theorem, $x^varphi (143)cong1pmod143$, if $x$ and $143$ are coprime.



      $varphi (143)=varphi (13)cdot varphi (11)=(13-1)(11-1)=(12)(10)=120$.



      Next, $(13)(37)-4(120)=1$. That is, $(13)(37)cong1pmod120$. (This can be done with the Euclidean algorithm, since $37$ and $120$ are coprime.)



      Now $(x^37)^13=x^481=(x^120)^4cdot xcong xpmod143implies 108^13cong xpmod143implies x=69$. (For the last step I used Wolfram alpha.)






      share|cite|improve this answer



























        up vote
        0
        down vote













        As $lambda(143)=60,$ let us find integer $a,b$ such that $$37a+60b=1$$



        Like my answer here in Solving a Linear Congruence, $$37cdot13-60cdot8=1$$



        $$m=m^37cdot13-60cdot8equiv(108)^13cdot1^-8pmod143$$



        $108equiv-2pmod11implies(108)^13equiv(-2)^13equiv(-2)^3equiv3 (1)$ using Fermat's Little Theorem



        Similarly, $(108)^13equiv4pmod13 (2)$



        Apply Chinese Remainder Theorem, on $(1),(2)$






        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',
          convertImagesToLinks: true,
          noModals: false,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: 10,
          bindNavPrevention: true,
          postfix: "",
          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%2f2909253%2fhow-to-solve-108-m37-pmod-143%23new-answer', 'question_page');

          );

          Post as a guest






























          4 Answers
          4






          active

          oldest

          votes








          4 Answers
          4






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes








          up vote
          1
          down vote













          Note that $37$ is coprime to $phi(143)(=phi(11times13)=120$).
          So in the multiplicative group of order 120, consisting integers coprime to $143, xmapsto x^37$ is an automorphism of groups (suffices to know it is a bijection).



          Its inverse is the map $xmapsto x^a$ with $a$ being the inverse of 37 mod 120. (It happens that $a=13$ here.)



          So, for $x$ coprime to 143, we can factorize the identity map ( Euler's theorem states $x^120$ is 1 mod 143) $xmapsto x ^1 = (x^13)^37pmod 143$



          Applying for your case $x=108$, we get $m=108^13pmod143= 69pmod143$.






          share|cite|improve this answer


























            up vote
            1
            down vote













            Note that $37$ is coprime to $phi(143)(=phi(11times13)=120$).
            So in the multiplicative group of order 120, consisting integers coprime to $143, xmapsto x^37$ is an automorphism of groups (suffices to know it is a bijection).



            Its inverse is the map $xmapsto x^a$ with $a$ being the inverse of 37 mod 120. (It happens that $a=13$ here.)



            So, for $x$ coprime to 143, we can factorize the identity map ( Euler's theorem states $x^120$ is 1 mod 143) $xmapsto x ^1 = (x^13)^37pmod 143$



            Applying for your case $x=108$, we get $m=108^13pmod143= 69pmod143$.






            share|cite|improve this answer
























              up vote
              1
              down vote










              up vote
              1
              down vote









              Note that $37$ is coprime to $phi(143)(=phi(11times13)=120$).
              So in the multiplicative group of order 120, consisting integers coprime to $143, xmapsto x^37$ is an automorphism of groups (suffices to know it is a bijection).



              Its inverse is the map $xmapsto x^a$ with $a$ being the inverse of 37 mod 120. (It happens that $a=13$ here.)



              So, for $x$ coprime to 143, we can factorize the identity map ( Euler's theorem states $x^120$ is 1 mod 143) $xmapsto x ^1 = (x^13)^37pmod 143$



              Applying for your case $x=108$, we get $m=108^13pmod143= 69pmod143$.






              share|cite|improve this answer














              Note that $37$ is coprime to $phi(143)(=phi(11times13)=120$).
              So in the multiplicative group of order 120, consisting integers coprime to $143, xmapsto x^37$ is an automorphism of groups (suffices to know it is a bijection).



              Its inverse is the map $xmapsto x^a$ with $a$ being the inverse of 37 mod 120. (It happens that $a=13$ here.)



              So, for $x$ coprime to 143, we can factorize the identity map ( Euler's theorem states $x^120$ is 1 mod 143) $xmapsto x ^1 = (x^13)^37pmod 143$



              Applying for your case $x=108$, we get $m=108^13pmod143= 69pmod143$.







              share|cite|improve this answer














              share|cite|improve this answer



              share|cite|improve this answer








              edited Sep 8 at 4:12

























              answered Sep 8 at 4:07









              P Vanchinathan

              14.1k12036




              14.1k12036




















                  up vote
                  0
                  down vote













                  We work in the ring $R=Bbb Z/143$.
                  Its units form a group $R^times$ with $phi(143)=143cdotleft(1-frac 111right)left(1-frac 113right)=120$ elements. We want to solve in this group
                  $$
                  108=m^37 .
                  $$
                  We start from this, take the $13$.th power and get
                  $$
                  m=m^481=(m^37)^13=108^13=69
                  $$
                  in $R$. (We had to get the inverse of $37$ modulo $120$, it is $13$.)
                  One checks that this is a solution, to have the converse too.




                  sage search for the solution:



                  sage: R = Zmod(143)
                  sage: for m in R:
                  ....: if m^37 == R(108):
                  ....: print m
                  ....:
                  69
                  sage: R(108)^13
                  69





                  share|cite|improve this answer
























                    up vote
                    0
                    down vote













                    We work in the ring $R=Bbb Z/143$.
                    Its units form a group $R^times$ with $phi(143)=143cdotleft(1-frac 111right)left(1-frac 113right)=120$ elements. We want to solve in this group
                    $$
                    108=m^37 .
                    $$
                    We start from this, take the $13$.th power and get
                    $$
                    m=m^481=(m^37)^13=108^13=69
                    $$
                    in $R$. (We had to get the inverse of $37$ modulo $120$, it is $13$.)
                    One checks that this is a solution, to have the converse too.




                    sage search for the solution:



                    sage: R = Zmod(143)
                    sage: for m in R:
                    ....: if m^37 == R(108):
                    ....: print m
                    ....:
                    69
                    sage: R(108)^13
                    69





                    share|cite|improve this answer






















                      up vote
                      0
                      down vote










                      up vote
                      0
                      down vote









                      We work in the ring $R=Bbb Z/143$.
                      Its units form a group $R^times$ with $phi(143)=143cdotleft(1-frac 111right)left(1-frac 113right)=120$ elements. We want to solve in this group
                      $$
                      108=m^37 .
                      $$
                      We start from this, take the $13$.th power and get
                      $$
                      m=m^481=(m^37)^13=108^13=69
                      $$
                      in $R$. (We had to get the inverse of $37$ modulo $120$, it is $13$.)
                      One checks that this is a solution, to have the converse too.




                      sage search for the solution:



                      sage: R = Zmod(143)
                      sage: for m in R:
                      ....: if m^37 == R(108):
                      ....: print m
                      ....:
                      69
                      sage: R(108)^13
                      69





                      share|cite|improve this answer












                      We work in the ring $R=Bbb Z/143$.
                      Its units form a group $R^times$ with $phi(143)=143cdotleft(1-frac 111right)left(1-frac 113right)=120$ elements. We want to solve in this group
                      $$
                      108=m^37 .
                      $$
                      We start from this, take the $13$.th power and get
                      $$
                      m=m^481=(m^37)^13=108^13=69
                      $$
                      in $R$. (We had to get the inverse of $37$ modulo $120$, it is $13$.)
                      One checks that this is a solution, to have the converse too.




                      sage search for the solution:



                      sage: R = Zmod(143)
                      sage: for m in R:
                      ....: if m^37 == R(108):
                      ....: print m
                      ....:
                      69
                      sage: R(108)^13
                      69






                      share|cite|improve this answer












                      share|cite|improve this answer



                      share|cite|improve this answer










                      answered Sep 8 at 4:12









                      dan_fulea

                      5,0901312




                      5,0901312




















                          up vote
                          0
                          down vote













                          By Euler's theorem, $x^varphi (143)cong1pmod143$, if $x$ and $143$ are coprime.



                          $varphi (143)=varphi (13)cdot varphi (11)=(13-1)(11-1)=(12)(10)=120$.



                          Next, $(13)(37)-4(120)=1$. That is, $(13)(37)cong1pmod120$. (This can be done with the Euclidean algorithm, since $37$ and $120$ are coprime.)



                          Now $(x^37)^13=x^481=(x^120)^4cdot xcong xpmod143implies 108^13cong xpmod143implies x=69$. (For the last step I used Wolfram alpha.)






                          share|cite|improve this answer
























                            up vote
                            0
                            down vote













                            By Euler's theorem, $x^varphi (143)cong1pmod143$, if $x$ and $143$ are coprime.



                            $varphi (143)=varphi (13)cdot varphi (11)=(13-1)(11-1)=(12)(10)=120$.



                            Next, $(13)(37)-4(120)=1$. That is, $(13)(37)cong1pmod120$. (This can be done with the Euclidean algorithm, since $37$ and $120$ are coprime.)



                            Now $(x^37)^13=x^481=(x^120)^4cdot xcong xpmod143implies 108^13cong xpmod143implies x=69$. (For the last step I used Wolfram alpha.)






                            share|cite|improve this answer






















                              up vote
                              0
                              down vote










                              up vote
                              0
                              down vote









                              By Euler's theorem, $x^varphi (143)cong1pmod143$, if $x$ and $143$ are coprime.



                              $varphi (143)=varphi (13)cdot varphi (11)=(13-1)(11-1)=(12)(10)=120$.



                              Next, $(13)(37)-4(120)=1$. That is, $(13)(37)cong1pmod120$. (This can be done with the Euclidean algorithm, since $37$ and $120$ are coprime.)



                              Now $(x^37)^13=x^481=(x^120)^4cdot xcong xpmod143implies 108^13cong xpmod143implies x=69$. (For the last step I used Wolfram alpha.)






                              share|cite|improve this answer












                              By Euler's theorem, $x^varphi (143)cong1pmod143$, if $x$ and $143$ are coprime.



                              $varphi (143)=varphi (13)cdot varphi (11)=(13-1)(11-1)=(12)(10)=120$.



                              Next, $(13)(37)-4(120)=1$. That is, $(13)(37)cong1pmod120$. (This can be done with the Euclidean algorithm, since $37$ and $120$ are coprime.)



                              Now $(x^37)^13=x^481=(x^120)^4cdot xcong xpmod143implies 108^13cong xpmod143implies x=69$. (For the last step I used Wolfram alpha.)







                              share|cite|improve this answer












                              share|cite|improve this answer



                              share|cite|improve this answer










                              answered Sep 8 at 6:39









                              Chris Custer

                              6,6192622




                              6,6192622




















                                  up vote
                                  0
                                  down vote













                                  As $lambda(143)=60,$ let us find integer $a,b$ such that $$37a+60b=1$$



                                  Like my answer here in Solving a Linear Congruence, $$37cdot13-60cdot8=1$$



                                  $$m=m^37cdot13-60cdot8equiv(108)^13cdot1^-8pmod143$$



                                  $108equiv-2pmod11implies(108)^13equiv(-2)^13equiv(-2)^3equiv3 (1)$ using Fermat's Little Theorem



                                  Similarly, $(108)^13equiv4pmod13 (2)$



                                  Apply Chinese Remainder Theorem, on $(1),(2)$






                                  share|cite|improve this answer
























                                    up vote
                                    0
                                    down vote













                                    As $lambda(143)=60,$ let us find integer $a,b$ such that $$37a+60b=1$$



                                    Like my answer here in Solving a Linear Congruence, $$37cdot13-60cdot8=1$$



                                    $$m=m^37cdot13-60cdot8equiv(108)^13cdot1^-8pmod143$$



                                    $108equiv-2pmod11implies(108)^13equiv(-2)^13equiv(-2)^3equiv3 (1)$ using Fermat's Little Theorem



                                    Similarly, $(108)^13equiv4pmod13 (2)$



                                    Apply Chinese Remainder Theorem, on $(1),(2)$






                                    share|cite|improve this answer






















                                      up vote
                                      0
                                      down vote










                                      up vote
                                      0
                                      down vote









                                      As $lambda(143)=60,$ let us find integer $a,b$ such that $$37a+60b=1$$



                                      Like my answer here in Solving a Linear Congruence, $$37cdot13-60cdot8=1$$



                                      $$m=m^37cdot13-60cdot8equiv(108)^13cdot1^-8pmod143$$



                                      $108equiv-2pmod11implies(108)^13equiv(-2)^13equiv(-2)^3equiv3 (1)$ using Fermat's Little Theorem



                                      Similarly, $(108)^13equiv4pmod13 (2)$



                                      Apply Chinese Remainder Theorem, on $(1),(2)$






                                      share|cite|improve this answer












                                      As $lambda(143)=60,$ let us find integer $a,b$ such that $$37a+60b=1$$



                                      Like my answer here in Solving a Linear Congruence, $$37cdot13-60cdot8=1$$



                                      $$m=m^37cdot13-60cdot8equiv(108)^13cdot1^-8pmod143$$



                                      $108equiv-2pmod11implies(108)^13equiv(-2)^13equiv(-2)^3equiv3 (1)$ using Fermat's Little Theorem



                                      Similarly, $(108)^13equiv4pmod13 (2)$



                                      Apply Chinese Remainder Theorem, on $(1),(2)$







                                      share|cite|improve this answer












                                      share|cite|improve this answer



                                      share|cite|improve this answer










                                      answered Sep 8 at 10:57









                                      lab bhattacharjee

                                      216k14153266




                                      216k14153266



























                                           

                                          draft saved


                                          draft discarded















































                                           


                                          draft saved


                                          draft discarded














                                          StackExchange.ready(
                                          function ()
                                          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2909253%2fhow-to-solve-108-m37-pmod-143%23new-answer', 'question_page');

                                          );

                                          Post as a guest













































































                                          這個網誌中的熱門文章

                                          How to combine Bézier curves to a surface?

                                          Carbon dioxide

                                          Why am i infinitely getting the same tweet with the Twitter Search API?