# Basic modular inverses

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 7:16
• I was under the impression that the correct answer is 8? Is this just not true? – jacksonf Oct 13 '17 at 7:17
• Please checkout math.meta.stackexchange.com/questions/5020/… to typeset your formulae – AnotherJohnDoe Oct 13 '17 at 7:18
• Why not? $5\times8=40$ which is congruent to $1$ mod $13$ – Brian Cheung Oct 13 '17 at 7:19
• @jacksonf, do you know the $\equiv$ operator and how to use it? – AnotherJohnDoe Oct 13 '17 at 7:22

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.