7
$\begingroup$

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!

5 Answers 5

2

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.

  • 3
    @Nate, the term (on MSE) may very well come from [Dubuque](http://math.stackexchange.com/a/174687/11763).2013-03-05
15

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.

6

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.

6

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.

4

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

  • 0
    yeah,you are right.2012-06-26