4
$\begingroup$

assume we want to find the multiplicative inverse for $117$ in $Z337$.

i know that in order to find the the multiplicative inverse we use Euclidean and Extended Euclidean algorithm.

Eculidian:

$337 = 2*117 + 103$

$117 = 1*103 + 14$

$103 = 7*14 + 5$

$14 = 2*5 + 4$

$5 = 1*4 + 1$

Extended Euclidean:

not going to include the whole solution because i am pretty sure of it, i get:

$1=25*337-72*117$

Extended Euclidean gives us that the inverse is $-72$. but how come a calculator says the inverse is $265$ and so do the teacher. do i need to do anything more ? usually i only need to do Euclidean and Extended Euclidean to find the inverse.

$\endgroup$
  • 1
    $\begingroup$ $-72\equiv 265\ (\textrm{ mod }337)$ $\endgroup$ – King Ghidorah Dec 11 '16 at 19:17
  • $\begingroup$ ohh i see, is it wrong to say that $-72$ is the multiplicative inverse? is it enough to stop at $-72$ ? $\endgroup$ – pabloBar Dec 11 '16 at 19:21
  • $\begingroup$ If the final result is negative, then you need to add the order ($337$ in this case). $\endgroup$ – barak manos Dec 11 '16 at 19:21
  • $\begingroup$ I fixed some typos in your question (you had $177$ vs. $117)\ \ $ $\endgroup$ – Bill Dubuque Dec 11 '16 at 20:14
  • $\begingroup$ ops, sorry it should be 117. Thanks ! $\endgroup$ – pabloBar Dec 11 '16 at 20:16
3
$\begingroup$

Either answer is correct since they are both congruent, i.e. $\,{\rm mod}\,\ 337\!:\ \color{#c00}{{-}72}\equiv 337-72\equiv 265.\ $ Below is the complete calculation by a fractional form of the Extended Euclidean Algorithm

${\rm mod}\ 337\!:\,\ \dfrac{0}{337} \overset{\large\frown}\equiv \dfrac{1}{117} \overset{\large\frown}\equiv \dfrac{-3}{\color{#0a0}{-14}} \overset{\large\frown}\equiv \dfrac{-23}5 \overset{\large\frown}\equiv\color{#c00}{\dfrac{-72} {1}}\overset{\large\frown}\equiv\dfrac{0}0\,$ or, equivalently, in equational form

$\qquad\ \ \ \begin{array}{rrl} [\![1]\!]\!:\!\!\!& 337\,x\!\!\!&\equiv\ \ 0\\ [\![2]\!]\!:\!\!\!& 117\,x\!\!\!&\equiv\ \ 1\\ [\![1]\!]-3[\![2]\!]=:[\![3]\!]\!:\!\!\!& \color{#0a0}{{-}14}\,x\!\!\!&\equiv -3\\ [\![2]\!]+8[\![3]\!]=:[\![4]\!]\!:\!\!\!& 5\,x\!\!\! &\equiv -23\\ [\![3]\!]+3[\![4]\!]=:[\![5]\!]\!:\!\!\!& \color{#c00}1\, x\!\!\! &\equiv \color{#c00}{-72} \end{array}$

Remark $\ $ This is essentially the augmented matrix form of the exteneded Euclidean algorithm, optimized by omitting one column, then interpreting the linear congruences as modular fractions.

Allowing negative remainders (i.e. least magnitude reps) often simplifies calculations, e.g.$\,10^{n}\equiv (-1)^{n}\equiv \pm1\pmod{11}\ $ is used to calculate remainders mod $11$ via alternating digit sums (casting out elevens). I did so above: $\bmod 117\!:\ 337 \equiv \color{#0a0}{{-}14}\ ({\rm vs.}\ 103\,$ in your calculation). Using the samller magnitude residue $\,-14\,$ simplifies subsequent calculations (it eliminates one step from your calculations, but generally such choices save many steps in longer calculations).

See this answer for another worked example.

$\endgroup$
  • $\begingroup$ Thanks for the answer, but i wonder if its mathematically correct to say that $-72$ is the multiplicative inverse? is it ok if the multiplicative inverse is negative ? $\endgroup$ – pabloBar Dec 11 '16 at 19:30
  • $\begingroup$ In@pabloBar $\ 117^{-1}\equiv -72\pmod{337}\,$ is correct, but $\,{ -}72 = (117^{-1}\bmod 337)\,$ is not correct. Do you understand the difference? $\endgroup$ – Bill Dubuque Dec 11 '16 at 19:33
  • $\begingroup$ how would you translate these expressions in words?, sorry a bit bad when it comes the math expressions. $\endgroup$ – pabloBar Dec 11 '16 at 19:36
  • $\begingroup$ @pabloBar $\ a\equiv b\pmod n\,$ means $\,n\,$ divides $\,a-b,\,$ but $\, a = (b\bmod n)\,$ means the same plus $\, 0\le a < n,\,$ i.e. $\,a\,$ is the least nonnegative integer $\equiv b\pmod n,\, $ i.e. the remainder left on dividing $\,b\,$ by $\,n.$ $\ \ $ $\endgroup$ – Bill Dubuque Dec 11 '16 at 19:41
  • $\begingroup$ on exam i would do the calculations above and then state with the exact words that "the multiplicative is $-72$", would my statement be correct in this case ? $\endgroup$ – pabloBar Dec 11 '16 at 19:47

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.