Results 1 to 3 of 3

Math Help - Modular arithmetic

  1. #1
    Newbie
    Joined
    May 2011
    Posts
    5

    Exclamation Modular arithmetic

    Hello!
    Can someone please tell me how to calculate the value of the general form
    a^(-1) mod b?
    A particular example is 97^(-1) mod 4060?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Euclidean algorithm.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Behold, the power of SARDINES!
    TheEmptySet's Avatar
    Joined
    Feb 2008
    From
    Yuma, AZ, USA
    Posts
    3,764
    Thanks
    78
    Quote Originally Posted by nicola5 View Post
    Hello!
    Can someone please tell me how to calculate the value of the general form
    a^(-1) mod b?
    A particular example is 97^(-1) mod 4060?
    You need to use the Euclidean algorithm

    4060=41\cdot 97 +83 \iff 83=4060-41\cdot 97

    97=1\cdot 83 +14 \iff 14 =97-1\cdot 83

    83=5\cdot 14+13 \iff 13=83-5\cdot 14

    14=1\cdot 13+1 \iff 1=14-1\cdot 13

    Now we just need to back substitute to get 1 as a linear combination of 4060 and 97

    1=14-1(83-5\cdot 14)=6\cdot 14-1\cdot 83

    1=6(97-1\cdot 83)-1\cdot 83=6\cdot 97-7\cdot 83

    1=6\cdot 97-7\cdot (4060-41\cdot 97)=293\cdot 97-7\cdot 4060

    1=293\cdot 97-7\cdot 4060 \iff (293)(97) \equiv 1 \mod (4060)

    So 97 is the inverse of 293 mod 4060

    Note that this only works if they are coprime
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. modular arithmetic help
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 9th 2011, 05:50 AM
  2. Modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 3rd 2011, 11:07 PM
  3. Modular Arithmetic
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 28th 2010, 05:08 AM
  4. Modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 13th 2008, 03:17 PM
  5. modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 25th 2007, 08:39 PM

Search Tags


/mathhelpforum @mathhelpforum