Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

5 Answers 5

up vote 4 down vote accepted

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.

share|improve this 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.

share|improve this answer

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.

share|improve this answer

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

share|improve this answer
4  
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.

share|improve this answer
    
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
2  
@Nate, the term (on MSE) may very well come from Dubuque. –  anon Mar 5 '13 at 16:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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