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!

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
15
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – Zev Chonoles Jun 26 '12 at 2:24
  • $\begingroup$ yeah,you are right. $\endgroup$ – Aang Jun 26 '12 at 2:46
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Nate Eldredge Mar 5 '13 at 15:58
  • 3
    $\begingroup$ @Nate, the term (on MSE) may very well come from Dubuque. $\endgroup$ – anon Mar 5 '13 at 16:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.