Basic modular inverses

Question

I know how to do modular inverses in a hypothetical sense with the Euclidian method, and have been trying to do the, but I seem to keep getting the incorrect answer.

I'm trying to find the inverse of $\;5\pmod {13}$, for example. The answer should be 8, but I can't seem to get that. These are my steps:
\begin{align} 13 & = 2(5)+3\\ 5 & = 1(3)+2\\ 3 & =1(2)+1 \end{align}

\begin{align} 1 & =3-1(2)\\ & =3-1(5-1(3))\\ & = 2(3)-5\\ & = 2(13-2(5))-5\\ & = 2(13)-4(5)-5\\ & = 2(13)-5(5) \end{align}

I'm sure I'm just misunderstanding the steps, but I don't know how.

Also, can the same method to used to find the inverse of $5\pmod{11}$, since $11=2(5)+1$? I immediately don't know how to proceed from here.

So you get $1=2(13)-5(5)$. What can you get if you take modulo $13$? — Brian Cheung, Oct 13 '17 at 07:16
I was under the impression that the correct answer is 8? Is this just not true? — jacksonf, Oct 13 '17 at 07:17
Please checkout https://math.meta.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference to typeset your formulae — , Oct 13 '17 at 07:18
@jacksonf, do you know the $\equiv$ operator and how to use it? — , Oct 13 '17 at 07:22
Note that $-5 \equiv 8 \bmod 13$ - you need to attend to the sign — Mark Bennet, Oct 13 '17 at 07:23

score 2 · Accepted Answer · answered Oct 13 '17 at 07:43

Ok, after applying the extended Euclidean algorithm applied to $13$ (modulus) and $5$ (the number you want to invert) you will find that

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

as stated. But taking this whole equation modulo $13$, we get

$$1 \equiv 13\cdot 2 + -5 \cdot 5 \equiv -5 \cdot 5 \equiv 8 \cdot 5 \pmod{13}$$

using that multiplies of $13$ vanish (are equivalent to $0$) and that $8 \equiv -5 \pmod{13}$ (add $13$ to $-5$). So $8$ and $5$ are each other's inverses in $\mathbb{Z}_{13}$. And indeed $5 \times 8 = 40$ is one plus $39$, a multiple of $13$.

For $5$ modulo $11$ we first write $1$ as a combination of $11$ and $5$:

$$1 = 1\cdot 11 - 2\cdot 5$$ and taking everything modulo $11$ again, the first term vanishes and we get that $-2$ is the inverse of $5$ modulo $11$, but $-2 \equiv 9 \pmod{11}$, so we can also use $9$ if that's more convenient. (and indeed $9\times 5 = 45 = 1 + 4\times 11 \equiv 1 \pmod{11}$ so that works out.

Basic modular inverses

1 Answers1