Use euclidean algorithm to calculate the multiplicative inverse of $5$ in $\mathbb{Z}_{12}$

Question

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.

Answer 1

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 :).

Answer 2

You have $$1=−2⋅12+5⋅5$$

So modulo $12$ you have

$$1\equiv 5\cdot 5$$

Which is just what you want.

Answer 3

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}$.