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
up vote 2 down vote accepted

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
  • Yeah, I definitely need to reread this chapter because I'm having a lot of issues understanding this. Thanks for the help! – John Mar 3 '16 at 19:05

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.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.