Calculate $67^{-1} \pmod{119}$.
So I tried this and I got
\begin{align*}
x \equiv 67^{-1} \pmod{119} &\implies x \equiv \frac{1}{67} \pmod{119}\\
&\implies 67x \equiv 1 \pmod{119}\\
&\implies 67x = 1\\
&\implies x = \frac{1}{67}
\end{align*}
I just stopped after that because I knew I was going wrong can some one please help me with this one.
Best Answer
In modular arithmetic (or more generally, in a group), $a^{-1}$ does not mean $\frac{1}{a}$ in the usual sense of $\mathbb{Q}$, $\mathbb{R}$, $\mathbb{C}$, etc. (i.e. $67^{-1}$ does not mean $1 \div 67 \approx 0.0149$). In modular arithmetic, $a^{-1}$ means the multiplicative inverse of $a$. That is, it is the unique element in $\{1, \dots, 118\}$ such that $aa^{-1} = a^{-1}a \equiv 1 \pmod{119}$; note, the existence of an inverse for any non-zero element relies on the fact that the modulus is prime. If the modulus is not prime, the only non-zero elements which have multiplicative inverses are those which are coprime to the modulus.
Note: As Bill Dubuque outlines in his answer, provided $a$ is coprime to the modulus, you can treat $a^{-1}$ as $\frac{1}{a}$, but it represents a different value than it does in say $\mathbb{R}$.
Let $x$ be the multiplicative inverse of $67$ modulo $119$ (i.e. $x \equiv 67^{-1} \pmod{119}$). Then you are looking to solve $67x \equiv 1 \pmod{119}$. By definition, $67x \equiv 1 \pmod{119}$ means that $119 \mid (67x - 1)$ so there is some integer $y$ such that $67x - 1 = 119y$, or written differently $67x + 119y = 1$. Note, if $67$ and $119$ weren't coprime, this equation would have no integer solutions. This is a diophantine equation that you can solve by using the Euclidean algorithm and back substitution. Have you seen this before?