1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ $-2×12 \equiv -2×0 \equiv 0 \pmod 12$, so you're left with $1\equiv 5×5$. You should write this equivalence as a step in your calculation, as the conclusion you want (the inverse of whatever you're working with) is then immediately consequential. $\endgroup$ – Nij Nov 13 '16 at 12:00
2
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

So modulo $12$ you have

$$1\equiv 5\cdot 5$$

Which is just what you want.

$\endgroup$
  • $\begingroup$ Alright. What if we were asked to say multiplicative inverse of $3$ in $Z_{13}$? My final calc is: $1=13-4 \cdot 3$. Then, $13-4=9$ so multiplicative inverse is $9$? Thanks a lot so far :) $\endgroup$ – berndgr Nov 13 '16 at 11:58
  • 1
    $\begingroup$ Well, it's easy enough to check that answer: just multiply $3$ by $9$, take the remainder $\bmod 13$, and see what you get. $\endgroup$ – TonyK Nov 13 '16 at 12:07
2
$\begingroup$

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

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.