Finding Multiplicative Inverse

Question

I'm told to find the multiplicative inverse of $\mathbf 9\bmod37$.

I can't really use the the Euclidean Algorithm on the equation $\mathbf 9 = Q \cdot 37 + R$ where the LHS is already smaller than the RHS or am I wrong in thinking this way?

Answer 1

Hint, easy to observe $9\cdot(-4)=-36=1 \pmod {37}$. On your other point, Euclidean algorithm works fine.

Answer 2

Since 4 and 37 are relatively prime, you have $$37\mid (9x-1)\iff 37\mid 4(9x-1)\iff 37\mid (36x-4)\iff 37\mid (-x-4)\iff x\equiv -4\equiv 33\pmod{37}$$ So 33 is the inverse.