I'm trying to find the modular inverse of 30(mod7)
I have tried using the Euclidean algorithm and it gave me the right answer, which is x≡6(mod7). 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≡1(mod7)
(7∗4+2)x≡1(mod7)
2x≡1(mod7)
<- 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≡4(mod7), which is wrong. Could anyone point out what is the problem here?
Answer
First, write 30=2(mod7) , and now use the Euclidean algorithm with this, which is way easier.
By the way, the answer indeed is 4 , since 30⋅4=120=1+17⋅7 , or simpler: 2⋅4=1+7
No comments:
Post a Comment