Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: 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
    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 by a moderator: Jun 20, 2012
  6. Jun 20, 2012 #5
    Thank you HallsofIvy. It's all clear now :D
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook