Multiplicative Inverse Question What is the multiplicative inverse of $9\pmod{37}$?
I've done the Euclidean algorithm and found the gcd is $1$. I'm stuck on using the extended Euclidean algorithm. I'm confused because I'm left with $$37=(9\times 4)+1$$ and can't substitute it anywhere.
 A: For small numbers, you don't need the Extended Euclidean Algorithm. Just set up the required congruence and solve, choosing multipliers, relatively prime to the modulus, that successively work to force the coefficient of the unknown to get smaller and smaller in absolute value (and eventually equal to $1$). For example . . .
\begin{align*}
&9x \equiv 1 \pmod{37}\\[6pt]
\implies\; &36x \equiv 4 \pmod{37}\\[6pt]
\implies\; &-x \equiv 4 \pmod{37}\\[6pt]
\implies\; &x \equiv {-4} \pmod{37}\\[6pt]
\implies\; &x \equiv {33} \pmod{37}\\[6pt]
\end{align*}
A: We need to find for $x$ such that $$9x\equiv 1\pmod {37}.$$ By inspection, one can see that a particular solution is $$x_0=-4.$$ So all soultions are given by $$x\equiv -4\pmod{37}.$$
But $$-4\equiv 33\pmod{37}.$$ Thus, 
$$x\equiv 33\pmod{37}.$$
A: The technique in quasi's answer can be proven as follows.

Take any integers $m,a,b,x$ such that $0 < a < m$ and $ax \equiv b \pmod{m}$.
If $a = 1$ then we are done so from now we assume that $a > 1$.
Let $k$ be the smallest positive integer such that $ak \ge m$.
If $ak = m$ then:
  $a \mid m \mid ax-b$ and hence $a \mid b$.
  Let $c$ be an integer such that $b = ac$.
  Then $ak = m \mid a(x-c)$ and hence $x \equiv c \pmod{k}$.   [(◇) See note below.]
If $ak > m$ then:
  $m > a(k-1)$ and hence $0 < ak-m < a$.
  $(ak-m)x \equiv akx \equiv bk \pmod{m}$.
Therefore in all cases we have reduced the equation to be solved to a simpler one.

Note that the (◇) is not necessarily reversible. If $m$ is known to be a prime then we never use (◇) so it is alright. Otherwise we will have to check all the possible solutions at the end. Here is an example:
Take any integer $x$ such that $9x \equiv 1 \pmod{14}$.
Then $4x \equiv 2(9x) \equiv 2 \pmod{14}$.
Thus $2x \equiv 4(4x) \equiv 8 \pmod{14}$.
Thus $x \equiv 4 \pmod{7}$.
Since the original equation is modulo $14$, it suffices to check all $x$ from $0$ to $13$ that satisfies the last equation. It turns out that $11$ is a solution (but $4$ is not).
We can easily avoid this problem by using multipliers that are coprime to the modulus, as quasi suggested. However, algorithmically, how do we tell this? We could use the Euclidean algorithm for this since the multiplier is small, or we could just use small primes and check whether they are divisible by the modulus.
A: $37=9\cdot 4 + 1$  therefore $9\cdot 4 + 1\equiv 0\pmod{37}$
$9\cdot 4 \equiv -1\pmod{37}$
$9\cdot (-4)\equiv 1\pmod{37}$
$9\cdot (37-4)\equiv 1\pmod{37}$
