Modular Arithmetic - pairs of additive inverse pairs and multiplicative inverse pairs












1














I am taking a Cryptography class and we are working on modular arithmetic. I am still unsure on how to find pairs of additive inverse pairs and multiplicative inverse pairs. I've seen some videos and attempted to read about doing so but I find myself confused on what exactly I'm looking for. I've learned about the GCD, euclidean algorithm, but i just can't seem to piece it all together. Any help would be much appreciated. Thanks!



Example:
13 mod 17



How I got this:
For the additive inverse, I take the number given (13) and then find the number that would add up to n (n=17), in this case it is 4.
For the multiplicative inverse, I take the number given (13) and then add n to it(n=17), and then I find a number that multiples with 13 to be congruent to 1.



I picture a clock with n numbers around it. Im worried when it comes to a much bigger number such as 321^-1 mod 56709.



additive inverse:(13,4)
multiplicative inverse: a x b = 1(mod 17)
13 x 4 = 1(mod 17)





I'm working on another example:



list all additive inverse pairs and multiplicative inverse pairs of the sets Z28 and Z28*.
So far i have this:



Integers in the set:



Z28 = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27}



Z28* = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27}



Additive Inverse Pairs:



Z28 = (0,0),(1,27),(2,26),(3,25),(4,24),(5,23),(6,22),(7,21),(8,20),(9,19),(10,18),(11,17),(12,16),(13,15),(14,14)



Z28* = (1,27),(2,26),(3,25),(4,24),(5,23),(6,22),(7,21),(8,20),(9,19),(10,18),(11,17),(12,16),(13,15),(14,14)



as for the multiplicative inverse pairs, its taking me a while to check each one. Another question is, is there a faster way to find all inverse pairs of a set?










share|cite|improve this question
























  • Show us how far you can get through an example... say, the additive and multiplicative inverses for 13 under mod 17.
    – Joffan
    Jan 29 '15 at 18:43










  • 13 mod 17 additive inverse:(13,4) multiplicative inverse: a x b = 1(mod 17) 13 x 4 = 1(mod 17)
    – user655321
    Jan 29 '15 at 18:57












  • If you include how you got the answer I think it would be really useful. Apologies for choosing an example with the same result on both :-)
    – Joffan
    Jan 29 '15 at 19:00


















1














I am taking a Cryptography class and we are working on modular arithmetic. I am still unsure on how to find pairs of additive inverse pairs and multiplicative inverse pairs. I've seen some videos and attempted to read about doing so but I find myself confused on what exactly I'm looking for. I've learned about the GCD, euclidean algorithm, but i just can't seem to piece it all together. Any help would be much appreciated. Thanks!



Example:
13 mod 17



How I got this:
For the additive inverse, I take the number given (13) and then find the number that would add up to n (n=17), in this case it is 4.
For the multiplicative inverse, I take the number given (13) and then add n to it(n=17), and then I find a number that multiples with 13 to be congruent to 1.



I picture a clock with n numbers around it. Im worried when it comes to a much bigger number such as 321^-1 mod 56709.



additive inverse:(13,4)
multiplicative inverse: a x b = 1(mod 17)
13 x 4 = 1(mod 17)





I'm working on another example:



list all additive inverse pairs and multiplicative inverse pairs of the sets Z28 and Z28*.
So far i have this:



Integers in the set:



Z28 = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27}



Z28* = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27}



Additive Inverse Pairs:



Z28 = (0,0),(1,27),(2,26),(3,25),(4,24),(5,23),(6,22),(7,21),(8,20),(9,19),(10,18),(11,17),(12,16),(13,15),(14,14)



Z28* = (1,27),(2,26),(3,25),(4,24),(5,23),(6,22),(7,21),(8,20),(9,19),(10,18),(11,17),(12,16),(13,15),(14,14)



as for the multiplicative inverse pairs, its taking me a while to check each one. Another question is, is there a faster way to find all inverse pairs of a set?










