Finding inverses in Z mod n

1. Jun 19, 2012

tonit

1. The problem statement, all variables and given/known data

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

So I get $13 = 4\cdot 3 + 1$ and so $1 = 13 - 4\cdot 3$.

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

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

Attached Files:

• ATATATATATA.JPG
File size:
13.5 KB
Views:
145
Last edited: Jun 19, 2012
2. Jun 19, 2012

I like Serena

Hi tonit!

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.

3. Jun 19, 2012

tonit

4. Jun 19, 2012

HallsofIvy

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
5. Jun 20, 2012

tonit

Thank you HallsofIvy. It's all clear now :D