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. 

Another way as $70=7\cdot 10$
$(70)^{-1}\equiv 7^{-1}\cdot 10^{-1}$
Now, as $7\cdot4=28\equiv1\pmod{27}\implies 7^{-1}\equiv4\pmod{27}$
and $27\cdot37=999\equiv1000-1\implies 10\cdot100\equiv1\pmod{27}\implies 10^{-1}\equiv100\pmod{27}\equiv19$
$\implies (70)^{-1}\equiv4\cdot19\pmod{27}\equiv22$