share|cite|improve this question
























  • Show us how far you can get through an example... say, the additive and multiplicative inverses for 13 under mod 17.
    – Joffan
    Jan 29 '15 at 18:43










  • 13 mod 17 additive inverse:(13,4) multiplicative inverse: a x b = 1(mod 17) 13 x 4 = 1(mod 17)
    – user655321
    Jan 29 '15 at 18:57












  • If you include how you got the answer I think it would be really useful. Apologies for choosing an example with the same result on both :-)
    – Joffan
    Jan 29 '15 at 19:00
















1












1








1


1





I am taking a Cryptography class and we are working on modular arithmetic. I am still unsure on how to find pairs of additive inverse pairs and multiplicative inverse pairs. I've seen some videos and attempted to read about doing so but I find myself confused on what exactly I'm looking for. I've learned about the GCD, euclidean algorithm, but i just can't seem to piece it all together. Any help would be much appreciated. Thanks!



Example:
13 mod 17



How I got this:
For the additive inverse, I take the number given (13) and then find the number that would add up to n (n=17), in this case it is 4.
For the multiplicative inverse, I take the number given (13) and then add n to it(n=17), and then I find a number that multiples with 13 to be congruent to 1.



I picture a clock with n numbers around it. Im worried when it comes to a much bigger number such as 321^-1 mod 56709.



additive inverse:(13,4)
multiplicative inverse: a x b = 1(mod 17)
13 x 4 = 1(mod 17)





I'm working on another example:



list all additive inverse pairs and multiplicative inverse pairs of the sets Z28 and Z28*.
So far i have this:



Integers in the set:



Z28 = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27}



Z28* = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27}



Additive Inverse Pairs:



Z28 = (0,0),(1,27),(2,26),(3,25),(4,24),(5,23),(6,22),(7,21),(8,20),(9,19),(10,18),(11,17),(12,16),(13,15),(14,14)



Z28* = (1,27),(2,26),(3,25),(4,24),(5,23),(6,22),(7,21),(8,20),(9,19),(10,18),(11,17),(12,16),(13,15),(14,14)



as for the multiplicative inverse pairs, its taking me a while to check each one. Another question is, is there a faster way to find all inverse pairs of a set?










share|cite|improve this question















I am taking a Cryptography class and we are working on modular arithmetic. I am still unsure on how to find pairs of additive inverse pairs and multiplicative inverse pairs. I've seen some videos and attempted to read about doing so but I find myself confused on what exactly I'm looking for. I've learned about the GCD, euclidean algorithm, but i just can't seem to piece it all together. Any help would be much appreciated. Thanks!



Example:
13 mod 17



How I got this:
For the additive inverse, I take the number given (13) and then find the number that would add up to n (n=17), in this case it is 4.
For the multiplicative inverse, I take the number given (13) and then add n to it(n=17), and then I find a number that multiples with 13 to be congruent to 1.



I picture a clock with n numbers around it. Im worried when it comes to a much bigger number such as 321^-1 mod 56709.



additive inverse:(13,4)
multiplicative inverse: a x b = 1(mod 17)
13 x 4 = 1(mod 17)





I'm working on another example:



list all additive inverse pairs and multiplicative inverse pairs of the sets Z28 and Z28*.
So far i have this:



Integers in the set:



Z28 = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27}



Z28* = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27}



Additive Inverse Pairs:



Z28 = (0,0),(1,27),(2,26),(3,25),(4,24),(5,23),(6,22),(7,21),(8,20),(9,19),(10,18),(11,17),(12,16),(13,15),(14,14)



Z28* = (1,27),(2,26),(3,25),(4,24),(5,23),(6,22),(7,21),(8,20),(9,19),(10,18),(11,17),(12,16),(13,15),(14,14)



as for the multiplicative inverse pairs, its taking me a while to check each one. Another question is, is there a faster way to find all inverse pairs of a set?







modular-arithmetic cryptography






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Jan 29 '15 at 19:26







user655321

















asked Jan 29 '15 at 18:37









