How can you calculate the multiplicative inverse using euclidean algorithm (I tried on an example)?

312 Views Asked by At

I'd finally like to know the exact way how it's done, if it's possible at all. I know sometimes it might be better to avoid euclid but I have to know how it's done by using this.

Here is an example I made myself and I hope it's a good one.

Find the multiplicative inverse of $11$ in $\mathbb{Z_{12}}$

We can also write: $\text{ gcd }(11,12)=1$

$$12=11\cdot1+1$$

$$11=1 \cdot 11+0$$

Now $1=12-11\cdot 1$

I don't think we can do anything from here now.. But what does this tell us, what's the multiplicative inverse now? How can we know it from this notation? Did I do it correct at all? Please do tell me!

1

There are 1 best solutions below

3
On BEST ANSWER

Finding the multiplicative inverse of $a $ modulus $m $ is finding the solution to $ax \equiv 1 \mod m $

We know that equation has a solution iff $\gcd(a, m) $ divides 1, which implies $\gcd(a, m) = 1$

If that is the case, then from the euclidean algorithm to find the gcd you know you can have

$$1 = x_0a + y_0m $$

With $x_0, y_0 $ integers. Right? But taking that modulus $m $ we get

$$1 \equiv x_0a + y_0m \mod m \iff 1 \equiv x_0a \mod m$$

And thus $x_0$ is $a $'s multiplicative inverse.

For your specific case we have $\gcd(11, 12) = 1$ so 11 has a multiplicative inverse. From the euclidean algorithm we can see, as you wrote, that $1 = 1\cdot12 - 1\cdot11$.

Here we have $x_0 = -1$ and $y_0 = 1$. So it follows that $x_0 = -1$ is the multiplicative inverse of 11 modulus 12:

$$-1 \equiv 11 \mod 11 \Rightarrow (-1)\cdot11 \equiv 1 \mod 12 \iff (11)\cdot11 \equiv 1 \mod 12 \iff 121 \equiv 1 \mod 12$$

But $121 = 10\cdot12 + 1 \Rightarrow 121 \equiv 1 \mod12$ showing that 11 is its own multiplicative inverse.