Wednesday, December 20, 2017

elementary number theory - Modular Inverses



I'm doing a question that states to find the inverse of $19 \pmod {141}$.



So far this is what I have:




Since $\gcd(19,141) = 1$, 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...