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?
Answer
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\;$
No comments:
Post a Comment