Results 1 to 7 of 7

Math Help - Modular arithmetic

  1. #1
    Newbie
    Joined
    Jan 2010
    Posts
    9

    Modular arithmetic

    Hello,

    How can I compute:

    17^{-1} mod 23 ?

    Regards.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    The two ways I know of are: (1) Extended Euclidean algorithm (2) Modular exponentiation. See here for some discussion. If you'd like an example, just ask, and I or someone else will provide one.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by Migotek84 View Post
    Hello,

    How can I compute:

    17^{-1} mod 23 ?

    Regards.
    17=-6=(-2)\cdot 3\!\!\pmod {23}\,,\,\,2^{-1}=12\!\!\pmod {23}\Longrightarrow -2^{-1}=-12=11\!\!\pmod {23} ,  3^{-1}=8\!\!\pmod {23}\Longrightarrow 17^{-1}=(-2)^{-1}\cdot 3^{-1}=11\cdot 8=19\!\!\pmod{23}

    Tonio
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Jan 2009
    Posts
    715
    There is a general method to find the inverse , you know , it is Euclidean Algorithm , but i promise once you have practised a lot , it would be very easy for you to solve , without Euclidian Algorithm .

     [17^{-1}] = [ \frac{1}{17} ] = \frac{[-1]}{[6]} = \frac{[ - 4 ] }{[24]} =  [-4 ] = [19]
    Last edited by simplependulum; June 20th 2010 at 10:02 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Also, without going too deeply in the number theoretical realm, if you know the Euler totient of the modulus, you can efficiently compute :

    17^{\varphi{(23)} - 1} \equiv 17^{-1} \pmod{23}

    In order to do this you use the modular exponentiation (square and multiply) algorithm, and \varphi{(23)} is the Euler totient of 23 (which incidentally equals 22).
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,814
    Thanks
    703
    Hello, Migotek84!


    Here's a very primitive method . . .



    Compute: . 17^{-1}\text{ (mod 23)}

    Let: . x \:\equiv\:17^{-1}\text{ (mod 23)}

    Multiply by 17: . 17x \:\equiv\:1\text{ (mod 23)}

    Then: . 17x \:=\:23a + 1\:\text{ for some integer }a.

    \text{Solve for }x\!:\;\;x \:=\:\dfrac{23a+1}{17} \:=\:a + \dfrac{6a+1}{17} .[1]


    Since x is an integer, 6a+1 is a multiple of 17.

    . . 6a+1 \:=\:17b\:\text{ for some integer }b.

    \text{Solve for }a\!:\;\;a \:=\:\dfrac{17b-1}{6} \:=\:2b + \dfrac{5b-1}{6} .[2]


    Since a is an integer, 5b-1 is a multiple of 6.

    . . 5b-1 \:=\:6c\:\text{ for some integer }c.

    \text{Solve for }b\!:\;\;b \:=\:\dfrac{6c+1}{5} \:=\:c + \dfrac{c+1}{5} .[3]


    Since b is an integer, c+1 is a multiple of 5.
    . . The first time this happens is when . c = 4


    Substitute into [3]: . b \:=\:4 + \frac{4+1}{5} \quad\Rightarrow\quad b \:=\:5

    Substitute into [2]: . a \:=\:2(5) + \frac{5(5)-1}{6} \quad\Rightarrow\quad a \:=\:14

    Substitute into [1]: . x \:=\:14 + \frac{6(14)+1}{17} \quad\Rightarrow\quad x \:=\:19


    Therefore: . 19\:\equiv\:17^{-1}\text{ (mod 23)}

    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Hey Soroban,
    I remember having seen this method on some Wikipedia article, when I first discovered modular arithmetic (nearly a year ago). I really liked it, if I recall correctly this is the Euclidian Algorithm backwards, right ?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 3rd 2011, 11:07 PM
  2. Modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 3rd 2011, 01:37 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