user655321user655321

681211




681211












  • Show us how far you can get through an example... say, the additive and multiplicative inverses for 13 under mod 17.
    – Joffan
    Jan 29 '15 at 18:43










  • 13 mod 17 additive inverse:(13,4) multiplicative inverse: a x b = 1(mod 17) 13 x 4 = 1(mod 17)
    – user655321
    Jan 29 '15 at 18:57












  • If you include how you got the answer I think it would be really useful. Apologies for choosing an example with the same result on both :-)
    – Joffan
    Jan 29 '15 at 19:00




















  • Show us how far you can get through an example... say, the additive and multiplicative inverses for 13 under mod 17.
    – Joffan
    Jan 29 '15 at 18:43










  • 13 mod 17 additive inverse:(13,4) multiplicative inverse: a x b = 1(mod 17) 13 x 4 = 1(mod 17)
    – user655321
    Jan 29 '15 at 18:57












  • If you include how you got the answer I think it would be really useful. Apologies for choosing an example with the same result on both :-)
    – Joffan
    Jan 29 '15 at 19:00


















Show us how far you can get through an example... say, the additive and multiplicative inverses for 13 under mod 17.
– Joffan
Jan 29 '15 at 18:43




Show us how far you can get through an example... say, the additive and multiplicative inverses for 13 under mod 17.
– Joffan
Jan 29 '15 at 18:43












13 mod 17 additive inverse:(13,4) multiplicative inverse: a x b = 1(mod 17) 13 x 4 = 1(mod 17)
– user655321
Jan 29 '15 at 18:57






13 mod 17 additive inverse:(13,4) multiplicative inverse: a x b = 1(mod 17) 13 x 4 = 1(mod 17)
– user655321
Jan 29 '15 at 18:57














If you include how you got the answer I think it would be really useful. Apologies for choosing an example with the same result on both :-)
– Joffan
Jan 29 '15 at 19:00






If you include how you got the answer I think it would be really useful. Apologies for choosing an example with the same result on both :-)
– Joffan
Jan 29 '15 at 19:00












2 Answers
2






active

oldest

votes


















0














Multiplicative inverses are pairs $(a,b)$ where $a cdot b = 1 text{ mod m}$.
$2 cdot 26 text{ mod m }$ isn't $1$ but $24$.



Multiplicative inverses are thus:



Prelude> [(x,y)|x<-[1..28],y<-[1..28],x*y `mod` 28 == 1]
[(1,1),(3,19),(5,17),(9,25),(11,23),(13,13),(15,15),(17,5),(19,3),(23,11),(25,9),(27,27)]


If $$s cdot r = 1$$ then $$(m-r)cdot(m-s) = 1$$ which means that if you have a pair of multiplicative inverses you get another one for free.



$$(m-r)cdot(m-s) = mcdot m -rm -sm +rs = rs = 1$$



It's obvious that $1$ is always a self-inverse because $1 cdot 1 = 1$.
This also means that $m-1$ is necessarily a self-inverse. If $(3,19)$ are inverses then $(28-3,28-19) = (25,9)$ thus if $(3,19)$ is a pair of inverses then $(25,9)$ must be a pair of multiplicative inverses as well.






