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. 

To illustrate how you would use your work here:
$$ 70 = 2(27) + 16 \\  
 27 = 1(16) + 11 \\   
 16 = 1(11) + 5  \\   
 11 = 2(5) + 1  $$   (last line modified)
From this point, we start stacking these results together, so as to get $1$, $27$ and $70$ all in the same expression:
$$ 1=11-2(5)\\
1=11-2(16-11)=3(11)-2(16)\\
1=3(27-16)-2(16)=3(27)-5(16)\\
1=3(27)-5(70-2(27))=13(27)-5(70)
$$
Thus, $1\equiv 13(27)-5(70)\equiv 0 -5(70)\equiv 22(70)\pmod{27}$
Actually this can be shortened somewhat by reducing $70\equiv 16\pmod{27}$ ahead of time. Then you only have to deal with the last three equations in your list. Once you get to this point
$$
1=3(27)-5(16)
$$
you can conclude that $1\equiv 0-5(16)\equiv 22(70)$ and be done.
