# Finding modular inverse (wrong approach)

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?

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

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\;$