Wednesday 13 November 2013

How do you find the modular inverse of $5pmod{!11}$



I need to find out the modular inverse of 5(mod 11), I know the answer is 9 and got the following so far and don't understand how to than get the answer. I know how to get the answer for a larger one such as 27(mod 392) but am stuck because they are both low numbers.



11=5 (2)+1



5=1 (5)


Answer




In finding a modular inverse, you are trying to solve the modular equation
$$
ax\equiv 1\pmod n.
$$
Ordinarily, you use the Extended Euclidean Algorithm for this to solve the equation $ax+ny=1$. If the numbers $a$, and $n$ are small, then simple trial and error is probably just as fast or faster.



For your example, we have $a=5$ and $n=11$, which means would could just use trial and error.
\begin{align}
1\cdot 5 &\equiv 5\\
2\cdot 5 &\equiv 10\\

3\cdot 5 &\equiv 15\equiv 4 \\
4\cdot 5 &\equiv 20\equiv -2\\
5\cdot 5 &\equiv 25\equiv 3 \\
6\cdot 5 &\equiv 30\equiv -3 \\
7\cdot 5 &\equiv 35\equiv 2 \\
8\cdot 5 &\equiv 40\equiv -4 \\
9\cdot 5 &\equiv 45\equiv 1 \\
10\cdot 5 &\equiv 50\equiv -5 \\
\end{align}




Since $9\cdot 5 \equiv 1$ then we have found the modular inverse to be 9.



When looking at those numbers on the far right side, keep in mind that any multiple of 11 made be added or subtracted to the modulus and it is still equivalent. That is, $-3\equiv 30\equiv 8$ since $-3+3(11)=30$ and $8+2(11)=30$.


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