Calculate the multiplicative inverse of $5$ in $\mathbb{Z}_{12}$

$\begingroup$

Calculate the multiplicative inverse of $5$ in $\mathbb{Z}_{12}$ using euclidean algorithm.

I think I got it but the end is a bit confusing, how to know what number is the multiplicative invererse..?

First of all, $5$ must have a multiplicative inverse in $\mathbb{Z}_{12}$ because $\text{gcd}(12,5)=1$

Then

$$5x \equiv1 \text{ mod } 12$$

$$x \equiv 5^{-1} (\text{mod }12)$$

$$12 = 2 \cdot 5+2$$

$$5 = 2 \cdot 2+1$$

$$1 = 5-2 \cdot 2$$

$$1 = 5-2 \cdot (12 - 2 \cdot 5)$$

$$1=5-2 \cdot 12 +4 \cdot 5$$

$$1 = -2 \cdot 12+5 \cdot 5$$

Fine but how do I know that the multiplicative inverse of $5$ in $\mathbb{Z}_{12}$ is $5$?

Because in last line we have several numbers, how to know which one is the one we are looking for?

$\endgroup$ 2

1 Answer

$\begingroup$

$$1=−2⋅12+5⋅5$$ This means that $\color{red}{5}\cdot \color{blue}{5}= 1 + 2\cdot 12 \equiv 1 \bmod12$, so $\color{blue}{5}$ is the inverse of $\color{red}{5}$ mod $12$.

$\endgroup$

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy