1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Finding inverses in Z mod n

  1. Jun 19, 2012 #1
    1. The problem statement, all variables and given/known data

    Let's say I want to find the inverse of [itex]\bar{4}[/itex] in [itex]\mathbb{Z}_{13}[/itex].

    So I get [itex]13 = 4\cdot 3 + 1[/itex] and so [itex]1 = 13 - 4\cdot 3[/itex].

    But this doesn't show that [itex]3[/itex] is inverse of [itex]4[/itex]. So I have to express [itex]4 = 3\cdot 1 + 1[/itex]
    which yields that [itex]1 = 4 - 1\cdot 3 = 4 - 3\cdot (13 - 3\cdot 4) = 10\cdot 4 - 3 \cdot 13[/itex] from where I get that [itex]\bar{10}[/itex] is inverse of [itex]\bar{4}[/itex] mod [itex]13[/itex].

    So which is the right way for finding inverses in Zn? I'm attaching a screenshot from my book
     

    Attached Files:

    Last edited: Jun 19, 2012
  2. jcsd
  3. Jun 19, 2012 #2

    I like Serena

    User Avatar
    Homework Helper

    Hi tonit! :smile:

    You're trying to find x with ##4x \equiv 1 \pmod{13}##.

    Since you already have ##13 = 4\cdot 3 + 1##, it follows that ##4 \cdot 3 \equiv -1 \pmod{13}##.
    That's almost, but not quite what you need.

    So let's multiply left and right by -1.
    Then you get:
    $$4 \cdot -3 \equiv 1 \pmod{13}$$
    Much closer!

    It follows that ##4^{-1} \equiv -3 \equiv 10 \pmod{13}##.


    Note that with bigger numbers you typically need the euclidean algorithm to find the inverse.
    For that, I suspect you'll need to learn how to apply this algorithm.
     
  4. Jun 19, 2012 #3
    ok. Thank you!...very helpful
     
  5. Jun 19, 2012 #4

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    More generally, to find the inverse of a, modulo n, you are looking for an integer b< n such that ab= 1 (mod n) which is the same as saying ab= kn+ 1 for some integer n.

    That is the same as solving the Diophantine equation ab- kn= 1 where a and n are known and you want to find integers b and k. To find the multiplicative inverse of 4 modulo 13, we want to solve 4b- 13k= 1 and can do that using the Euclidean Algorithm as I like Serena suggests:
    4 divides into 13 three times with remainder 1 so we have immediately 13(1)= 4(3)+ 1 so that 4(-3)+ 13(1)= 4(-3)- 13(-1)= 1. One solution is a= -3 which is the same as -3+ 13= 10 mod 13.

    Here's how that would work for "bigger numbers": If the problem were, say, to find the multiplicative inverse of 24 modulo 111, we would look for x such that 24x= 1 (mod 113) which is the same as 24x= 113k+ 1 or 24x- 113k= 1.

    24 divides into 113 four times with remainder 17 so that 113(1)- 24(4)= 17. 17 divides into 24 once with remainder 7: 24(1)- 17(1)= 7. 7 divides into 17 twice with remainder 3: 17(1)- 7(2)= 3. Finally, 3 divides into 7 twice with remainder 1: 7- 3(2)= 1.

    Replacing that "3" in the last equation with 17(1)- 7(2) from the previous equation gives 7- (17(1)- 7(2))2= 7(5)- 17(2)= 1. Replacing that "7" with 24(1)- 17(1) gives (24(1)- 17(1))(5)- 17(2)= 24(5)- 17(7)= 1. Replacing that "17" with 113(1)- 24(4) gives 24(5)- (113(1)- 24(4))7= 24(33)- 113(7)= 1.

    That is, one solution to 24x- 113k= 1 is x= 33, k= 7 and tells us that the multiplicative inverse of 24, modulo 113, is 33: 24(33)= 792= 7(113)+ 1.
     
    Last edited: Jun 20, 2012
  6. Jun 20, 2012 #5
    Thank you HallsofIvy. It's all clear now :D
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook