Efficient Methods for Finding Inverses in Zn

[tonit]

Homework Statement

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

 

[I like Serena]

Homework Statement

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

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.

 

[tonit]

ok. Thank you!...very helpful

 

[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.

 

[tonit]

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