share|cite|improve this answer





























    0














    The extended Euclidean algorithm is probably your best tool for anything but obvious multiplicative inverses. For simple inverses it can be useful to get comfortable with using negative congruences too, so $13equiv -4 bmod 17 $ and since $4^2equiv -1$ then $4cdot -4 equiv 1 bmod 17$.



    To illustrate the extended Euclidean algorithm I'll use your example of finding $321^{-1} bmod 56789$ (although not $56709$, since then they have a common factor of $3$). This proceeds effectively by finding a series of equations satisfying $n = 56789s +321t$, starting with $n = 56789$ and $n=321$ and proceeding to smaller values of $n$, until - if possible - $n=1$.



    $begin{array}{c|c}
    n & s & t & q \ hline
    56789 & 1 & 0 & \
    321 & 0 & 1 & 176 \
    293 & 1 & -176 & 1 \
    28 & -1 & 177 & 10 \
    13 & 11 & -1946 & 2 \
    2 & -23 & 4069 & 6 \
    1 & 149 & -26360 & \
    end{array}$



    $q$ represents the multiplier to get a close match for the $n$ values of the previous two equations, giving the best reduction in $n$ for the next line.



    The final equation here says that $1 = 56789cdot 149 + 321cdot(-26360)$. This of course means that $ 321cdot(-26360) equiv 1 bmod 56789$ or, converting to a positive congruence, $321^{-1} equiv 30429 bmod 56789$.



    The same process for finding $13^{-1} bmod 17$ works also of course:



    $begin{array}{c|c}
    n & s & t & q \ hline
    17 & 1 & 0 & \
    13 & 0 & 1 & 1 \
    4 & 1 & -1 & 3 \
    1 & -3 & color{red}{4} & \
    end{array}$



    For finding a full set of multiplicative inverses, we do have the advantage of generally only having to find less than half of them. Your listing of $Bbb Z_{28}^times$ includes some numbers that should not be there, since they do not have inverses - all those numbers which share a factor with $28$. The correct listing then is $Bbb Z_{28}^times = {1,3,5,9,11,13,15,17,19,23,25,27}$. $1$ is the identity already and $-1equiv 27bmod 28$ is self-inverse (always true for $1$ less than the modulus). Then we can look for multiples of the small numbers either side of the low multiples of $28$ (all equivalences $bmod 28$):



    $3cdot 9 =27equiv -1 implies 3^{-1}equiv -9 equiv 19$

    $5cdot 11 =55equiv -1 implies 5^{-1}equiv -11 equiv 17$

    from $3$'s result $9^{-1}equiv -3equiv 25$

    from $5$'s result $11^{-1}equiv -5equiv 23$

    $13cdot 15 = (14-1)(14+1) equiv -1 implies 13^{-1}equiv -15equiv 13$

    and similarly $15^{-1}equiv -13equiv 15$



    with the other results being the other half of established inverse pairs, giving the full result:



    ${(1), (3,19), (5,17), (9,25), (11,23), (13), (15), (27)}$



    single items being self-inverse.






    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%2f1125366%2fmodular-arithmetic-pairs-of-additive-inverse-pairs-and-multiplicative-inverse%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









      0














      Multiplicative inverses are pairs $(a,b)$ where $a cdot b = 1 text{ mod m}$.
      $2 cdot 26 text{ mod m }$ isn't $1$ but $24$.



      Multiplicative inverses are thus:



      Prelude> [(x,y)|x<-[1..28],y<-[1..28],x*y `mod` 28 == 1]
      [(1,1),(3,19),(5,17),(9,25),(11,23),(13,13),(15,15),(17,5),(19,3),(23,11),(25,9),(27,27)]


      If $$s cdot r = 1$$ then $$(m-r)cdot(m-s) = 1$$ which means that if you have a pair of multiplicative inverses you get another one for free.



      $$(m-r)cdot(m-s) = mcdot m -rm -sm +rs = rs = 1$$



      It's obvious that $1$ is always a self-inverse because $1 cdot 1 = 1$.
      This also means that $m-1$ is necessarily a self-inverse. If $(3,19)$ are inverses then $(28-3,28-19) = (25,9)$ thus if $(3,19)$ is a pair of inverses then $(25,9)$ must be a pair of multiplicative inverses as well.






      share|cite|improve this answer


























        0














        Multiplicative inverses are pairs $(a,b)$ where $a cdot b = 1 text{ mod m}$.
        $2 cdot 26 text{ mod m }$ isn't $1$ but $24$.



        Multiplicative inverses are thus:



        Prelude> [(x,y)|x<-[1..28],y<-[1..28],x*y `mod` 28 == 1]
        [(1,1),(3,19),(5,17),(9,25),(11,23),(13,13),(15,15),(17,5),(19,3),(23,11),(25,9),(27,27)]


        If $$s cdot r = 1$$ then $$(m-r)cdot(m-s) = 1$$ which means that if you have a pair of multiplicative inverses you get another one for free.



        $$(m-r)cdot(m-s) = mcdot m -rm -sm +rs = rs = 1$$



        It's obvious that $1$ is always a self-inverse because $1 cdot 1 = 1$.
        This also means that $m-1$ is necessarily a self-inverse. If $(3,19)$ are inverses then $(28-3,28-19) = (25,9)$ thus if $(3,19)$ is a pair of inverses then $(25,9)$ must be a pair of multiplicative inverses as well.






        share|cite|improve this answer
























          0












          0








          0






          Multiplicative inverses are pairs $(a,b)$ where $a cdot b = 1 text{ mod m}$.
          $2 cdot 26 text{ mod m }$ isn't $1$ but $24$.



          Multiplicative inverses are thus:



          Prelude> [(x,y)|x<-[1..28],y<-[1..28],x*y `mod` 28 == 1]
          [(1,1),(3,19),(5,17),(9,25),(11,23),(13,13),(15,15),(17,5),(19,3),(23,11),(25,9),(27,27)]


          If $$s cdot r = 1$$ then $$(m-r)cdot(m-s) = 1$$ which means that if you have a pair of multiplicative inverses you get another one for free.



          $$(m-r)cdot(m-s) = mcdot m -rm -sm +rs = rs = 1$$



          It's obvious that $1$ is always a self-inverse because $1 cdot 1 = 1$.
          This also means that $m-1$ is necessarily a self-inverse. If $(3,19)$ are inverses then $(28-3,28-19) = (25,9)$ thus if $(3,19)$ is a pair of inverses then $(25,9)$ must be a pair of multiplicative inverses as well.






          share|cite|improve this answer












          Multiplicative inverses are pairs $(a,b)$ where $a cdot b = 1 text{ mod m}$.
          $2 cdot 26 text{ mod m }$ isn't $1$ but $24$.



          Multiplicative inverses are thus:



          Prelude> [(x,y)|x<-[1..28],y<-[1..28],x*y `mod` 28 == 1]
          [(1,1),(3,19),(5,17),(9,25),(11,23),(13,13),(15,15),(17,5),(19,3),(23,11),(25,9),(27,27)]


          If $$s cdot r = 1$$ then $$(m-r)cdot(m-s) = 1$$ which means that if you have a pair of multiplicative inverses you get another one for free.



          $$(m-r)cdot(m-s) = mcdot m -rm -sm +rs = rs = 1$$



          It's obvious that $1$ is always a self-inverse because $1 cdot 1 = 1$.
          This also means that $m-1$ is necessarily a self-inverse. If $(3,19)$ are inverses then $(28-3,28-19) = (25,9)$ thus if $(3,19)$ is a pair of inverses then $(25,9)$ must be a pair of multiplicative inverses as well.







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered Jan 18 '17 at 19:31









          mromanmroman

          1333




          1333























              0














              The extended Euclidean algorithm is probably your best tool for anything but obvious multiplicative inverses. For simple inverses it can be useful to get comfortable with using negative congruences too, so $13equiv -4 bmod 17 $ and since $4^2equiv -1$ then $4cdot -4 equiv 1 bmod 17$.



              To illustrate the extended Euclidean algorithm I'll use your example of finding $321^{-1} bmod 56789$ (although not $56709$, since then they have a common factor of $3$). This proceeds effectively by finding a series of equations satisfying $n = 56789s +321t$, starting with $n = 56789$ and $n=321$ and proceeding to smaller values of $n$, until - if possible - $n=1$.



              $begin{array}{c|c}
              n & s & t & q \ hline
              56789 & 1 & 0 & \
              321 & 0 & 1 & 176 \
              293 & 1 & -176 & 1 \
              28 & -1 & 177 & 10 \
              13 & 11 & -1946 & 2 \
              2 & -23 & 4069 & 6 \
              1 & 149 & -26360 & \
              end{array}$



              $q$ represents the multiplier to get a close match for the $n$ values of the previous two equations, giving the best reduction in $n$ for the next line.



              The final equation here says that $1 = 56789cdot 149 + 321cdot(-26360)$. This of course means that $ 321cdot(-26360) equiv 1 bmod 56789$ or, converting to a positive congruence, $321^{-1} equiv 30429 bmod 56789$.



              The same process for finding $13^{-1} bmod 17$ works also of course:



              $begin{array}{c|c}
              n & s & t & q \ hline
              17 & 1 & 0 & \
              13 & 0 & 1 & 1 \
              4 & 1 & -1 & 3 \
              1 & -3 & color{red}{4} & \
              end{array}$



              For finding a full set of multiplicative inverses, we do have the advantage of generally only having to find less than half of them. Your listing of $Bbb Z_{28}^times$ includes some numbers that should not be there, since they do not have inverses - all those numbers which share a factor with $28$. The correct listing then is $Bbb Z_{28}^times = {1,3,5,9,11,13,15,17,19,23,25,27}$. $1$ is the identity already and $-1equiv 27bmod 28$ is self-inverse (always true for $1$ less than the modulus). Then we can look for multiples of the small numbers either side of the low multiples of $28$ (all equivalences $bmod 28$):



              $3cdot 9 =27equiv -1 implies 3^{-1}equiv -9 equiv 19$

              $5cdot 11 =55equiv -1 implies 5^{-1}equiv -11 equiv 17$

              from $3$'s result $9^{-1}equiv -3equiv 25$

              from $5$'s result $11^{-1}equiv -5equiv 23$

              $13cdot 15 = (14-1)(14+1) equiv -1 implies 13^{-1}equiv -15equiv 13$

              and similarly $15^{-1}equiv -13equiv 15$



              with the other results being the other half of established inverse pairs, giving the full result:



              ${(1), (3,19), (5,17), (9,25), (11,23), (13), (15), (27)}$



              single items being self-inverse.






              share|cite|improve this answer


























                0














                The extended Euclidean algorithm is probably your best tool for anything but obvious multiplicative inverses. For simple inverses it can be useful to get comfortable with using negative congruences too, so $13equiv -4 bmod 17 $ and since $4^2equiv -1$ then $4cdot -4 equiv 1 bmod 17$.



                To illustrate the extended Euclidean algorithm I'll use your example of finding $321^{-1} bmod 56789$ (although not $56709$, since then they have a common factor of $3$). This proceeds effectively by finding a series of equations satisfying $n = 56789s +321t$, starting with $n = 56789$ and $n=321$ and proceeding to smaller values of $n$, until - if possible - $n=1$.



                $begin{array}{c|c}
                n & s & t & q \ hline
                56789 & 1 & 0 & \
                321 & 0 & 1 & 176 \
                293 & 1 & -176 & 1 \
                28 & -1 & 177 & 10 \
                13 & 11 & -1946 & 2 \
                2 & -23 & 4069 & 6 \
                1 & 149 & -26360 & \
                end{array}$



                $q$ represents the multiplier to get a close match for the $n$ values of the previous two equations, giving the best reduction in $n$ for the next line.



                The final equation here says that $1 = 56789cdot 149 + 321cdot(-26360)$. This of course means that $ 321cdot(-26360) equiv 1 bmod 56789$ or, converting to a positive congruence, $321^{-1} equiv 30429 bmod 56789$.



                The same process for finding $13^{-1} bmod 17$ works also of course:



                $begin{array}{c|c}
                n & s & t & q \ hline
                17 & 1 & 0 & \
                13 & 0 & 1 & 1 \
                4 & 1 & -1 & 3 \
                1 & -3 & color{red}{4} & \
                end{array}$



                For finding a full set of multiplicative inverses, we do have the advantage of generally only having to find less than half of them. Your listing of $Bbb Z_{28}^times$ includes some numbers that should not be there, since they do not have inverses - all those numbers which share a factor with $28$. The correct listing then is $Bbb Z_{28}^times = {1,3,5,9,11,13,15,17,19,23,25,27}$. $1$ is the identity already and $-1equiv 27bmod 28$ is self-inverse (always true for $1$ less than the modulus). Then we can look for multiples of the small numbers either side of the low multiples of $28$ (all equivalences $bmod 28$):



                $3cdot 9 =27equiv -1 implies 3^{-1}equiv -9 equiv 19$

                $5cdot 11 =55equiv -1 implies 5^{-1}equiv -11 equiv 17$

                from $3$'s result $9^{-1}equiv -3equiv 25$

                from $5$'s result $11^{-1}equiv -5equiv 23$

                $13cdot 15 = (14-1)(14+1) equiv -1 implies 13^{-1}equiv -15equiv 13$

                and similarly $15^{-1}equiv -13equiv 15$



                with the other results being the other half of established inverse pairs, giving the full result:



                ${(1), (3,19), (5,17), (9,25), (11,23), (13), (15), (27)}$



                single items being self-inverse.






                share|cite|improve this answer
























                  0












                  0








                  0






                  The extended Euclidean algorithm is probably your best tool for anything but obvious multiplicative inverses. For simple inverses it can be useful to get comfortable with using negative congruences too, so $13equiv -4 bmod 17 $ and since $4^2equiv -1$ then $4cdot -4 equiv 1 bmod 17$.



                  To illustrate the extended Euclidean algorithm I'll use your example of finding $321^{-1} bmod 56789$ (although not $56709$, since then they have a common factor of $3$). This proceeds effectively by finding a series of equations satisfying $n = 56789s +321t$, starting with $n = 56789$ and $n=321$ and proceeding to smaller values of $n$, until - if possible - $n=1$.



                  $begin{array}{c|c}
                  n & s & t & q \ hline
                  56789 & 1 & 0 & \
                  321 & 0 & 1 & 176 \
                  293 & 1 & -176 & 1 \
                  28 & -1 & 177 & 10 \
                  13 & 11 & -1946 & 2 \
                  2 & -23 & 4069 & 6 \
                  1 & 149 & -26360 & \
                  end{array}$



                  $q$ represents the multiplier to get a close match for the $n$ values of the previous two equations, giving the best reduction in $n$ for the next line.



                  The final equation here says that $1 = 56789cdot 149 + 321cdot(-26360)$. This of course means that $ 321cdot(-26360) equiv 1 bmod 56789$ or, converting to a positive congruence, $321^{-1} equiv 30429 bmod 56789$.



                  The same process for finding $13^{-1} bmod 17$ works also of course:



                  $begin{array}{c|c}
                  n & s & t & q \ hline
                  17 & 1 & 0 & \
                  13 & 0 & 1 & 1 \
                  4 & 1 & -1 & 3 \
                  1 & -3 & color{red}{4} & \
                  end{array}$



                  For finding a full set of multiplicative inverses, we do have the advantage of generally only having to find less than half of them. Your listing of $Bbb Z_{28}^times$ includes some numbers that should not be there, since they do not have inverses - all those numbers which share a factor with $28$. The correct listing then is $Bbb Z_{28}^times = {1,3,5,9,11,13,15,17,19,23,25,27}$. $1$ is the identity already and $-1equiv 27bmod 28$ is self-inverse (always true for $1$ less than the modulus). Then we can look for multiples of the small numbers either side of the low multiples of $28$ (all equivalences $bmod 28$):



                  $3cdot 9 =27equiv -1 implies 3^{-1}equiv -9 equiv 19$

                  $5cdot 11 =55equiv -1 implies 5^{-1}equiv -11 equiv 17$

                  from $3$'s result $9^{-1}equiv -3equiv 25$

                  from $5$'s result $11^{-1}equiv -5equiv 23$

                  $13cdot 15 = (14-1)(14+1) equiv -1 implies 13^{-1}equiv -15equiv 13$

                  and similarly $15^{-1}equiv -13equiv 15$



                  with the other results being the other half of established inverse pairs, giving the full result:



                  ${(1), (3,19), (5,17), (9,25), (11,23), (13), (15), (27)}$



                  single items being self-inverse.






                  share|cite|improve this answer












                  The extended Euclidean algorithm is probably your best tool for anything but obvious multiplicative inverses. For simple inverses it can be useful to get comfortable with using negative congruences too, so $13equiv -4 bmod 17 $ and since $4^2equiv -1$ then $4cdot -4 equiv 1 bmod 17$.



                  To illustrate the extended Euclidean algorithm I'll use your example of finding $321^{-1} bmod 56789$ (although not $56709$, since then they have a common factor of $3$). This proceeds effectively by finding a series of equations satisfying $n = 56789s +321t$, starting with $n = 56789$ and $n=321$ and proceeding to smaller values of $n$, until - if possible - $n=1$.



                  $begin{array}{c|c}
                  n & s & t & q \ hline
                  56789 & 1 & 0 & \
                  321 & 0 & 1 & 176 \
                  293 & 1 & -176 & 1 \
                  28 & -1 & 177 & 10 \
                  13 & 11 & -1946 & 2 \
                  2 & -23 & 4069 & 6 \
                  1 & 149 & -26360 & \
                  end{array}$



                  $q$ represents the multiplier to get a close match for the $n$ values of the previous two equations, giving the best reduction in $n$ for the next line.



                  The final equation here says that $1 = 56789cdot 149 + 321cdot(-26360)$. This of course means that $ 321cdot(-26360) equiv 1 bmod 56789$ or, converting to a positive congruence, $321^{-1} equiv 30429 bmod 56789$.



                  The same process for finding $13^{-1} bmod 17$ works also of course:



                  $begin{array}{c|c}
                  n & s & t & q \ hline
                  17 & 1 & 0 & \
                  13 & 0 & 1 & 1 \
                  4 & 1 & -1 & 3 \
                  1 & -3 & color{red}{4} & \
                  end{array}$



                  For finding a full set of multiplicative inverses, we do have the advantage of generally only having to find less than half of them. Your listing of $Bbb Z_{28}^times$ includes some numbers that should not be there, since they do not have inverses - all those numbers which share a factor with $28$. The correct listing then is $Bbb Z_{28}^times = {1,3,5,9,11,13,15,17,19,23,25,27}$. $1$ is the identity already and $-1equiv 27bmod 28$ is self-inverse (always true for $1$ less than the modulus). Then we can look for multiples of the small numbers either side of the low multiples of $28$ (all equivalences $bmod 28$):



                  $3cdot 9 =27equiv -1 implies 3^{-1}equiv -9 equiv 19$

                  $5cdot 11 =55equiv -1 implies 5^{-1}equiv -11 equiv 17$

                  from $3$'s result $9^{-1}equiv -3equiv 25$

                  from $5$'s result $11^{-1}equiv -5equiv 23$

                  $13cdot 15 = (14-1)(14+1) equiv -1 implies 13^{-1}equiv -15equiv 13$

                  and similarly $15^{-1}equiv -13equiv 15$



                  with the other results being the other half of established inverse pairs, giving the full result:



                  ${(1), (3,19), (5,17), (9,25), (11,23), (13), (15), (27)}$



                  single items being self-inverse.







                  share|cite|improve this answer












                  share|cite|improve this answer



                  share|cite|improve this answer










                  answered Oct 6 '17 at 3:27









                  JoffanJoffan

                  32.2k43169




                  32.2k43169






























                      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%2f1125366%2fmodular-arithmetic-pairs-of-additive-inverse-pairs-and-multiplicative-inverse%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

                      1300-talet

                      1300-talet

                      Display a custom attribute below product name in the front-end Magento 1.9.3.8