# Finding Multiplicative Inverse

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?

• Note the uses of \mod, \bmod, and \pmod $(a\equiv b)\pmod c$ is coded as (a\equiv b)\pmod c. If there's more than one character to be included in the parentheses, you need {curly braces}, thus $(a\equiv b) \pmod{37}$ is coded as (a\equiv b) \pmod{37}. In \bmod, the "b" stands for "binary", and that means the spacing conventions used for binary operators like "$+$" are used, thus $a\bmod b$. I edited the question, using \bmod. (And the "p" in \pmod stands for "parentheses".) $\qquad$ – Michael Hardy Mar 3 '16 at 19:21
• The Euclidean Algorithm gives $37 = 4 \cdot 9 + 1$. Solving for $1$ yields $1 = 37 - 4 \cdot 9$. Hence, $9^{-1} \equiv -4 \equiv 33 \pmod{37}$. – N. F. Taussig Mar 4 '16 at 8:50

Hint, easy to observe $9\cdot(-4)=-36=1 \pmod {37}$. On your other point, Euclidean algorithm works fine.
• So $\mathbf 9(mod)37$ is in the same equivalence class as $\mathbf 1(mod)37$? I don't understand how this helps. Maybe I need to read up on this topic a bit more – John Mar 3 '16 at 18:45
• No. $9*(-4)=-36$ is. So $-4=33 \pmod {37}$ becomes the inverse. – Nemo Mar 3 '16 at 18:48
• Okay, that makes a lot of sense actually. How much different would the question be if it became $\mathbf 8(mod)37$ since it doesn't leave you with a remainder of 1? – John Mar 3 '16 at 18:54
• Better to use the Euclidean algorithm in general. You'll get $8*14-37*3=1$, and taking mod $37$ the inverse is obvious. – Nemo Mar 3 '16 at 18:59
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.