Friday, 8 November 2013

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.


Answer




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.


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...