Is there a simpler way to find an inverse of a congruence? In order to find an inverse of a congruence, do we have to go through Euclid’s algorithm and do back substitution?
Here is an example to find an inverse of 9 modulo 23.

 A: There are many ways to compute modular inverses that are often simpler for smaller numbers, e.g. below I use Gauss's algorithm a few ways. The basic idea is to scale the top and bottom to obtain a $\rm\color{#c00}{smaller}$ denominator, then repeat, till the bottom exactly divides the top (or $ $ top $\!\pm\!$ modulus)
${\rm mod}\ 23\!:\,\ \dfrac{1}9\equiv \dfrac{3}{27}\equiv \dfrac{-20}{\color{#c00}4}\equiv -5$
${\rm mod}\ 23\!:\,\ \dfrac{1}9\equiv \dfrac{2}{18}\equiv \dfrac{25}{\color{#c00}{-5}}\equiv -5$
${\rm mod}\ 23\!:\,\ \dfrac{1}3\equiv \dfrac{24}3\equiv 8\,\Rightarrow\,\dfrac{1}9\equiv 8^2\equiv -5 $
Beware $\ $ Modular fraction arithmetic is well-defined only for fractions with denominator coprime to the modulus. See here for further discussion.
A: EDIT: remembered the name of the thing I was talking about: the primitive roots
My two favorite methods are guessing and brute-forcing. Together with Euclid's Algorithm, these are the most pratical ways I know of calculating inverses.
(As I see now from other answers there are many inventive representations and ways to compute just a couple of useful methods.)
Unless one knows a primitive root, in which case it generates all invertible elements and therefore inverting one is just check what is the power of the primitive root that cancels it.
A: Here's another method. Maybe you could still call it Euclid's algorithm though. Subtract consecutive equations:
$$23=23(1)+9(0)\\ 9=23(0)+9(1)\\ 5=23(1)+9(-2)$$
(Here $23-9\cdot 2= 5$)
$$4=23(-1)+9(3)\\1=23(2)+9(-5)$$
$$9(-5)\equiv 1\pmod{23}\\ 9^{-1}\equiv -5\equiv 18\pmod{23}$$
A: You can use the Euler Theorem/Fermat Little Theorem:
By Euler Theorem
$$a^{\phi(n)-1}\equiv a^{-1} \pmod{n}$$
The LHS can be calculate by doubling the power usually fast, but for large $n$ it is not as fast as the Euclidian algorithm. 
If $p$ is prime we get 
$$a^{-1} \equiv a^{p-2} \pmod{p}$$
With your example we get
$$9^2 \equiv 81 \equiv 12 \pmod{23} \\
9^4 \equiv 144 \equiv 6 \pmod{23} \\
9^8 \equiv 36 \equiv -10 \pmod{23} \\
9^{16} \equiv 100 \equiv 8 \pmod{23} \\
9{-1} \equiv 9^{21} \equiv 9^{16}\cdot 9^4 \cdot 9^1 \equiv 8 \cdot 6 \cdot 9 \equiv 2 \cdot 9 \equiv 18 \equiv -5 \pmod{23}$$
P.S. In this exercise it is much faster to find the inverse of $3 \pmod{23}$ by the Euclidian algorithm and square it.
