<s>[INST] 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. 
 [/INST] We have $70\equiv16\pmod{27}\equiv2^4$
As $(2,27)=1,$ 
so using Carmichael function $\lambda(27)=\phi(27)=3^{3-1}(3-1)=18$ where $\phi$ is the Totient function
$\implies 2^{18}\equiv1\pmod{27}$
$\implies (2^a)^{-1}\equiv2^{18-a} \pmod{27}$
$\implies (2^4)^{-1}\equiv2^{14} \pmod{27}$
Now, $2^5=32\equiv5\pmod{27}\implies 2^{14}=(2^5)^2\cdot2^4\equiv5^2\cdot16\pmod{27}\equiv(-2)(-11)\equiv22$
We can apply this method to find inverse of any integer $a\pmod m$ where $m$ is an integer provided $(a,m)=1$
In fact, we can find smaller exponent $d(>0)$ than $\lambda(m)$ such that $a^d\equiv1\pmod m$
But,as $2$ is a primitive root of $3^2=9$
using this $,2$ is a primitive root of $3^n$ for integer $n\ge1$
$\implies $ord$_{27}2=\phi(27)=18$
</s>