# 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!

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.

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.

HINT

You can backtrack through the Euclidean algorithm to find the gcd of of $19$ and $141$ as a linear combination of $19$ and $141$. That is, you can find $19x + 141 y = 1$, or subsequently $19x \equiv 1 \mod 141$. Then $x$ will be your inverse.

If $\phi(m)$ denotes the number of primes $\leq m$, then $b^{-1}\pmod m = b^{\phi(m)-1}\pmod m$.

• This is true, but even using a fast method like exponentiation by squaring, raising a number to the $\phi(141)=92$ power is much more time intensive than using Euclid's algorithm. – Zev Chonoles Jun 26 '12 at 2:24
• yeah,you are right. – Aang Jun 26 '12 at 2:46

Using method of Gauss and modulo 141: 1/19 = 8/152 = 8/11 = 104/143 = 104/2 = 52

As asked by Nate Eldredge, I am explaining it in detail:

We have to find 1/19 (mod 141). So, we take fraction 1/19, now multiply 19 with a number that is nearest to 141. If we multiply 19 with 8, we get 1/19 = 8/152. On taking modulo 141, 8/152 becomes 8/11. Now, multiply 11 with a number that makes it near to 141. This number is 13. So, when 8/11 is multiplied with 13, we get 104/143. Taking modulo 141, we get 104/2 = 52.

This can also be solved in the following manner: Let x = 1/19 (mod 141). So, 19x = 141y + 1. This can be written as 19x - 1 = 141y. Now, we can compute y = -1/141 (mod 19) = -1/8 = -2/16 = -2/-3 = 2/3 = 12/18 = -12 = +7.

As y = 7, x = (141*7+1)/19 = 52. In this way, we obtained the same answer but using much simpler computation.

• This answer, and the others you've recently posted, would be a lot more helpful if you would explain (or give a reference for) the "method of Gauss" and how you are using it here. – Nate Eldredge Mar 5 '13 at 15:58
• @Nate, the term (on MSE) may very well come from Dubuque. – anon Mar 5 '13 at 16:25