Inverse element in $\mathbb Z_{493}$

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

$ \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}$