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