Use euclidean algorithm to calculate the multiplicative inverse of $5$ in $\mathbb{Z}_{12}$ I really like to know the exact way how its done. Here is what I wrote:
$5$ must have a multiplicative inverse because $\text{ gcd }(12,5)=1$
So $5x \equiv 1 \text{ mod } 12 \Leftrightarrow x \equiv 5^{-1}(\text{mod } 12)$
$$12=5 \cdot 2+2$$
$$5=2 \cdot 2+1$$
$$2=1 \cdot 2+0$$
$\Rightarrow$
$$1=5-2 \cdot 2$$
$$1=5-2 \cdot (12-5 \cdot 2)$$
$$1=5-2 \cdot 12+4 \cdot 5$$
$$1=-2 \cdot 12 + 5 \cdot 5$$
From an online calculator, I know that $5$ is its own inverse. But how do you know that from the last notation?
Please don't explain it too complicated, I have very big troubles in understanding it and I'm already very happy I was able to calculate it till here myself.
 A: You have $$1=−2⋅12+5⋅5$$
So modulo $12$ you have
$$1\equiv 5\cdot 5$$
Which is just what you want.
A: Take a very close look at the last line:
$$1 = -2 \cdot 12 + 5 \cdot 5.$$
Literally this is saying that $1$ is the sum of a multiple of $12$ and $5\cdot 5$.  Since $5\cdot 5$ differs from $1$ by a multiple of $12$, this means $5\cdot 5 \equiv 1 \pmod{12}$, so $5$ is an inverse of $5$ modulo $12$.
More generally, any time you have an integer identity of the form
$$1 = m\cdot n + a\cdot b,$$
you can, if you read carefully, conclude quite a few related facts, such as:


*

*$a$ is the inverse of $b$ modulo $n$,

*$b$ is the inverse of $a$ modulo $n$,

*$a$ is the inverse of $b$ modulo $m$,

*$m$ is the inverse of $n$ modulo $a$,

*$n$ is the inverse of $m$ modulo $b$,

*etc.


The Euclidean algorithm is very powerful indeed :).
A: I will show you how to do it through continued fractions, that is essentially the same. We have:
$$\frac{12}{5}=2+\frac{2}{5}= 2 +\frac{1}{2+\frac{1}{2}} = [2;2,2]\tag{1}$$
and if $\frac{p_n}{q_n},\frac{p_{n+1}}{q_{n+1}}$ are two consecutive convergents of the same continued fraction, the difference between them is $\pm\frac{1}{q_n q_{n+1}}$. In our case $[2;2] = \frac{5}{2}$, and
$$ \frac{12}{5}-\frac{5}{2} = -\frac{1}{10} \tag{2} $$
leads to:
$$ 12\cdot 2 - 5\cdot 5 = -1,\quad 5\cdot 5 = 2\cdot 12+1 \tag{3} $$
hence $5$ is the inverse of itself $\!\!\pmod{12}$.
