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!
Best Answer
Hint $\, $ Applying the $\rm\color{#940}{Euclidean}$ algorithm to $\rm\color{#C00}{LHS}$ column yields $\rm\: \color{#0A0}{52\cdot 19}\,\equiv\, 1\pmod{141}.\:$
$$\rm\begin{eqnarray}(1)\quad \color{#C00}{141}\!\ &=&\,\ \ \ 1&\cdot& 141\, +\ 0&\cdot& 19 \\ (2)\quad\ \color{#C00}{19}\ &=&\,\ \ \ 0&\cdot& 141\, +\ 1&\cdot& 19 \\ \color{#940}{(1)-7\,(2)}\, \rightarrow\, (3)\quad\ \ \ \color{#C00}{ 8}\ &=&\,\ \ \ 1&\cdot& 141\, -\ 7&\cdot& 19 \\ \color{#940}{(2)-2\,(3)}\,\rightarrow\,(4)\quad\ \ \ \color{#C00}{3}\ &=&\, {-}2&\cdot& 141\, + 15&\cdot& 19 \\ \color{#940}{(3)-3\,(4)}\,\rightarrow\,(5)\quad \color{#C00}{{-}1}\ &=&\,\ \ \ 7&\cdot& 141\, -\color{#0A0}{ 52}&\cdot& \color{#0A0}{19} \end{eqnarray}\qquad$$
See this answer for much more on this extended Euclidean algorithm.