Friday, May 24, 2019

elementary number theory - Modular Inverses



I'm doing a question that states to find the inverse of 19(mod141).



So far this is what I have:



Since gcd, an inverse exists to we can use the Euclidean algorithm to solve for it.



141 = 19\cdot 7 + 8
19 = 8\cdot 2 + 3
8 = 3\cdot 2 + 2
3 = 2\cdot 1 + 1
2 = 2\cdot 1
The textbook says that the answer is 52 but I have no idea how they got the answer and am not sure if I'm on the right track. An explanation would be appreciated! Thanks!


Answer



You're on the right track; as mixedmath says, you now have to "backtrack" your steps like this:
\begin{eqnarray}1\;\;\;\;&&=3-2\cdot 1\\ 1=&3-(8-3\cdot 2)\cdot 1&=3\cdot 3-8\\ 1=&(19-8\cdot 2)\cdot 3-8&=19\cdot 3-8\cdot 7\\ 1=&19\cdot 3-(141-19\cdot 7)\cdot 7&=19\cdot52-141\cdot 7\end{eqnarray}
This last equation, when taken modulo 141, gives 1\equiv 19\cdot 52\bmod 141, demonstrating that 52 is the inverse of 19 modulo 141.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection f \colon A \rightarrow B and I want to get bijection. Can I just resting codomain to f(A)? I know that every function i...