elementary number theory - double check my steps to find multiplicative inverse?

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.

Answer

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 extended 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 smaller 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.