Inverse element in $\mathbb Z_{493}$ I am trying to find the inverse for $348$ in $\mathbb Z/493$.
So since $x \cdot x^{-1} = 1$, I have tried to solve it by using the extended euclidean algorithm. $\gcd(493, 348):$
\begin{align}
493 &= 348 \cdot 1 + 145\\
348 &= 145 \cdot 2 + 58\\
145 &= 58 \cdot 2 + 29\\
58 &= 29 \cdot 2 + 0
\end{align}
Then the linear combination:
\begin{align} 
29 &= 145 - 52 \cdot 2\\
29 &= 145 - (348 - 145 \cdot 2) \cdot 2\\
29 &= -2 \cdot 348 + 5 \cdot 145\\
29 &= -2 \cdot 348 + 5 \cdot (493 - 348)\\
29 &= -7 \cdot 348 + 5 \cdot 493
\end{align}
Question: If there is an inverse, is it $-7$ here? Is that the correct way to find an inverse ?
I appreciate every hint.
 A: Quite simply, this inverse does not exist.  Given an $x \in \mathbb{Z}$, the equivalence class to which $x$ belongs is invertible in $\mathbb{Z}_m \iff \gcd(x, m) = 1$.  
In such a case, you would proceed exactly as you tried here.  Using  the extended Euclidean algorithm, we can find integers $a$ and $b$ such that $ax + bm = 1$.  Modding out both sides of this equation by $m$ yields $ax \equiv 1 \pmod{m}$; thus, the equivalence class to which $a$ belongs is the inverse of that to which $x$ belongs.
A: $ \begin{align}{\bf Hint}\quad  \overbrace{j\,a\equiv 1\!\!\!\pmod{\! n}}^{\large a^{-1}\ {\rm exists\ mod\ } n}\,&\Rightarrow\, j\,\color{#0a0}a + k\,\color{#0a0}n \,=\, \color{#c00}{\bf 1}\,\Rightarrow\,\gcd(\color{#0a0}{a,n})=1\\[0.5em] 
&\!\!\!\!\!{\rm by}\quad d\mid\color{#0a0}{a,n}\Rightarrow d\mid\color{#c00}{\bf 1}\end{align}$
A: The inverse here is found from the continued fraction, not the residue.
               0       A   B     C
  493          1     493         1            
  348    1     1     349   1     1            
  145    2     3     144   2     3            
   58    2     7      61   2     7             
   29    2    17      22   2    17             
    0                 17   1    24             
                       5   3    89             
                       2   2   202            
                       1   2   493           

This actually finds that the LCM of 493 and 348 is 29.  Therefore, this number does not have an inverse, relative to 493.  Here we find 202*493 is +/- 1, there are 8 numbers in the continued fraction, so 202 * 493 = -1, and we take 493-202=291 as the required answer.
The columns A start with the modulus (493) and the number for which the reciprocal is required (349).  Column A continues with remainders or the previous two entries.
Column B consists of the whole parts, eg 493 = 1*349+144.
Column C derives from column B, in C(n) = B(n).C(n-1)+C(n-2), where C(0)=0, C(1)=1.  The last entry should be the modulus itself (493).  The second last entry is + 1/x if there is an odd number of rows, and -1/x if there is an even number of rows.
