3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So you get $1=2(13)-5(5)$. What can you get if you take modulo $13$? $\endgroup$ – Brian Cheung Oct 13 '17 at 7:16
  • $\begingroup$ I was under the impression that the correct answer is 8? Is this just not true? $\endgroup$ – jacksonf Oct 13 '17 at 7:17
  • 1
    $\begingroup$ Please checkout math.meta.stackexchange.com/questions/5020/… to typeset your formulae $\endgroup$ – AnotherJohnDoe Oct 13 '17 at 7:18
  • $\begingroup$ Why not? $5\times8=40$ which is congruent to $1$ mod $13$ $\endgroup$ – Brian Cheung Oct 13 '17 at 7:19
  • $\begingroup$ @jacksonf, do you know the $\equiv$ operator and how to use it? $\endgroup$ – AnotherJohnDoe Oct 13 '17 at 7:22
2
$\begingroup$

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.

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