1
$\begingroup$

I'm trying to find the modular inverse of $$30 \pmod{7} $$ I have tried using the Euclidean algorithm and it gave me the right answer, which is $x \equiv 6 \pmod{7} $. However, I tried using another approach that I thought would be simpler, but it resulted in a wrong answer. These were my steps:

Suppose x is the modular inverse of 30 mod 7. $$30x \equiv 1 \pmod{7} $$ $$(7*4 + 2)x \equiv 1 \pmod{7} $$ $$2x \equiv 1 \pmod{7}$$ <- I have a feeling it's the previous line of simplification that's causing the problem.) So the inverse of 2 mod 7 is 4. Thus the resulting answer is $x \equiv 4 \pmod{7} $, which is wrong. Could anyone point out what is the problem here?

$\endgroup$
  • 1
    $\begingroup$ No, it's not wrong: indeed $\;30^{-1}=4\pmod 7\;$ $\endgroup$ – DonAntonio Mar 20 '16 at 10:04
  • 1
    $\begingroup$ The problem here is that the inverse of $30$ is not $6$. $\endgroup$ – Crostul Mar 20 '16 at 10:07
  • $\begingroup$ I think I did the Euclid's algorithm incorrectly. Thank you all for your help. $\endgroup$ – Tony Tarng Mar 20 '16 at 10:10
3
$\begingroup$

First, write $\;30=2\pmod 7\;$ , and now use the Euclidean algorithm with this, which is way easier.

By the way, the answer indeed is $\;4\;$ , since $\;30\cdot4=120=1+17\cdot7\;$ , or simpler: $\;2\cdot4=1+7\;$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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