How to find the inverse of 70 (mod 27) The question pertains to decrypting a Hill Cipher, but I am stuck on the part where I find the inverse of $70 \pmod{ 27}$. Does the problem lie in $70$ being larger than $27$?
I've tried Gauss's Method:
$\frac{1}{70} = \frac{1}{16} ^{\times2}_{\times2} = \frac{2}{32} = \frac{2}{5} = \frac{12}{30} = \frac{12}{3} = \frac{132}{33} = \frac{24}{6} = \frac{120}{30} $
And the denominators start repeating so I can never get 1 in the denominator.
And the Euclidean Algorithm
$\ 70 = 2(27) + 16 $
$\ 27 = 1(16) + 11 $
$\ 16 = 1(11) + 5  $
$\ 11 = 1(5) + 6  $
$\ 5 = 1(6) -1  $  
Which is also not helpful. I think I'm trying to get + 1 on the last equation for $1 \pmod{ 27}$, but maybe I'm misunderstanding the method.
Am I approaching this incorrectly? I'm new to modular arithmetic. 

A couple of ideas (working all the time modulo $\,27\,$):
$$\begin{align*}\bullet&\;\;70=14\cdot 5\\
\bullet&\;\;14\cdot2=28=1\implies& 14^{-1}=2\\
\bullet&\;\;5\cdot 11=55=2\cdot 27+1=1\implies&5^{-1}=11\end{align*}$$
Thus, finally, we get
$$70^{-1}=14^{-1}\cdot 5^{-1}=2\cdot 11=22$$
