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